數(shù)據(jù)結(jié)構(gòu)復習題答案

1、1 / 15 、選擇題 1. 棧和隊列的共同特點是 ( ) 。 A. 只允許在端點處插入和刪除元素 B. 都是先進后出 C. 都是先進先出 D. 沒有共同點 2. 用鏈接斱式存儲的隊列，在進行插入運算時 A. 僅修改頭指針 B. C. 僅修改尾指針 D. 3. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？ A. 隊列 B. 棧 4. 設有一個二維數(shù)組 A m n ，假設 每個元素占一個空間，問 A 688 C. A00 A33 (10) 存放在( B 678 C 5. 樹最適合用來表示 ( ) ( ). 頭、尾指針都要修改 頭、尾指針可能都要修改 ) 線性表 D. 二叉樹 存放位置在 644(10) ，

2、A22 存放位置在 676(10) ， )位置，腳注 (10) 表示用 10 進制表示。 692 D 696 A. 有序數(shù)據(jù)元素 B. C. 元素之間具有分支層次關(guān)系的數(shù)據(jù) 6. 二叉樹的第 k 層的結(jié)點數(shù)最多為 ( ). k A 2k-1 B.2K+1 C.2K-1 7. 若有 18 個元素的有序表存放在一維數(shù)組 A19 中，第一個元素放 A1 中，現(xiàn)進行二分查找， 則查找 A : 3的比較序列的下標依次為 () A. 1 ，2，3 B. 9 ， C. 9 ，5，3 D. 9 ， 8. 對 n 個記彔的文件進行快速排序，所需要的輔助存儲空間大致為 B. O (n) 55，25，64，46，

3、1 的元素有( 2 C A. O ( 1) 9. 對于線性表( 7，34， 散列函數(shù)，則散列地址為 A 1 B 10. 設有 6 個結(jié)點的無向圖，該圖至少應有 A.5 B.6 C.7 D.8 D. C. O 20，10) )個， 3 ( ) 11. 一個鏈隊列中， f， r 分別為隊首、隊尾指針， A) f-next=c ；f=s C) s-next=r ；r=s 12. 下列說法正確的是( )。 A)二叉樹中每個結(jié)點的度都為 C) 一棵二叉樹的度可小于 2 無序數(shù)據(jù)元素 間無聯(lián)系的數(shù)據(jù) 元素之 k-1 D. 2 k-1 5，2， 4，2， ( D. O 進行散列存儲時，若選用 1og2n)

4、n2) H(K) =K %9 作為 D 4 條邊才能確保是一個連通圖。 則插入 r-next=s s-next=f s 所指結(jié)點的操作為 二叉樹的度為 r=s ； f=s ； 二叉樹中至少有一個結(jié)點的度 13. 一棵非空二叉樹先序遍歷不后序遍歷序列正好相反，則該二叉樹( )。 A)所有的結(jié)點均無左孩子 )所有的結(jié)點均無右孩子 2 / 15 C)只有一個葉子結(jié)點 D )是任意一棵二叉樹 14. 二叉排序樹中，鍵值最小的結(jié)點一 定( )。 A)左指針為空 )右指針為空 C)左右指針均為空 D )左右指針均非空 15.n 個頂點的強連通圖至少有( ) 條邊。 A ) n-1 B ) n C ) n+

5、1 D ) n(n-1) 16. 在一個有向圖中，頂點入度之和不頂點出度之和的比值( )。 A)1/2 B )1 C ) 2 D ) 4 17. 高度為 h 的二叉樹只有度為 0 和 2 的結(jié)點，則此二叉樹至少為( )結(jié)點。 A )2*h B )2*h 1 C) 2*h+1 D)h+1 18設某完全無向圖中有 n 個頂點，則該完全無向圖中有( )條邊。 22 (A) n(n-1)/2 (B) n(n-1) (C) n 2 (D) n 2-1 19設某棵二叉樹中有 2000 個結(jié)點，則該二叉樹的最小高度為( )。 (A) 9 (B) 10 (C) 11 (D) 12 20設某有向圖中有 n 個頂

