數(shù)據(jù)結(jié)構(gòu)習(xí)題

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

2、隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn) 的運(yùn)算是 （ C ） 。 A R=F-next;B R=R-next; C F=F-next; D F=R-next; 串是一種特殊的線性表，其特殊性體現(xiàn)在 （ B ）。 A .可以順序存儲(chǔ) C.可以鏈接存儲(chǔ) 以下說法正確的是（ C ）。 A）空串與空格串是相同的 C）空串是零個(gè)字符組成的串 B. 數(shù)據(jù)元素是一個(gè)字符 D.數(shù)據(jù)元素可以是多個(gè)字符 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) 將一個(gè) A1.100,1.100的三對(duì)角矩陣， 按行優(yōu)先存入一維數(shù)組B1.298 中，A中元素 A66, 65在B數(shù)組中的位置 k為（B ）。 A） 198B） 195C） 197 一個(gè)稀疏矩陣的轉(zhuǎn)置矩陣應(yīng)是（ B ）。 A. 下三角矩陣B.稀疏矩陣C.非稀疏矩陣 D.有時(shí)為稀疏矩陣 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 )個(gè)結(jié)點(diǎn)。 A16B 32 具有 10 個(gè)葉子結(jié)點(diǎn)的二叉樹中有( A 8B9 在二叉樹的中序遍歷遞歸算法中， 時(shí)作訪問操作。 A1B2C 3 C 31D 10 B)個(gè)度為2的結(jié)點(diǎn)。 C 10D 11 順著搜索路徑， 在第( B )次經(jīng)過結(jié)點(diǎn) D4 在中序線索二叉樹中，若某結(jié)點(diǎn)有右孩子，則該結(jié)點(diǎn)的直接后繼是 A 左子樹的最右下結(jié)點(diǎn) B 右子樹的最右下結(jié)點(diǎn) C 左子樹的最左下結(jié)點(diǎn) D 右子樹的最左下結(jié)點(diǎn) 按照二叉樹的定義，具有 3 個(gè)結(jié)點(diǎn)的二叉樹有 ( C )種形態(tài)。 A3 B4 C5 D6 某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是(B)的 二叉樹。

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

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

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

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

9、的關(guān)鍵字類 型是字符串） 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. 在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí) 間復(fù)雜度是（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、速排序中，每次劃分選擇的基準(zhǔn)元素為該區(qū)間的（D ）時(shí)，得到的兩 個(gè)子區(qū)間是均勻的。 72. A .最大值B.最小值 C.任意值D.中間值 73. 若從二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按關(guān)鍵字 有序，則該二叉樹是下列樹中的哪種（ C） A.二叉排序樹 B.哈夫曼樹C.堆。 二、填空題 1. 在一個(gè)長度為n的順序表中刪除第i個(gè)元素，要移動(dòng)_n-i_個(gè)元素。 2. 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表長的一半元 素，具體移動(dòng)元素的個(gè)數(shù)與元素所在的位置有關(guān)。 3. 若線性表采用順序存儲(chǔ)結(jié)構(gòu)存放，那么在長度為n的線性表中刪除第i （1 next = h 。 5. 一個(gè)隊(duì)列的入隊(duì)序

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

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

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

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

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

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

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

18、中頂點(diǎn)的所有拓 撲序列。 11. 已知一個(gè)圖的頂點(diǎn)集 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; 按照普里姆算法從頂點(diǎn) 2 出發(fā)得到最小生成樹，試寫出在最小生成樹 中依次得到的各條邊。 12. 設(shè)al、a2、a3是不同的關(guān)鍵字，且 a1a2a3,可組成六種不同的輸入 序列。問其中哪幾種輸入序列所構(gòu)造的二叉排序樹的高度為 3 13. 構(gòu)造二叉排序樹，在查找每個(gè)結(jié)點(diǎn)概率相等情況下的平均查找長度， 二叉排序樹的插入和刪除算法 14. 畫出用線性探測(cè)再散列（線性探查法）處理沖突時(shí)生成的哈希表及計(jì) 算平