4《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》復(fù)習(xí)題

1、1數(shù)據(jù)結(jié)構(gòu)導(dǎo)論數(shù)據(jù)結(jié)構(gòu)導(dǎo)論模擬試題模擬試題一、考試題型及分值分布：一、考試題型及分值分布：1、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)2、填空題(本大題共13小題，每小題2分，共26分)3、應(yīng)用題(本大題共5小題，每小題6分，共30分)4、算法設(shè)計(jì)題(本大題共2小題，每小題7分，共14分)二、單項(xiàng)選擇題和填空題樣題參考二、單項(xiàng)選擇題和填空題樣題參考（一）單項(xiàng)選擇題（一）單項(xiàng)選擇題1.在二維數(shù)組中，每個(gè)數(shù)組元素同時(shí)處于（）個(gè)向

2、量中。A.0B.1C.2D.n2.已知單鏈表A長(zhǎng)度為m，單鏈表B長(zhǎng)度為n，它們分別由表頭指針?biāo)赶?，若將B整體連接到A的末尾，其時(shí)間復(fù)雜度應(yīng)為（）。A.O(1)B.O(m)C.O(n)D.O(mn)3.假定一個(gè)鏈?zhǔn)疥?duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear，則判斷隊(duì)空的條件為()。A.front==rearB.front!=NULLC.rear!=NULLD.front==NULL4.若讓元素123依次進(jìn)棧，則出棧次序不可能出現(xiàn)()

3、種情況。A.321B.213C.312D.1325.圖的廣度優(yōu)先搜索類(lèi)似于樹(shù)的（）遍歷。A.先根B.中根C.后根D.層次6.下面程序段的時(shí)間復(fù)雜度為()。f(inti=0ilink=sB.slink=toplinktoplink=sC.slink=toptop=sD.slink=toptop=toplink10.一棵具有35個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為()。假定空樹(shù)的高度為1。A.5B.6C.7D.811.一個(gè)有n個(gè)頂點(diǎn)和n條邊的無(wú)向圖一

4、定是()的。A連通B不連通C無(wú)回路D有回路12.在一個(gè)長(zhǎng)度為n的順序表的任一位置插入一個(gè)新元素的時(shí)間復(fù)雜度為（）。A.O(n)B.O(n2)C.O(1)D.O(n2)13.已知廣義表為A((abc)(def))，從A中取出原子e的運(yùn)算是（）。ATail(Head(A))BHead(Tail(A))3（1）求有向圖結(jié)點(diǎn)的拓?fù)湫蛄校浣Y(jié)果必定是唯一的（2）求兩個(gè)指向結(jié)點(diǎn)間的最短路徑，其結(jié)果必定是唯一的（3）求AOE網(wǎng)的關(guān)鍵路徑，其結(jié)果必定是

5、唯一的其中哪個(gè)（些）是正確的？A.只有（1）B.（1）和（2）C.都正確D.都不正確30若進(jìn)棧序列為abc，則通過(guò)入出棧操作可能得到的abc的不同排列個(gè)數(shù)為:()A.4B.5C.6D.731.以下關(guān)于廣義表的敘述中正確的是：()A.廣義表是由0個(gè)或多個(gè)單元素或子表構(gòu)成的有限序列B.廣義表至少有一個(gè)元素是子表C.廣義表不能遞歸定義D)廣義表不能為空表32.排序時(shí)掃描待排序記錄序列，順次比較相鄰的兩個(gè)元素的大小，逆序時(shí)就交換位置。這是哪種排

6、序方法的基本思想？()A.堆排序B.直接插入排序C.快速排序D.冒泡排序33已知一個(gè)有向圖的鄰接矩陣表示，要?jiǎng)h除所有從第i個(gè)結(jié)點(diǎn)發(fā)出的邊，應(yīng)該：()A.將鄰接矩陣的第i行刪除B.將鄰接矩陣的第i行元素全部置為0C.將鄰接矩陣的第i列刪除D.將鄰接矩陣的第i列元素全部置為034有一個(gè)含頭結(jié)點(diǎn)的雙向循環(huán)鏈表，頭指針為head則其為空的條件是：()A.headpriro==NULLB.headnext==NULLC.headnext==hea

7、dD.headnextpriro==NULL35.在順序表(3681012151618212530)中，用折半法查找關(guān)鍵碼值11，所需的關(guān)鍵碼比較次數(shù)為：()A.2B.3C.4D.536.以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？()A.從隊(duì)尾插入一個(gè)新元素B.從隊(duì)列中刪除第i個(gè)元素C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值37對(duì)包含n個(gè)元素的哈希表進(jìn)行查找，平均查找長(zhǎng)度為：()A.O(log2n)B.O(n)C.O(nlog2n)D不直接依賴于

8、n38將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為1，則編號(hào)最大的非葉結(jié)點(diǎn)的編號(hào)為：()A.48B.49C.50D.5139某二叉樹(shù)結(jié)點(diǎn)的中序序列為A、B、C、D、E、F、G，后序序列為B、D、C、A、F、G、E，則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為：()A.3B.2C.4D.540下面是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)。A.存儲(chǔ)密度大B.插入運(yùn)算方便C.查找方便D.適合各種邏輯結(jié)構(gòu)的存儲(chǔ)表示41下面關(guān)于串的敘述中