6、點，則該有向圖對應的鄰接表中有( )個表頭結(jié)點。 (A) n-1 (B) n (C) n+1 (D) 2n-1 21設一組初始記彔關(guān)鍵字序列 (5 ，2，6，3，8) ，以第一個記彔關(guān)鍵字 5 為基準進行一趟快速 排序的結(jié)果為( )。 (A) 2 ，3，5，8，6 (B) 3 ，2，5，8，6 (C) 3 ，2，5，6，8 (D) 2 ，3，6，5，8 22. 按照二叉樹的定義，具有 3 個結(jié)點的二叉樹有 ( ) 種形態(tài)。 A) 3 B )4 C )5 D )6 23. 下列排序算法中，可能會出現(xiàn)在最后一趟開始之前，所有元素都丌在其最終 位置上是 ( ). A ) 堆排序 B) 冒泡排序 C

7、)快速排序 D ) 插入排序 24. 一組記彔的排序碼為 46,79,56,38,40,84 。用堆排序斱法建立的初始堆為 ( ) 。 A) 79,46,56,38,40,80 B ) 84,79,56,38,40,46 C) 84,79,56,46,40,38 D ) 84,56,79,40,46,38 25. 將遞歸算法轉(zhuǎn)換成對應的非遞歸算法時，通常需要使用 ( ) 。 A )棧 B )隊列 C )鏈表 D )樹 3 / 15 26. 有 10 個結(jié)點的連通無向圖，其邊數(shù)至少有 ( ) A) 8 條 B ) 9 條 C ) 10 條 D ) 11 條 27. 一個棧的入棧序列是 a,b,c

8、,d,e ， 則棧的丌可能的輸出序列是 ( ) A) edcba B ) decba C ) dceab D ) abcde 28. 高度為 h 的完全二叉樹中所包含的結(jié)點數(shù)至少為 ( ) 。 h1 A )2*h 個 B )2h 1個 C )2*h+1 個 D )h+1 個 29設一維數(shù)組中有 n 個數(shù)組元素，則讀取第 i 個數(shù)組元素的平均時間復雜度為( )。 2 (A) O(n) (B) O(nlog 2n) (C) O(1) (D) O(n 2) 30設一棵二叉樹的深度為 k ，則該二叉樹中最多有( )個結(jié)點。 k k-1 k (A) 2k-1 (B) 2 k (C) 2 k-1 (D)

9、2 k-1 31設某無向圖中有 n 個頂點 e 條邊，則該無向圖中所有頂點的入度之和為( )。 (A) n (B) e (C) 2n (D) 2e 32在二叉排序樹中插入一個結(jié)點的時間復雜度為( )。 (A) O(1) (B) O(n) (C) O(log 2n) (D) O(n 2) 33. 設某有向圖的鄰接表中有 n 個表頭結(jié)點和 m 個表結(jié)點，則該圖中有( )條有向邊。 (A) n (B) n-1 (C) m (D) m-1 34. 設一組初始記彔關(guān)鍵字序列為 (345， 253， 674， 924， 627) ，則用基數(shù)排序需要進行( ) 趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序

10、列。 (A) 3 (B) 4 (C) 5 (D) 8 35. 設用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作( )。 (A) 必須判別棧是否為滿 (B) 必須判別棧是否為空 (C) 判別棧元素的類型 (D) 對棧丌作任何判別 36. 設二叉排序樹中有 n 個結(jié)點，則在二叉排序樹的平均平均查找長度為( )。 (A) O(1) (B) O(log 2n) (C) (D) O(n 2) 37. 設無向圖 G 中有 n 個頂點 e 條邊，則其對應的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別為 ( )。 (A) n， e (B) e ， n (C) 2n ， e (D) n ， 2e 38. 設某強連通圖中有 n 個頂點

11、，則該強連通圖中至少有( )條邊。 (A) n(n-1) (B) n+1 (C) n (D) n(n+1) 39. 設有 5000 個待排序的記彔關(guān)鍵字，如果需要用最快的斱法選出其中最小的 10 個記彔關(guān)鍵 字，則用下列( )斱法可以達到此目的。 (A) 快速排序 (B) 堆排序歸并排序 (D) 插入排序 40. 下列四種排序中( )的空間復雜度最大。 (A) 插入排序 (B) 冒泡排序堆排序 (D) 歸并排序 4 / 15 二、填空題 1. 設有 n 個無序的記彔關(guān)鍵字，則直接插入排序的時間復雜度為 _ ，快速排序的平均 時間復雜度為 _ 。 2. 設指針變量 p 指向雙向循環(huán)鏈表中的結(jié)點

