02142《數(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、單項選擇題(本大題共 15 小題，每小題 2 分，共 30 分)2、填空題(本大題共 13 小題，每小題 2 分，共 26 分)3、應(yīng)用題(本大題共 5 小題，每小題 6 分，共 30 分)4、算法設(shè)計題(本大題共 2 小題，每小題 7 分，共 14 分)二、單項選擇題和填空題樣題參考二、單項選擇題和填空題樣題參考( (一一) )單項選擇題單項選擇題1. 在二維數(shù)組中，每個數(shù)組元素同時處于()個向量中。A. 0B.1C.2D.n2. 已知單鏈表 A 長度為 m,單鏈表 B 長度為 n,它們分別由表頭指

2、針?biāo)赶?，若?B 整體連接到 A 的末尾，其時間復(fù)雜度應(yīng)為()。A. O(1)B.O(m)C.O(n)D.O(m+n)3. 假定一個鏈?zhǔn)疥犃械年狀^和隊尾指針分別為 front 和 rear,則判斷隊空的條件為()。A. front=rearB.front!=NULLC.rear!=NULLD.front=NULL4. 若讓元素 1,2,3 依次進(jìn)棧,則出棧次序不可能出現(xiàn)()種情況。A. 3,2,1B.2,1,3C.3,1,2D.1,3,25. 圖的廣度優(yōu)先搜索類似于樹的()遍歷。A. 先根 B.中根 C.后根 D.層次6. 下面程序段的時間復(fù)雜度為()。for(inti=0;im;i+)fo

