數(shù)據(jù)結構習題

1、單項選擇題 1. 下面程序段的時間復雜度為 ( C ) 。 for(int i=0; im; i+) for(int j=0; jnext=headDhead!=NULL 8. 設一個鏈表最常用的操作是在末尾插入結點和刪除尾結點，則選用 ( C )最節(jié)省時間。 A)單鏈表B)循環(huán)鏈單表 C)帶尾指針的循環(huán)鏈單表D)帶頭結點的 雙循環(huán)鏈表 棧的插入與刪除操作在（ A ）進行。 A. 棧頂B.棧底 C任意位置D.指定位置 設一個棧的輸入序列為 A、B、C D,則借助一個棧所能得到的輸出序 列不可能是（ D ）。 AABCDB DCBAC ACDBD DABC 在一個鏈隊中，假設 F 和 R 分別是

2、隊首和隊尾指針，則刪除一個結點 的運算是 （ C ） 。 A R=F-next;B R=R-next; C F=F-next; D F=R-next; 串是一種特殊的線性表，其特殊性體現(xiàn)在 （ B ）。 A .可以順序存儲 C.可以鏈接存儲 以下說法正確的是（ C ）。 A）空串與空格串是相同的 C）空串是零個字符組成的串 B. 數(shù)據(jù)元素是一個字符 D.數(shù)據(jù)元素可以是多個字符 B） fox”是FoxBasd的子串 D）空串長度等于1 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 若 n 為主串長， m 為子串長 mn） ，則用簡單模式匹配算法最壞

3、情況 下，需要比較字符總數(shù)是（ C ）。 Am B m(n-m+1)C n*m D (n-m)*(m-1) 將一個 A1.100,1.100的三對角矩陣， 按行優(yōu)先存入一維數(shù)組B1.298 中，A中元素 A66, 65在B數(shù)組中的位置 k為（B ）。 A） 198B） 195C） 197 一個稀疏矩陣的轉(zhuǎn)置矩陣應是（ B ）。 A. 下三角矩陣B.稀疏矩陣C.非稀疏矩陣 D.有時為稀疏矩陣 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 廣義表(e)的表頭是(C )。 A )e B) ( ) C) (e) D) (e) 深

4、度為 5 的二叉樹至多有 ( C )個結點。 A16B 32 具有 10 個葉子結點的二叉樹中有( A 8B9 在二叉樹的中序遍歷遞歸算法中， 時作訪問操作。 A1B2C 3 C 31D 10 B)個度為2的結點。 C 10D 11 順著搜索路徑， 在第( B )次經(jīng)過結點 D4 在中序線索二叉樹中，若某結點有右孩子，則該結點的直接后繼是 A 左子樹的最右下結點 B 右子樹的最右下結點 C 左子樹的最左下結點 D 右子樹的最左下結點 按照二叉樹的定義，具有 3 個結點的二叉樹有 ( C )種形態(tài)。 A3 B4 C5 D6 某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是(B)的 二叉樹。

5、 A .空或只有一個結點 C. 任一結點無左孩子 圖的廣度優(yōu)先搜索類似于樹的 A.先根B.中根 B. 高度等于其結點數(shù) D. 任一結點無右孩子 ( D )次序遍歷。 C. 后根D.層次 An-l 條有向邊 B n 條有向邊 C. n(n-1)/2條有向邊D. n(n-1)條有向邊 36. 任何一個無向連通圖的最小生成樹(B)。 37. A.只有一棵B.有一棵或多棵C. 一定有多棵D.可能不存在 38. 設 G1=(V1,E1)和G2=(V2,E2)為兩個圖，如果 V2包含 V1, E2包含 E1, 則稱 ( A )。 39. A. G1 是 G2 的子圖B. G1 是 G2 的連通分量 40.

6、 C. G2 是 G1 的連通分量D. G2 是 G1 的子圖 41. 下面關于圖的存儲的敘述中，哪一個是正確的。 ( A ) 42. A 用鄰接矩陣法存儲圖，占用的存儲空間數(shù)只與圖中結點個數(shù)有關，與 邊數(shù)無關 43. B.用鄰接矩陣法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關，與結點 個數(shù)無關 44. C.用鄰接表存儲圖，占用的存儲空間數(shù)只與圖中結點個數(shù)有關，與邊 數(shù)無關 45. D.用鄰接表存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關，與結點個 數(shù)無關 46. ( D )適合用鄰接表表示。 47. A.稠密圖B.有向完全圖 48. C.無向完全圖D.稀疏圖 49. 一般，圖的DFS生成樹的高度(

7、C )BFS生成樹的高度。 50. A.小于B.等于C.大于D.小于或等于 51. 從一棵二叉排序樹中查找一個元素時，其平均時間復雜度為(C )。 A. 0(1)B. 0(n)C. O(1og2n)D. 0(n2) 52. 二分查找法要求查找表中各元素的鍵值必須是(A )排列。 53. A.遞增或遞減 B.遞增C.遞減D.無序 54. 向具有n個結點的、結構均衡的二叉排序樹中插入一個元素的時間復 雜度為(B )。 A. 0(1)B. O(log2n)C. 0(n)D. 0(nlog2n) 55. 線性表必須是(D ),才能進行二分查找。 56. A.用向量存儲的線性表B.用鏈表存儲的有序表 5