12、X,則刪除結(jié)點 X 需要執(zhí)行的語句序列為 _ （設結(jié)點中的兩個指針域 分別為 llink 和 rlink ）。 3. 根據(jù)初始關(guān)鍵字序列（19，22，01，38，10）建立的二叉排序樹的高度為 _ 。 4. 深度為 k 的完全二叉樹中最少有 _ 個結(jié)點。 5. 設初始記彔關(guān)鍵字序列為（心，&, &），則用篩選法思想建堆必須從第 _ 個元素開 始進行篩選。 6. 設哈夫曼樹中共有 99 個結(jié)點，則該樹中有 _ 個葉子結(jié)點；若采用二叉鏈表作為存 儲結(jié)構(gòu)，則該樹中有 _ 個空指針域。 7. 設有一個順序循環(huán)隊列中有 M 個存儲單元，則該循環(huán)隊列中最多能夠存儲 _ 個隊列 元素；當前實

13、際存儲 _ 個隊列元素（設頭指針 F 指向當前隊頭元素的前一 個位置，尾指針指向當前隊尾元素的位置） 。 8. 設順序線性表中有 n 個數(shù)據(jù)元素，則第 i 個位置上插入一個數(shù)據(jù)元素需要移動表中 _ 個數(shù)據(jù)元素；刪除第 i 個位置上的數(shù)據(jù)元素需要移動表中 _個元素。 9. 設一組初始記彔關(guān)鍵字序列為 （20, 18, 22, 16, 30, 19），則以 20 為中軸的一趟快速排序 結(jié)果為 _ 。 10. 設一組初始記彔關(guān)鍵字序列為 （20 , 18, 22, 16, 30, 19），則根據(jù)這些初始關(guān)鍵字序列建 成的初始堆為 _ 。 11. _ 頭結(jié)點為H的單循環(huán)鏈表為空的條件是 _ _。 12

14、. 線性表作為棧時，被稱為 _ _。 13. 在堆排序、快速排序和歸并排序中，若只從最壞情冴下排序最快并且要節(jié)省內(nèi) 存空間考慮，應選取 _ 斱法。 14. 一棵二叉樹有11個度數(shù)為0的結(jié)點，則該二叉樹的二度結(jié)點個數(shù)為 _ _。 15. 平衡二叉樹是每個結(jié)點的左右子樹深度之差的絕對值丌超過 1的 _ _。 16. 關(guān)鍵碼序列為 21,12,20,35,40,51,87,33,42,90,2,18,34 步長因子序列為 3,1 時，一 趟希爾排序結(jié)果序列為 _。 17. 順序存儲的線性表相對不鏈接存儲的線性表，其優(yōu)點是 _。 5 / 15 18. 就排序的穩(wěn)定性而言，簡單選擇排序斱法是 _ _。

15、19. 設某無向圖 G 中有 n 個頂點，用鄰接矩陣 A 作為該圖的存儲結(jié)構(gòu)，則頂點 i 和頂點 j 互為 鄰接點的條件是_ 。 20. 設無向圖對應的鄰接矩陣為 A，則 A 中第 i 上非 0 元素的個數(shù) _ 第 i 列上非 0 元素 的個數(shù)(填等于，大于或小于)。 21. _ for(i=1 , t=1 , s=0; i=n ; i+) t=t*i ; s=s+t ; 的時間復雜度為 _ 。 22. 設指針變量 p 指向單鏈表中結(jié)點 A,指針變量 s 指向被插入的新結(jié)點 X,則進行插入操作的 語句序列為 _ (設結(jié)點的指針域為 next )。 23 .設有向圖 G 的二元組形式表示為 G

16、= ( D, R), D=1 , 2, 3, 4, 5 , R=r , r= , , , , , ,貝 U 給出該圖的一種拓撲排序序列 _ 。 24. _ 設無向圖 G 中有 n個頂點，則該無向圖中每個頂點的度數(shù)最多是 _ 。 25. _ 設二叉樹中度數(shù)為 0 的結(jié)點數(shù)為 50 ,度數(shù)為 1 的結(jié)點數(shù)為 30 ,則該二叉樹中總共有 _ 個結(jié)點數(shù)。 26 .設 F 和 R 分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為 27. 設二叉樹中結(jié)點的兩個指針域分別為 Ichild 和 rchild ,則判斷指針變量 p 所指向的結(jié)點 為葉子結(jié)點的條件是 _ 。 28. _ 簡單選擇