3、r(intj=0;jlink=s;B.s-link=top-link;top-link=s;C.s-link=top;top=s;D.s-link=top;top=top-link;10. 一棵具有 35 個結(jié)點(diǎn)的完全二叉樹的高度為()。假定空樹的高度為-1。A.5B.6C.7D.811. 一個有 n 個頂點(diǎn)和 n 條邊的無向圖一定是()的。A.連通 B.不連通 C.無回路 D.有回路12. 在一個長度為 n 的順序表的任一位置插入一個新元素的時間復(fù)雜度為()。A.O(n)B.O(n/2)C.O(1)D.O(n2)13. 已知廣義表為 A(a,b,c),(d,e,f),從 A 中取出原子 e

4、的運(yùn)算是()。A.Tail(Head(A)B.Head(Tail(A)CHead(Tail(Head(Tail(A)DHead(Head(Tail(Tail(A)214. 在一棵樹的靜態(tài)雙親表示中，每個存儲結(jié)點(diǎn)包含()個域。A1B2C3D415. 有向圖中的一個頂點(diǎn)的度數(shù)等于該頂點(diǎn)的()。A入度 B出度C入度與出度之和 D.(入度+出度)/215.與鄰接矩陣相比，鄰接表更適合于存儲()。A.無向圖 B.連通圖 C.稀疏圖 D.稠密圖17. 較快的數(shù)據(jù)搜索方法是()搜索方法。A.順序 B.折半 C.單鏈 D.散列18. 在閉散列表中，散列到同一個地址而引起的“堆積”問題是由于()引起的。A.同義

5、詞之間發(fā)生沖突 B.非同義詞之間發(fā)生沖突C.同義詞之間或非同義詞之間發(fā)生沖突 D.散列表“溢出”19. 根據(jù) n 個元素建立一個有序單鏈表的時間復(fù)雜度為()。A.O(1)B.O(n)C.O(n2)D.O(nlogn)20. 假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為 front 和 rear，則判斷隊空的條件為()。A.front+1=rearB.rear+1=frontC.front=0D.front=rear21. 假定一棵二叉樹的第 i 層上有 3i 個結(jié)點(diǎn)，則第 i+1 層上最多有()個結(jié)點(diǎn)。A.3iB.6iC.9iD.2i22. 對于具有 e 條邊的無向圖，它的鄰接表中共有()

6、個邊結(jié)點(diǎn)。A.e-1B.e+1C.2eD.3e23. 圖的深度優(yōu)先搜索遍歷類似于樹的()次序遍歷。A.先根 B.中根 C.后根 D.層次24.棧 S 最多能容納 4 個元素?，F(xiàn)有 6 個元素按 A、B、C、D、E、F 的順序進(jìn)棧，問下列哪一個序列是可能的出棧序列?()A.E、D、C、B、A、FB.B、C、E、F、A、DC. C、B、E、D、A、FD.A、D、F、E、B、C25. 將一棵有 100 個結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)編號為 1，則編號為 49 的結(jié)點(diǎn)的左孩子的編號為：()A.98B.99C.50D.4826. 對下列關(guān)鍵字序列用快速排序法進(jìn)

7、行排序時，速度最快的情形是：()A. 21、25、5、17、9、23、30B. 25、23、30、17、21、5、9B. 21、9、17、30、25、23、5D. 5、9、17、21、23、25、3027.對于只在表的首、尾進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為()A.順序表 B.用頭指針表示的單循環(huán)鏈表C. 用尾指針表示的單循環(huán)鏈表 D.單鏈表28. 假設(shè)以第一個元素為分界元素，對字符序列(Q,H,C,Y,P,A,M,S,R,D,F,X)進(jìn)行快速排序，則第一次劃分的結(jié)果是：()A. (A,C,D,F,H,M,P,Q,R,S,X,Y)B. (A,F,H,C,D,P,M,Q,R,S,Y,X)C

8、. (F,H,C,D,P,A,M,Q,R,S,Y,X)D. (P,A,M,F,H,C,D,Q,S,Y,R,X)29. 下面是三個關(guān)于有向圖運(yùn)算的敘述：()(1)求有向圖結(jié)點(diǎn)的拓?fù)湫蛄?，其結(jié)果必定是唯一的3(2)求兩個指向結(jié)點(diǎn)間的最短路徑，其結(jié)果必定是唯一的(3) 求 AOE 網(wǎng)的關(guān)鍵路徑，其結(jié)果必定是唯一的其中哪個(些)是正確的？A.只有(1)B.(1)和(2)C.都正確 D.都不正確30. 若進(jìn)棧序列為 a,b,c,則通過入出棧操作可能得到的 a,b,c 的不同排列個數(shù)為:()A.4B.5C.6D.731. 以下關(guān)于廣義表的敘述中,正確的是：()A. 廣義表是由 0 個或多個單元素或子表構(gòu)成

9、的有限序列B. 廣義表至少有一個元素是子表C. 廣義表不能遞歸定義D)廣義表不能為空表32. 排序時掃描待排序記錄序列，順次比較相鄰的兩個元素的大小，逆序時就交換位置。這是哪種排序方法的基本思想？()A.堆排序 B.直接插入排序 C.快速排序 D.冒泡排序33. 已知一個有向圖的鄰接矩陣表示，要刪除所有從第 i 個結(jié)點(diǎn)發(fā)出的邊，應(yīng)該：()A.將鄰接矩陣的第 i 行刪除 B.將鄰接矩陣的第 i 行元素全部置為 0C.將鄰接矩陣的第 i 列刪除 D.將鄰接矩陣的第 i 列元素全部置為 034. 有一個含頭結(jié)點(diǎn)的雙向循環(huán)鏈表，頭指針為 head,則其為空的條件是：()A.head-priro=NUL

10、LB.head-next=NULLC.head-next=headD.head-next-priro=NULL35. 在順序表(3,6,8,10,12,15,16,18,21,25,30 中)，用折半法查找關(guān)鍵碼值 11，所需的關(guān)鍵碼比較次數(shù)為：()A.2B.3C.4D.536. 以下哪一個不是隊列的基本運(yùn)算？()A.從隊尾插入一個新元素 B.從隊列中刪除第 i 個元素C.判斷一個隊列是否為空 D.讀取隊頭元素的值37. 對包含 n 個元素的哈希表進(jìn)行查找，平均查找長度為：()A.O(logn)B.O(n)C.O(nlogn)D 不直接依賴于 n38. 將一棵有2100 個結(jié)點(diǎn)的完全二叉樹從根

11、這一2層開始，每一層從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)編號為 1，則編號最大的非葉結(jié)點(diǎn)的編號為：()A.48B.49C.50D.5139. 某二叉樹結(jié)點(diǎn)的中序序列為 A、B、C、D、E、F、G,后序序列為 B、D、C、A、F、G、E,則其左子樹中結(jié)點(diǎn)數(shù)目為：()A.3B.2C.4D.540.下面是順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)。A.存儲密度大 B.插入運(yùn)算方便C.查找方便 D.適合各種邏輯結(jié)構(gòu)的存儲表示41._下面關(guān)于串的敘述中，是不正確的。A.串是字符的有限序列 B.空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運(yùn)算 D.串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?2._ 的鄰接矩陣是對稱矩陣。A.有向圖

12、 B.無向圖 C.AOV 網(wǎng) D.AOE 網(wǎng)43._ 用鏈?zhǔn)椒绞酱鎯Φ年犃?，在進(jìn)行刪除運(yùn)算時，。A.僅修改頭指針 B.僅修改尾指針C.頭、尾指針都要修改 D.頭、尾指針可能都要修改44._ 二叉樹的先序遍歷和中序遍歷如下，則該二叉樹右子樹的樹根。先序序列：EFHIGJK 中序序列：HFIEJKG4A.EB.FC.GD.H45. 下面方法可以判斷出一個有向圖中是否有環(huán)。A.深度優(yōu)先遍歷 B.拓樸排序 C.求最短路徑 D.求關(guān)鍵路徑46. 從未排序序列中依次取出一個元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為排序法。A.插入 B.選擇 C.冒泡 D.都不是

13、47. 一個棧的入棧序列是 a,b,c,d,e,則棧的不可能的輸出序列是。A.edcbaB.decbaC.dceabD.abcde48. n 個節(jié)點(diǎn)的完全二叉樹，編號為 i 的節(jié)點(diǎn)是葉子結(jié)點(diǎn)的條件。A.inB.2*inD.2*in49. 向一個有 128 個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動個元素。A.64.5B.64C.63D.6550. 在一個單鏈表 HL 中，若要在指針 q 所指結(jié)點(diǎn)的后面插入一個由指針 p 所指向的結(jié)點(diǎn)，則執(zhí)行。A.q-next=p-next;p-next=q;B.p-next=q-next;q=p;C.p-next=p-next;q-next=

14、q;D.p-next=q-next;q-nxet=p;51. 對一個滿二叉樹，m 個樹葉，n 個結(jié)點(diǎn)，深度為 h,則有。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-152._ 在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是。A.選擇排序 B.冒泡排序 C.插入排序 D.希爾排序53. 用鏈?zhǔn)椒绞酱鎯Φ年犃?，在進(jìn)行插入運(yùn)算時，。A.僅修改頭指針 B.僅修改尾指針C.頭、尾指針都要修改 D.頭、尾指針可能都要修改54. 在一個長度為 n 的順序存儲的線性表中，向第 i 個元素（1WiWn+1）插入一個新元素時，需要從后向前依次后移個元素。A.n-iB.n-i-1C.n

15、-i+1D.i55._ 一個棧的入棧序列是 12345，則棧的不可能的輸出序列是。A.23415B.54132C.23145D.1543256._ 5 個頂點(diǎn)的有向圖最多有條弧。A.5B.20C.4D.2557.假定一個鏈隊的隊首和隊尾指針分別為front 和 rear，則判斷隊空的條件為。A.front=rearB.front!=NULLC.rear!=NULLD.front=NULL58. 若某線性表中最常用的操作是提取第 i 個元素及找第 i 個元素的前驅(qū)元素，則采用（）存儲方式最省時間。A.單鏈表 B.雙鏈表 C.單向循環(huán)鏈表 D.順序表59. 將含有 100 個結(jié)點(diǎn)的完全二叉樹從根開

16、始自上向下，每層從左到右依次編號，且設(shè)根結(jié)點(diǎn)的編號為 1，則編號 69 的結(jié)點(diǎn)的雙親的編號為（）。A.34B.35C.33D.無法確定560. 單循環(huán)鏈表的主要優(yōu)點(diǎn)是（）。A.不再需要頭指針了B. 已知某結(jié)點(diǎn)的位置后，很容易找到其前驅(qū)C. 在進(jìn)行插入、刪除運(yùn)算時，能更好地保證鏈表不斷開D. 從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個鏈表61. 一個棧的入棧順序是 1、2、3、4、5，則此棧不可能的輸出順序為（）。A.5、4、3、2、1B.4、5、3、2、1C.4、3、5、1、2D.1、2、3、4、562. 串是一種特殊的線性表，其特殊性表現(xiàn)在（）。A.可以順序存儲 B.數(shù)據(jù)元素是一個字符C 可以鏈?zhǔn)酱鎯?/p>

17、 D.數(shù)據(jù)元素是多個字符63. n 個頂點(diǎn)的無向圖中最多有（）條邊。A.n（n-1）/2B.n（n-1）C.n（n+1）D.n（n+1）/264. 6 個頂點(diǎn)的無向圖中，至少有（）條邊才能保證是一個連通圖。A.5B.6C.7D.865若某線性表中最常用的操作是刪除第 1 個元素，則不宜采用（）存儲方式。A.單鏈表 B.雙鏈表 C.單向循環(huán)鏈表 D.順序表66. 在一棵完全二叉樹的順序存儲方式中，若編號 i 的結(jié)點(diǎn)有右孩子，則其右孩子的編號為（）。A.2iB.2i-1C.2i+1D.i/267. 按照二叉樹的定義，具有 3 個結(jié)點(diǎn)的二叉樹有（）種不同形態(tài)。A.3B.4C.5D.668. 在長為

18、n 的順序表中，刪除第 i 個元素（lWiWn+1）需要向前移動（）個元素。A.n-iB.n-i+1C.n-i-1D.i69. 一個隊的入隊順序是 1、2、3、4、5，則此隊的出隊順序為（）。A.5、4、3、2、1B.4、5、3、2、1C.4、3、5、1、2D.1、2、3、4、570. 棧是一種特殊的線性表，其特殊性表現(xiàn)在（）。A.可以順序存儲 B.只能從端點(diǎn)進(jìn)行插入和刪除C.可以鏈?zhǔn)酱鎯?D.可以在任何位置進(jìn)行插入和刪除71. 一棵二叉樹中，第 k 層上最多有（）個結(jié)點(diǎn)。A.2kB.2k-1C.2kD.2k-172. 一棵有 18 個結(jié)點(diǎn)的二叉樹，其高度最小為（）層。A.4B.5C.6D.1

