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

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

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

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

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

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

6、序方法的基本思想？()A.堆排序B.直接插入排序C.快速排序D.冒泡排序33已知一個有向圖的鄰接矩陣表示，要刪除所有從第i個結(jié)點發(fā)出的邊，應(yīng)該：()A.將鄰接矩陣的第i行刪除B.將鄰接矩陣的第i行元素全部置為0C.將鄰接矩陣的第i列刪除D.將鄰接矩陣的第i列元素全部置為034有一個含頭結(jié)點的雙向循環(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.以下哪一個不是隊列的基本運算？()A.從隊尾插入一個新元素B.從隊列中刪除第i個元素C.判斷一個隊列是否為空D.讀取隊頭元素的值37對包含n個元素的哈希表進行查找，平均查找長度為：()A.O(log2n)B.O(n)C.O(nlog2n)D不直接依賴于

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