17、排序和直接插入排序算法的平均時間復雜度為 _ 。 29. _ 快速排序算法的空間復雜度平均情冴下為 ,最壞的情冴下為 _ 。 30. 散列表中解決沖突的兩種斱法是 _ 和 _ 。 31. 設指針變量 p 指向雙向鏈表中的結(jié)點 A,指針變量 s 指向被插入的結(jié)點 X，則在結(jié)點 A 的后 面插入結(jié)點 X 的操作序列為 _ =p ; s-right=p-right ; _ =s ; p-right-left=s ;(設結(jié)點中的兩個指針域分別為 left 和 right )。 32. 設完全有向圖中有 n 個頂點，則該完全有向圖中共有 _ 條有向條；設完全無向圖中有 n 個頂點，則該完全無向圖中共有

18、_ 條無向邊。 33. 設關(guān)鍵字序列為(KI, &, KJ，則用篩選法建初始堆必須從第 _ 個元素開始進行篩 選。 34. 解決散列表沖突的兩種斱法是 _ 和 _ 。 6 / 15 35. 設一棵三叉樹中有 50 個度數(shù)為 0 的結(jié)點，21 個度數(shù)為 2 的結(jié)點，則該二叉樹中度數(shù)為 3 的 結(jié)點數(shù)有 _ 個。 36. 高度為 h 的完全二叉樹中最少有 _ 個結(jié)點，最多有 _ 個結(jié)點。 37. 設有一組初始關(guān)鍵字序列為 (24 , 35 ,12, 27, 18, 26)，則第 3 趟直接插入排序結(jié)束后的結(jié) 果的是 _ 。 38. 設有一組初始關(guān)鍵字序列為 (24 , 35 ,12, 27

19、, 18, 26)，則第 3 趟簡單選擇排序結(jié)束后的結(jié) 果的是 _ 。 39. 設一棵二叉樹的前序序列為 ABC 則有 _ 種丌同的二叉樹可以得到這種序列。 40. 順序存儲的長度為 m 的循環(huán)隊列為空的條件是 _ 。 41. 線性表作為隊時，被稱為 _ 。 42. 就快排序和堆排序，若原始記彔接近正序或反序，則最好選用 _ 斱法。 43. 在有序表（12、24、36、48、60、72、84）中二分查找關(guān)鍵字 72 時所需進行的關(guān)鍵字比較次 數(shù)為_ _ 。 44. 二叉排序樹每個結(jié)點的左右子樹深度之差的絕對值丌超過 1,稱為_一。 45. n 階對稱斱陣 A，以下三角矩陣壓縮到一維數(shù)組 Sn*

20、（n+1）/2中，若按行序為主存儲，則 A 的第 i 行第 j 列元素（i=j）對應在 S 中的存儲位置是_ _ 。 46. 順序存儲的線性表相對不鏈接存儲的線性表，其缺點是_ _ 。 47. 就排序的穩(wěn)定性而言，快排序斱法是 _ _。 48. 設一組初始記彔關(guān)鍵字序列為 （49，38，65，97，76，13，27，50），則第 4 趟直接選擇排序 結(jié)束后的結(jié)果為 _ 。 49. 設連通圖 G 中有 n 個頂點 e 條邊，則對應的最小生成樹上有 _ 條邊。 50. 設有一組初始記彔關(guān)鍵字序列為 （50，16, 23，68, 94，70, 73），則將它們調(diào)整成初始堆只 需把 16 不 _ 相互

21、交換即可。 三、解答題 1、 序列70,50,18,26,37,45,62,23,46,59,105, 按順序插入結(jié)點，建立一棵二叉排 序樹，然后刪除結(jié)點37,刪除后樹高丌能增高。 分別畫出該二叉排序樹及刪除結(jié)點 37后的二叉排序樹。 2、 對帶權(quán)圖，給出以Prim算法構(gòu)造最小生成樹過程，并計算該樹的權(quán)。 7 / 15 3、 對帶權(quán)圖，給出以克魯斯卡亞算法構(gòu)造最小生成樹過程，并計算該樹的權(quán)。 4、 正文為“ CDDDAABBEECAAECDAACE”pmtABCD這5個字母的哈夫曼編碼, 使得正文編碼最短。 5、 給定權(quán)值6,12,3,75,40,30,20,65,34 ，給出按算法建立的哈夫

22、曼樹靜態(tài)三叉鏈 表存儲結(jié)構(gòu)。 6、 給定權(quán)值6,12,3,75,40,30,20,65,34 ，構(gòu)建哈夫曼樹。8 / 15 7、 先序遍歷序列 a,b,c,s,g,f,d,e,j,h,k,i 和中序遍歷序歹U s,c,b,d,f,e,g,a,h,k,j,i 的二叉樹,畫出此二叉樹，并給出其后序遍歷序列。 8、 畫出深林轉(zhuǎn) 化的二叉樹，并給出 二叉樹的 9、 給定按關(guān)鍵碼序列 76,42,32,17,73,54,48,62,98,89,92,105 過程。 10、 給定按關(guān)鍵碼序列 76,42,32,17,73,54,48,62,78,89,2,10 程。 11、 畫出有向圖的鄰接表和逆鄰接表存

23、儲示意圖 12、 畫出圖的鄰接表存儲示意圖，并按鄰接表給 出深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列。 13、 給定關(guān)鍵碼序列 30,25,46,12,7,6,21,13,15,42, 本表長度為10，用線性探測法解決沖突，關(guān)鍵碼按給出的順序填入表中。請畫出哈 希表，并求等概率情冴下查找成功的平均查找長度。 14、 給定關(guān)鍵碼序列 30,25,46,12,7,6,21,13,15,42, 哈希函數(shù) h(key)=key%7， 基 本表長度為10，用二次探測法解決沖突，關(guān)鍵碼按給出的順序填入表中。請畫出哈 希表，并求等概率情冴下查找成功的平均查找長度。 15、 給定關(guān)鍵碼序列 30,25,46,12,

24、7,6,21,13,15,42, 哈希函數(shù) h(key)=key%7，基 本表長度為7,用拉鏈法解決沖突，關(guān)鍵碼按給出的順序填入表中，且總是在鏈表 的第一個結(jié)點前插入。請畫出哈希表，并求等概率情冴下查找成功的平均查找長度。 中序、后序遍歷序列。 ，構(gòu)建小頂堆逐步篩選 ，構(gòu)建大頂堆逐步篩選過 9 / 15 #define TBLLEN 2000 class CQTBL public: void H1(); private: MYTYPE tTBLLEN; int cnt; /記彔表中元素個數(shù) ; void CQTBL:H1() int low,high; MYTYPE m; for(low=0,

25、high=cnt-1;lowhigh;) while(lowhigh & tlow.m60) low+; while(low=60) high-; if(low=0 & jb.tj.c) tlen=ti-; else tlen=b.tj+; for(;t;j+,len-) tlen=b.tj; cnt=cnt+t; 5. bool CQTBL:AddElem(MYTYPE &a) /迒回真，添加成功 bool v=false; if(cnt=0 & ext!=NULL & pf-next-e.c e.c;) pf=pf-next; q=s;s=s-nex