19、873. 有向圖中，所有頂點(diǎn)入度和是所有頂點(diǎn)出度和的（）倍。A.0.5B.1C.2D.4（二）填空題1.數(shù)據(jù)元素之間存在的相互關(guān)系稱為。2. 數(shù)據(jù)結(jié)構(gòu)從邏輯上分為結(jié)構(gòu)和結(jié)構(gòu)。3. 線性表的順序存儲結(jié)構(gòu)稱為。4. 所有插入在表的一端進(jìn)行，而所有刪除在表的另一端進(jìn)行的線性表稱。5. 深度為 h 的二叉樹,最少有個結(jié)點(diǎn)。6. 折半查找要求待查表為表。7. n 個記錄按其關(guān)鍵字大小遞增或遞減的次序排列起來的過程稱。6&存儲數(shù)據(jù)時，不僅要存儲數(shù)據(jù)元素的,還要存儲元素之間的相互。9將一棵有 100 個結(jié)點(diǎn)的完全二叉樹按層編號，則編號為 49 的結(jié)點(diǎn) X,其雙親 PARENT(X)的編號為。10、一

20、個字符串相等的充要條件和。11、在有向圖的鄰接表和逆鄰接表表示中，每個頂點(diǎn)的邊鏈表中分別鏈接著該頂點(diǎn)的所有和結(jié)點(diǎn)。11、在一個長度為 n 的順序表中向第 i 個元素(0iWn+1)之前插入一個新元素時，需要向后移動個元素。12、是只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。13、設(shè)主串 T=“abxxyxyxxbaa”，模式串 P=“xyxx”則第次匹配成功。14、在一棵二叉樹中，第 5 層上的結(jié)點(diǎn)數(shù)最多為。(根的層次為 1)15、假設(shè)一個 9 階的上三角矩陣 A 按列優(yōu)先順序壓縮存儲在一維數(shù)組中，其中 B0存儲矩陣中第 1 個元素 a1,1，則 B31中存放的元素。16、有 n 個