8、7. C.用鏈表存儲的線性表D.用向量存儲的有序表 58. 按照不同的順序輸入 4, 5, 6三個關鍵字，能建立(B )棵不同的二 叉排序樹。 A) 6B) 5C) 4D) 3 59. 在一棵m階B揺中，若在某結點中插入一個新關鍵字而引起該結點的 分裂，則該結點中原有( D )個關鍵字。 A)m/2B)m/2- 1C) mD)m-1E)m/2F)m/2 -1 60. 設有5000個無序的元素，希望用最快的速度挑選出其中前50個最大 的元素，最好選用(C )法。 61. A.冒泡排序 B快速排序 62. C.堆排序 D.基數(shù)排序 63. 下列序列中(B )是執(zhí)行第 趟快速排序后得到的序列 (排序

9、的關鍵字類 型是字符串） 64. A. da,ax,eb,de,bbffba,gc B. cd,eb,ax,da,bbffha,gc 65. C. gc,ax,cb,cd,bbffda,ba D. ax,bb,cd,daffeb,gc,ba 66. 在一個具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時 間復雜度是（B ）。 67. A. 0(1)B.0(n)C. O(n2) D.O(log2n) 68. 以下排序方法中，穩(wěn)定的排序方法是 (B )。 69. A .直接插入排序和希爾排序 B. 直接插入排序和冒泡排序 70. C.希爾排序和快速排序 D. 冒泡排序和快速排序 71. 在快

10、速排序中，每次劃分選擇的基準元素為該區(qū)間的（D ）時，得到的兩 個子區(qū)間是均勻的。 72. A .最大值B.最小值 C.任意值D.中間值 73. 若從二叉樹的任一結點出發(fā)到根的路徑上所經(jīng)過的結點序列按關鍵字 有序，則該二叉樹是下列樹中的哪種（ C） A.二叉排序樹 B.哈夫曼樹C.堆。 二、填空題 1. 在一個長度為n的順序表中刪除第i個元素，要移動_n-i_個元素。 2. 在順序表中插入或刪除一個元素，需要平均移動表長的一半元 素，具體移動元素的個數(shù)與元素所在的位置有關。 3. 若線性表采用順序存儲結構存放，那么在長度為n的線性表中刪除第i （1 next = h 。 5. 一個隊列的入隊序

11、列是a、b、c、d，則隊列的輸出序列為abed。 6. 棧結構通常采用的兩種存儲結構是順序棧 和鏈棧。 7. 設棧S和隊列Q的初始狀態(tài)為空，元素a、b、c、d、e、f依次通過棧 S,個元素出棧后即進入隊列Q。若這6個元素出隊列的順序是b、d、 c、f、e、a，則棧S的容量至少應該是3。 8. 設有一個nxn勺對稱矩陣A,將其上三角部分按行存放在一個一維數(shù) 組B中，A00存放于B0中，那么第i行的對角元素 Aii存放于B 中(2n-i+1)*i / 2 處。 9. 設有5對角矩陣A = (aj)2o*2o，按特殊矩陣壓縮存儲的方式將其5條對 角線上的元素存于數(shù)組B0 : m中，計算元素A10,1

12、0的存儲位置 44。 10. 已知廣義表L= (a,( ),b),(e),利用取表頭和取表尾的操作分離出原子 e 的運算是GetHead(GetHead(GetHead(GetTail(GetTail(L)。 11. 設廣義表 B=( ) ,(a, (b, c), (e,f),(),表頭為 (),表尾為 (a, (b, c), (e,f), ( )_。 12. 在空串和空格串中，長度不為0的是_空格串_。 13. 有n個結點的二叉鏈表中，其中空的指針域為n+1.指向孩子的指針個 數(shù)為 _n-1_。 14. 中綴算術表達式5+6/(23-(6+15)*8所對應的后綴算術表達式為 5,6,23,6

13、,15,+,-,/,8, *,+。 15假定一棵二叉樹的結點個數(shù)為50 ,則它的最小深度為 _6,最大深 度為 _50_ o 16. 一棵樹的后根序列與其轉(zhuǎn)換的二叉樹的中 序列相同，先根序列 與其轉(zhuǎn)換的二叉樹的先序列相同。 17. 具有400個結點的完全二叉樹的深度為 9o 18. 一棵二叉樹有 67個結點，這些結點的度要么是0,要么是2。這棵二 叉樹中度為2的結點有_33_個。 19. 已知森林的先序訪問序列為ABCDEFGHIJKL中序訪問序列為 CBEFDGAJIKLH則該森林有_2_棵樹。 20. 當對字符集進行編碼時，字符集中任一字符的編碼都不是其他字符的 編碼的前綴，這種編碼稱二進

14、制前綴編碼o 21. 高度為h的二叉樹只有度為 0和2的結點，則此類二叉樹的結點數(shù)至 少為2h-1+1個結點，至多為2h-1 個結點。 22. 深度為k的完全二叉樹至少有 2k-1 個結點，至多有 2k-1 個結點。 23. 一個有30個結點的完全二叉樹有15 個葉子結點；有個度 為2的結點。 24. 高度為i(i 1)的完全二叉樹按自上而下，從左到右的次序給結點編號 (從1開始)，則可能的編號最小的葉子結點的編號為2k-2+1o 25. 設圖 G= (V, E), V= 1 , 2, 3, 4, E= , , , ，從頂點1出發(fā)，對圖G進行廣度優(yōu)先搜索的序列有 _2_種。 26. 有向圖G用

15、鄰接矩陣A仁n,1.n存儲，矩陣中元素值1代表有弧，0代 表無弧，其第i行的所有元素之和等于頂點i的_出度度。 27. 一個連通圖的生成樹是該圖的極小連通子圖。若這個連通圖有n 個頂點，則它的生成樹有 _n-1_ 條邊。 28. n個頂點的無向連通圖的鄰接矩陣中至少有2(n-1)個非零元素，至 多有_n(n-1)_個非零元素。 29. PRIM算法與圖的邊數(shù)無關，適合求解稠密圖的最小生成樹。 30. 一棵3階B-樹中每個結點最多有3 棵子樹，每個結點最多有2 個關鍵字。含有9個葉子結點的3階B擁至少有4個非葉結點， 至多有 7個非葉結點。 31. 從有序表(12，18，30，43，56, 78

16、，82，95)中依次二分查找 43和56 元素時，其查找長度分別為_1和_3_。 32. 向一棵二叉排序樹中插入一個元素時，若元素的值小于根結點的值， 則應把它插入到根結點的左 子樹上。 33. 分別采用堆排序、快速排序、插入排序和歸并排序算法對初始狀態(tài)遞 增序列按遞增順序排序，最省時間的是算法插入排序，最費時間 的是算法快速排序。 三、簡答及圖示說明題 1. 廣義表的基本概念，如A = (a,b),c,(d,e,f)，用GetGead和GetTail操作 取元素d 2. 根據(jù)給定二叉樹的先序和中序序列，構造二叉樹 3. 根據(jù)給定樹的先序和后序序列，構造樹 4. 已知二叉樹，畫出中序的線索。

17、5. 森林和二叉樹的相互轉(zhuǎn)換 6. 有7個帶權結點，其權值分別為3，乙8，2，6，10，14,試以它們 為葉子結點生成一棵哈夫曼樹，畫出相應的哈夫曼樹(左子樹根結點的 權小于等于右子樹根結點的權)，并寫出哈夫曼編碼，計算帶權路徑長 度。 7. 給出圖的頂點集合和邊的集合，能畫出圖的鄰接矩陣、鄰接表，或者 給出圖的存儲結構，能夠畫出對應的圖 8. 用普里姆(prim )算法或克魯斯卡爾(Kruskal)算法構造最小生成樹。 9. 從某個頂點出發(fā)，畫出圖的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。 10. 設圖 G=( V, E), V=1, 2，3，4，5，6, E=, , , , , , 。請寫出圖 G

18、中頂點的所有拓 撲序列。 11. 已知一個圖的頂點集 V和邊集G分別為： V=0, 1, 2, 3, 4, 5, 6, 7； G=(0,1)3,(0,3)5,(0,5)18,(1,3)7,(1,4)6,(2,4)10,(2,7)20,(3,5)15,(3,6)12,(4,6)8 ,(4,7)12; 按照普里姆算法從頂點 2 出發(fā)得到最小生成樹，試寫出在最小生成樹 中依次得到的各條邊。 12. 設al、a2、a3是不同的關鍵字，且 a1a2a3,可組成六種不同的輸入 序列。問其中哪幾種輸入序列所構造的二叉排序樹的高度為 3 13. 構造二叉排序樹，在查找每個結點概率相等情況下的平均查找長度， 二叉排序樹的插入和刪除算法 14. 畫出用線性探測再散列（線性探查法）處理沖突時生成的哈希表及計 算平