南京理工大學(xué)紫金學(xué)院數(shù)據(jù)結(jié)構(gòu)試卷高清數(shù)位重置版

1、一、選擇題1. 樹最適合用來表示（ ）。A. 有序數(shù)據(jù)B. 無序數(shù)據(jù)元素C. 元素之間具有分支層次關(guān)系的數(shù)據(jù)D. 元素之間無聯(lián)系的數(shù)據(jù)2. 一個堆是一棵（ ）二叉樹。A. 普通B. 排序C. 滿D. 完全3. 設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中共有（ ）個空指針域。A. 2m-1 B. 2m C. 2m+1D. 4m4. 線性結(jié)構(gòu)的順序存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)。A. 隨機(jī)存取B. 順序存取C. 索引存取D. 散列存取5. 一下是平衡二叉樹的是（ ）。A. B. C. D. 6. 對圖進(jìn)行廣度優(yōu)先遍歷時，通常采用（ ）來實現(xiàn)算法。A. 棧B. 隊列C.

2、 樹D. 圖7. 有一個有序表為 8，15，20，22，32，41，45，62，75，77，82，85，97 ，當(dāng)二分查找值為22的數(shù)據(jù)時要進(jìn)行（ ）次比較。A. 2B. 3C. 4D. 58. 設(shè)單鏈表中結(jié)點的結(jié)構(gòu)為 ( data , next ) 。已知指針n所指結(jié)點不是尾結(jié)點，若在指針p所指結(jié)點之后插入結(jié)點s，則應(yīng)執(zhí)行下列哪一個操作？A. s-next=p; p-next=s;B. s-next=p-next; p-next=s;C. s-next=p-next; p=s;D. p-next=s; s-next=p;9. 由權(quán)值分別為11. 8. 6. 2. 5的葉子結(jié)點生成一棵哈夫曼樹

3、，它的帶權(quán)路徑長度為（ ）。A. 24B. 71C. 48D. 5310. 無向圖G = ( V, E )，其中V = a，b，c，d，e，f ，E = (a, b) , (a, c) , (a, e) , (b, e) , (c, f) , (f, d) , (e, d) 。對該圖進(jìn)行深度優(yōu)先遍歷，下面不能得到的序列是（ ）。A. acfdebB. aebdfcC. aedfcbD. abecdf11. 設(shè)有廣義表D ( a, b, D )，其長度為（ ），深度為（ ）。A. B. 3C. 2D. 512. 線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ ）存

4、儲方式最節(jié)省運算時間。A. 單鏈表B. 僅有頭指針的單循環(huán)鏈表 C. 雙鏈表 D. 僅有頭指針的單循環(huán)鏈表13. 在有n個結(jié)點的二叉鏈表中，值為非空的鏈域的個數(shù)為（ ）。A. n-1B. 2n-1C. n+1D. 2n+114. 稀疏矩陣一般的壓縮存儲方法有兩種，即（ ）。A. 二維數(shù)組和三維數(shù)組B. 三元組與散列 C. 三元組與十字鏈表 D. 散列和十字鏈表15. 以下不是堆的序列是（ ）。A. 100, 85, 98, 77, 80, 60, 82, 40, 20, 10, 66B. 100, 98, 85, 82, 80, 77, 66, 60, 40, 20, 10C. 10, 20,

5、 40, 60, 66, 77, 80, 82, 85, 98, 100D. 100, 85, 40, 77, 80, 60, 66, 98, 82, 10, 2016. 一個棧的入棧序列是 a, b, c, d, e，則棧的不可能輸出序列是（ ）A. edcbaB. decbaC. dceadD. abcde二、填空題1. 下面程序段的時間復(fù)雜度是_。i = 1;While ( i = n )i = i * 5;2. 在一個單鏈表中，要刪除某一個結(jié)點，必須找到該結(jié)點的_結(jié)點。3. 在一個長度為n的順序表中，在第1個元素 ( 1 = i = n+1 ) 之前插入一個新元素時須向后移動_個元素。

6、4. 有一個10階對稱矩陣A，采用壓縮存儲方式（以行為主存儲，且LOC ( A00 ) = 1，則A85 的地址是_。5. 設(shè)在一棵二叉樹中，度為0的結(jié)點個數(shù)為8，度為2的結(jié)點個數(shù)為_。6. 設(shè)二叉樹結(jié)點的先根序列為ABEDCFGH，中根序列為EDBAFCHG，則二叉樹中葉子結(jié)點是_。7. 求最小生成樹算法有Prim算法和Kruskal算法兩種，_算法適合稠密圖，_算法適合稀疏圖。8. 數(shù)據(jù)表中有10000個元素，如果僅要求求出其中最大的10個元素，則采用_是算法最節(jié)省時間。9. 循環(huán)隊列中隊滿條件為：_。三、綜合題1. 畫出廣義表LS = ( ( ), ( e ), ( a, ( b, c,

7、 d ) ) ) 的頭尾鏈表存儲結(jié)構(gòu)。2. 已知一棵二叉樹的先序序列與中序序列分別為：ABCDEFGHI和BCAEDGHFI（1）給出該二叉樹的后序遍歷序列。（2）畫出該二叉樹的帶頭結(jié)點的中序線索二叉樹。（3）將該二叉樹轉(zhuǎn)換成森林。3. 設(shè)有無向圖G，要求使用Prim算法構(gòu)造以頂點C為起點的最小生成樹，同時，寫出構(gòu)造最小生成樹的每一步過程（無需注明權(quán)值）。DCAB155566423EF6第3題圖V5V4V1V0V2V3第4題圖67489103204. 根據(jù)下圖所示的AOE網(wǎng)，請回答以下問題：（1）求這個工程最早可能在什么時間結(jié)束；（2）求每個活動的最早開始時間和最遲開始時間；（3）確定哪些活動

8、是關(guān)鍵活動。活動最早發(fā)生時間最遲發(fā)生時間5. 輸入一個正整數(shù)序列 23, 32, 16, 14, 42, 71, 57, 28, 55, 19, 12, 50 ，（1）構(gòu)造一棵二叉排序樹（只需最后結(jié)果圖）。（2）畫出構(gòu)造的一棵平衡二叉樹（只需最后結(jié)果圖）。（3）HASH表表長為12，HASH函數(shù)為H ( key ) = key%11，試用線性探測再散列解決沖突的方法構(gòu)造哈希表。01234567891011 6. 設(shè)待排序的關(guān)鍵字序列為 27, 46, 5, 18, 16, 51, 32, 26 , 分別使用以下排序方法進(jìn)行排序，寫出題目所給定趟數(shù)的結(jié)果。（1）第三趟直接插入排序的結(jié)果。（2）第一趟希爾排序的結(jié)果（增量為3）。（3）第二趟歸并排序。（4）第一趟快速排序。四、算法設(shè)計題有一個帶頭結(jié)點的單鏈表head