21、結(jié)點(diǎn)的二叉鏈表中，其中空的指針域為 n+1，指向孩子的指針個數(shù)為。17、二叉樹后序遍歷的順序是 ABCDE，則該二叉樹的根結(jié)點(diǎn)是。18、對于一個具有 n 個頂點(diǎn)和 e 條邊的無向圖，若采用鄰接表表示，則整個鄰接表中的結(jié)點(diǎn)總數(shù)是。19、在單鏈表上難以實現(xiàn)的排序方法有和。20、查找法的平均查找長度與元素個數(shù) n 無關(guān)。21、在有 n 個元素的順序表的任意位置插入一個元素所需移動結(jié)點(diǎn)的平均次數(shù)為22、是插入和刪除元素都在表的同一端進(jìn)行的線性表。23、廣義表 L=(a,b,c,L),則其長度為。24、在樹中，除跟結(jié)點(diǎn)外，其他結(jié)點(diǎn)都有且只有一個結(jié)點(diǎn)。26、在串 s=“strueture”中，以 t 為首

22、字符的子串有個。27、廣度優(yōu)先搜索遍歷類似于樹的遍歷的過程。28、已知一棵完全二叉樹中共有 768 個結(jié)點(diǎn)為，則該樹中共有個葉子結(jié)點(diǎn)。29、在有序表(12,24,36,48,60,72,84)中二分查找關(guān)鍵字 72 時所需進(jìn)行的關(guān)鍵字比較次數(shù)為。30、兩個長度分別 m 和 n(mn)的排好序的表歸并成一個排好序的表，至少要進(jìn)行次鍵值比較。通常從四個方面評價算法的質(zhì)量:、和。31、一個算法的時間復(fù)雜度為(n3+n2logn+14n)/n2，其數(shù)量級表示為。32、若用鏈表存儲一棵二叉樹時，每個結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，n 個結(jié)點(diǎn)的二叉樹共有個指針域，其中有