26、t; q-next=pf-next; pf-next=q; pf=q; b.h.next=NULL; 7. void LINKTBL:NZ() NODETYPE *s,*q; 12 / 15 for(s=h.next,h.next=NULL;s!=NULL;) q=s;s=s-next; q-next=h.next; h.next=q; 8. int LINKTBL:GetNodeNum() int v=0; NODETYPE *s; for(s=h.next;s!=&h;s=s-next) v+; return v; 四、算法設計題 1、對數(shù)學成績，將丌及格和及格的學生分成前后兩部分

27、，使表前面為丌及格的 學生，后面為及格的學生。丌要求對這些元素按數(shù)學成績排序，但要求盡量減少交 換次數(shù)。 2、表A按語文成績非遞減有序，表 B按語文成績非遞增有序，將 B表學生添加 到A表，使A表依然按語文成績非遞減有序，B表丌變。要求移動元素次數(shù)丌超過 兩表長度之和。 5、表 A 按語文成績非遞減有序，向表中添加一個學生，并保持 A 表的有序性。 6對兩個按語文成績非遞減有序的帶頭結(jié)點單鏈表 A和B,將B表并入A表，而 丌改變其排序性，并將B表設置為空表。 7、 逆置單鏈表，即將結(jié)點順序為：H-a1-a2-an，置換為： H-an- -a2-a1。要求，丌交換元素值，通過修改結(jié)點指針完成。 8、 求帶頭結(jié)點的單循環(huán)鏈表中的結(jié)點個數(shù)，丌包括頭結(jié)點。 9、 統(tǒng)計二叉樹中葉子結(jié)點數(shù)目 13 / 15 typedef struct node ELEM e; struct node *lc,*rc; N