工程圖學(xué)總復(fù)習(xí)題

1、數(shù)據(jù)結(jié)構(gòu)和算法的基本概念數(shù)據(jù)結(jié)構(gòu)和算法的基本概念一判斷題（下列各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打一判斷題（下列各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打√；錯(cuò)誤的打；錯(cuò)誤的打╳）（√）（1）數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。（√）（2）一個(gè)數(shù)據(jù)結(jié)構(gòu)是由一個(gè)邏輯結(jié)構(gòu)和這個(gè)邏輯結(jié)構(gòu)上的一個(gè)基本運(yùn)算集構(gòu)成的整體。（ㄨ）（3）數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（ㄨ）（4）數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是相同的。（ㄨ）（5）程序和算法原則上沒(méi)有區(qū)別，所以在討

2、論數(shù)據(jù)結(jié)構(gòu)時(shí)可以通用。（√）（6）從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。（√）（7）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲(chǔ)映像。（√）（8）數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)實(shí)際的存儲(chǔ)形式。（ㄨ）（9）數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計(jì)算機(jī)的。（√）（10）算法是對(duì)解題方法和步驟的描述。三選擇題三選擇題（1）數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（A）及它們之間的相互聯(lián)系。A.存儲(chǔ)結(jié)構(gòu)和邏輯結(jié)構(gòu)B.存儲(chǔ)和抽象C.聯(lián)系和抽象D.聯(lián)系與邏輯（2）在

3、邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成：（C）。A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)（3）數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（C）。A.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲(chǔ)結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（4）非線性結(jié)構(gòu)中的每個(gè)結(jié)點(diǎn)（D）。無(wú)直接前趨結(jié)點(diǎn)無(wú)直接后繼結(jié)點(diǎn)只有一個(gè)直接前趨結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn)可能有多個(gè)直接前趨結(jié)點(diǎn)和多個(gè)直接后繼結(jié)點(diǎn)（5）鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)

4、空間（A）。A分兩部分，一部分存放結(jié)點(diǎn)的值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針B只有一部分，存放結(jié)點(diǎn)的值C只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針D分兩部分，一部分存放結(jié)點(diǎn)的值，另一部分存放結(jié)點(diǎn)所占單元素（6）算法的計(jì)算量大小稱為算法的（C）。A.現(xiàn)實(shí)性B.難度C.時(shí)間復(fù)雜性D.效率（7）數(shù)據(jù)的基本單位是（B）。A.數(shù)據(jù)結(jié)構(gòu)B.數(shù)據(jù)元素C.數(shù)據(jù)項(xiàng)D.文件（8）每個(gè)結(jié)點(diǎn)只含有一個(gè)數(shù)據(jù)元素，所有存儲(chǔ)結(jié)點(diǎn)相繼存放在一個(gè)連續(xù)的存儲(chǔ)區(qū)里，這種存儲(chǔ)結(jié)構(gòu)稱

5、為（A）結(jié)構(gòu)。A.順序存儲(chǔ)B.鏈?zhǔn)酱鎯?chǔ)C.索引存儲(chǔ)D.散列存儲(chǔ)（9）每一個(gè)存儲(chǔ)結(jié)點(diǎn)不僅含有一個(gè)數(shù)據(jù)元素，還包含一組指針，該存儲(chǔ)方式是（B）（）（6）順序表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。（√）（7）線性表鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是可以用一組任意的存儲(chǔ)單元存儲(chǔ)表中的數(shù)據(jù)元素。（√）（8）線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。（）（9）順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。（ㄨ）（10）插

6、入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。二填空題二填空題順序表中邏輯上相鄰的元素在物理位置上必須相連。線性表中結(jié)點(diǎn)的集合是有限的，結(jié)點(diǎn)間的關(guān)系是一對(duì)一關(guān)系。順序表相對(duì)于鏈表的優(yōu)點(diǎn)是：節(jié)省存儲(chǔ)和隨機(jī)存取。鏈表相對(duì)于順序表的優(yōu)點(diǎn)是：插入、刪除方便。（5）采用順序存儲(chǔ)結(jié)構(gòu)的線性表叫順序表。（6）順序表中訪問(wèn)任意一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(1)。（7）鏈表相對(duì)于順序表的優(yōu)點(diǎn)是插入、刪除方便；缺點(diǎn)是存儲(chǔ)密度小。

7、（8）在雙鏈表中要?jiǎng)h除已知結(jié)點(diǎn)P，其時(shí)間復(fù)雜度為O(1)。（9）在單鏈表中要在已知結(jié)點(diǎn)P之前插入一個(gè)新結(jié)點(diǎn)，需找到P的直接前趨結(jié)點(diǎn)的地址，其查找的時(shí)間復(fù)雜度為O(n)。單鏈表中需知道頭指針才能遍歷整個(gè)鏈表。性表中第一個(gè)結(jié)點(diǎn)沒(méi)有直接前趨，稱為開(kāi)始結(jié)點(diǎn)。在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素，要移動(dòng)ni個(gè)元素。在一個(gè)長(zhǎng)度為n的順序表中，如果要在第i個(gè)元素前插入一個(gè)元素，要后移ni1個(gè)元素。在無(wú)頭結(jié)點(diǎn)的單鏈表中，第一個(gè)結(jié)點(diǎn)的地址存放在頭指針中

8、，而其它結(jié)點(diǎn)的存儲(chǔ)地址存放在前趨結(jié)點(diǎn)的指針域中。當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快速度存取線性表中的元素時(shí)，應(yīng)采用順序存儲(chǔ)結(jié)構(gòu)。在線性表的鏈?zhǔn)酱鎯?chǔ)中，元素之間的邏輯關(guān)系是通過(guò)指針決定的。在雙向鏈表中，每個(gè)結(jié)點(diǎn)都有兩個(gè)指針域，它們一個(gè)指向其前趨結(jié)點(diǎn)，另一個(gè)指向其后繼結(jié)點(diǎn)。對(duì)一個(gè)需要經(jīng)常進(jìn)行插入和刪除操作的線性表，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為宜。雙鏈表中，設(shè)p是指向其中待刪除的結(jié)點(diǎn)，則需要執(zhí)行的操作為：pprinext