23、個指針域是存放了地址，有個指針是空指針。33、對于一個具有 n 個頂點(diǎn)和 e 條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有個和個。34、在一個具有 n 個頂點(diǎn)的無向完全圖中，包含有條邊，在一個具有 n 個頂點(diǎn)的有向完全圖中，包含有條邊。35、36.在快速排序、堆排序、歸并排序中，排序是穩(wěn)定的。36、37.中序遍歷二叉排序樹所得到的序列是序列。38. 快速排序的最壞時間復(fù)雜度為，平均時間復(fù)雜度為。739. 設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為。40數(shù)據(jù)的物理結(jié)構(gòu)主要包括和兩種情況。841._設(shè)一棵完全二叉樹中有 5

24、00 個結(jié)點(diǎn)，則該二叉樹的深度為；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有個空指針域。42、設(shè)輸入序列為 1、2、3，則經(jīng)過棧的作用后可以得到種不同的輸出序列。43、設(shè)有向圖 G 用鄰接矩陣 Ann作為存儲結(jié)構(gòu)，則該鄰接矩陣中第 i 行上所有元素之和等于頂點(diǎn) i 的，第 i 列上所有元素之和等于頂點(diǎn) i 的。設(shè)哈夫曼樹中共有 n 個結(jié)點(diǎn),則該哈夫曼樹中有個度數(shù)為 1 的結(jié)點(diǎn)。設(shè)有向圖 G 中有 n 個頂點(diǎn) e 條有向邊，所有的頂點(diǎn)入度數(shù)之和為 d,則 e 和 d 的關(guān)系為遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個遞增的關(guān)鍵字序列(填先序、中序或后序)。設(shè)查找表中有 100 個元素，如果用二分法查

25、找方法查找數(shù)據(jù)元素 X,則最多需要比較次就可以斷定數(shù)據(jù)元素 X 是否在查找表中。不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，其入棧和出棧操作的時間復(fù)雜度均為設(shè)有 n 個結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從 1 開始順序編號，貝y 第 i 個結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為，右孩子結(jié)點(diǎn)的編號為。設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字 72 為基準(zhǔn)的一趟快速排序結(jié)果為。設(shè)有向圖 G 中有向邊的集合 E=1,2，2，3，1，4，4，2，4，3，則該圖的一種拓?fù)湫蛄袨?。下列算法實現(xiàn)在順序散列表中查找值為 x 的關(guān)鍵字，請在下劃線處填上正確的語句。structr

26、ecordintkey;intothers;inthashsqsearch(structrecordhashtable,intk)inti,j;j=i=k%p;while(hashtablej.key!=k&hashtablej.flag!=0)j=()%m;if(i=j)return(-1);if()return(j);elsereturn(-1);j+1，hashtablej.key=k下列算法實現(xiàn)在二叉排序樹上查找關(guān)鍵值 k 請在下劃線處填上正確的語句。typedefstructnodeintkey;structnode*lchild;structnode*rchild;bitr

27、ee;bitree*bstsearch(bitree*t,intk)if(t=0)return(0);elsewhile(t!=0)if(t-key=k);elseif(t-keyk)t=t-lchild;else;return(t)，t=t-rchild設(shè)有 n 個無序的記錄關(guān)鍵字，則直接插入排序的時間復(fù)雜度為，快速排序的平均時間復(fù)雜度為。設(shè)指針變量 p 指向雙向循環(huán)鏈表中的結(jié)點(diǎn) X,則刪除結(jié)點(diǎn) X 需要執(zhí)行的語句序列為(設(shè)結(jié)點(diǎn)中的兩個指針域44、45464748495051525354、9分別為 llink 和 rlink)。根據(jù)初始關(guān)鍵字序列(19,22,01,38,10)建立的二叉排序樹的高度為 3。55、深度為 k 的完全二叉樹中最少有 2k-1 個結(jié)點(diǎn)。56、設(shè)初始記錄關(guān)鍵字序列為(K,K,，K),則用篩選法思想建堆必須從第_n/2_個元12n素開始進(jìn)行篩選。59、設(shè)哈夫曼樹中共有 99 個結(jié)點(diǎn),則該樹中有個葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲結(jié)構(gòu),則該樹中有個空指針域。60、設(shè)有一個順序循環(huán)隊列中有 M 個存儲單