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

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

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

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

4、儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A. 單鏈表B. 僅有頭指針的單循環(huán)鏈表 C. 雙鏈表 D. 僅有頭指針的單循環(huán)鏈表13. 在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個(gè)數(shù)為（ ）。A. n-1B. 2n-1C. n+1D. 2n+114. 稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（ ）。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. 一個(gè)棧的入棧序列是 a, b, c, d, e，則棧的不可能輸出序列是（ ）A. edcbaB. decbaC. dceadD. abcde二、填空題1. 下面程序段的時(shí)間復(fù)雜度是_。i = 1;While ( i = n )i = i * 5;2. 在一個(gè)單鏈表中，要?jiǎng)h除某一個(gè)結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的_結(jié)點(diǎn)。3. 在一個(gè)長(zhǎng)度為n的順序表中，在第1個(gè)元素 ( 1 = i = n+1 ) 之前插入一個(gè)新元素時(shí)須向后移動(dòng)_個(gè)元素。

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

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

8、是關(guān)鍵活動(dòng)?；顒?dòng)最早發(fā)生時(shí)間最遲發(fā)生時(shí)間5. 輸入一個(gè)正整數(shù)序列 23, 32, 16, 14, 42, 71, 57, 28, 55, 19, 12, 50 ，（1）構(gòu)造一棵二叉排序樹（只需最后結(jié)果圖）。（2）畫出構(gòu)造的一棵平衡二叉樹（只需最后結(jié)果圖）。（3）HASH表表長(zhǎng)為12，HASH函數(shù)為H ( key ) = key%11，試用線性探測(cè)再散列解決沖突的方法構(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è)計(jì)題有一個(gè)帶頭結(jié)點(diǎn)的單鏈表head