1、.數(shù)據(jù)結(jié)構(gòu)試題(A)專業(yè) 00計算機 班級 學(xué)號 姓名 一、 填空題（2分X 15=30分）1n行n列的上三角矩陣Ann，采用壓縮存儲到一維數(shù)組Sn*(n+1)/2中，若按以列序為主存儲，則Aij對應(yīng)的S中的存儲位置是 (1) 。2FIFO是英文 (2) 的縮寫，表示 (3) 結(jié)構(gòu)。3LIFO是英文 (4) 的縮寫，表示 (5) 結(jié)構(gòu)。4.一棵二叉樹有67個結(jié)點，這些結(jié)點的度要么是0，要么是2。這棵二叉樹中度為2的結(jié)點有 (6) 個。5. 在一個無環(huán)有向圖G中，若存在一條從頂點i到頂點j的弧，則在頂點的拓?fù)湫蛄兄校旤ci與頂點j的先后次序是 (7) 。6. 已知一個無向圖的鄰接矩陣表示，計算第

2、i個結(jié)點的度的方法是 (8) 。7一個無向圖的鄰接表中，若表結(jié)點的個數(shù)是m，則圖中邊的條數(shù)是_(9)_條。8判定一個有向圖是否存在回路除了可以利用深度優(yōu)先遍歷算法外，還可以利用 (10)。 9. 設(shè)一個閉散列表的容量為m，用線性探測法解決沖突，要插入一個鍵值，若插入成功，至多要進(jìn)行 （11） 次比較。10二分查找的存儲結(jié)構(gòu)僅限于 （12） 。11. 在插入排序、希爾排序、快速排序、堆排序、歸并排序中，排序是不穩(wěn)定的有 （13） 。 12在堆排序和快速排序中，若原始記錄無序，則最好選用 （14） 。13. 將兩個長度分別m和n（mn）的排好序的表歸并成一個排好序的表，至少要進(jìn) （15） 次鍵值比

3、較。二、 應(yīng)用題 （計算機專業(yè)選做8題X7分=56分，其他選做8題X9分=72分）1 用給出的一組字符A，B，C，D，E，F(xiàn)，G的權(quán)值是3，12，7，4，2，8，11，建立一棵哈夫曼樹，并給出每個字符的哈夫曼編碼。2 依次把結(jié)點50,20,10,100,120,30,70,90,80,110,60插入到初始狀態(tài)為空的平衡二叉樹中,使得在每次插入后保持該樹仍然是平衡二叉樹。依次畫出每次插入后所形成的平衡二叉樹。3 畫出對長度為10的有序表進(jìn)行二分查找的一棵判定樹，并求其等概率時查找成功的平均查找長度。4 使用哈希函數(shù)H(key)=key % 11，把一個整數(shù)值轉(zhuǎn)換成哈希表下標(biāo)，現(xiàn)要把數(shù)據(jù)1，13

4、，12，34，38，33，27，22插入到哈希表中（表長為11）。1）使用線性探測法構(gòu)造哈希表。2) 使用鏈地址法構(gòu)造哈希表。5 對于G1所示的連通圖，請畫出：1） 以頂點1為根的深度優(yōu)先生成樹；2） 如果有關(guān)節(jié)點，請找出所有的關(guān)節(jié)點(計算機專業(yè)做)6 對于G2所示的無向圖，采用Prim算法構(gòu)造從頂點1 開始的最小生成樹（要求畫出構(gòu)造過程的每一步）。7 對于有向無環(huán)圖G4，畫出圖的鄰接表，并根據(jù)該鄰接表寫出拓?fù)溆行蛐蛄小? 對數(shù)據(jù)(46,25,78,12,62,37,70,29)進(jìn)行直接插入排序,請寫出排序的每趟的過程。（計算機專業(yè)不做）9將數(shù)據(jù)序列(28,76,54,39,87,14,46,

5、25,78,62,12)按shell排序法進(jìn)行排序,增量序列為5，3，1，請寫出每倘排序完成之后的序列狀態(tài)。10. 將數(shù)據(jù)(46,25,78,12,62,37,70,29)進(jìn)行降序排序,請寫出堆排序的初建堆過程。11. 將數(shù)據(jù)序列(46,25,78,12,62,37,70,29)進(jìn)行歸并排序,請寫出每趟排序過程。（計算機專業(yè)不做）12對于如圖G3所示的AOE網(wǎng)，求出各事件、各活動可能的最早開始時間和允許的最晚完成時間及活動的時間余量，并問哪些活動是關(guān)鍵活動。三、 算法設(shè)計（計算機專業(yè)做，2 X 7分=14分）1 寫出從圖的鄰接表表示轉(zhuǎn)換成鄰接矩陣表示的算法。2 寫出快速排序的分區(qū)算法。數(shù)據(jù)結(jié)構(gòu)

6、試題(A)專業(yè) 班級 學(xué)號 姓名 一、 填空（2分X15=30分）（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）（14）（15） 00計算機 數(shù)據(jù)結(jié)構(gòu)A卷參考答案：一、填空（2分X15=30分）（1） j*(j+1)/2+i（2） First In First Out（3） 隊列（4） Last In First Out（5） 棧（6） 33（7） 不變（8） 第i 行或第i列非零元素之和（9） m./2（10）拓?fù)渑判颍?1）m（12）有序的順序表（13）希爾排序、快速排序、堆排序（14）快速排序（15）n二、 應(yīng)用題1 畫出哈夫曼樹4分哈夫曼編碼：(

7、3分）A： 0000 B：11 C：100 D：011 E：0001 F：101 G：012轉(zhuǎn)對2種滿分3ASL=(1*2+2*2+4*3+3*4)/10=2.945. 1)生成樹4分2）關(guān)節(jié)點： V1、V2、V3、V7、V8、V9 3分6 每邊1.2分123456782 4 5 6 7 7 4 68 7.拓?fù)湫蛄校篤3、B5、V1、V4、V6、V2、V7、V88初 始： 46 25 78 12 62 37 70 29第一趟： 46 25 78 12 62 37 70 29第二趟： 25 46 78 12 62 37 70 29第三趟： 25 46 78 12 62 37 70 29第四趟：

8、12 25 46 78 62 37 70 29第五趟： 12 25 46 62 78 37 70 29第六趟： 12 25 37 46 62 78 70 29第七趟： 12 25 37 46 62 70 78 29第八趟： 12 25 29 37 46 62 70 78 每1趟約1分，到出錯為止9. 初始： 28 76 54 39 87 14 46 25 78 62 12分組d=5排序后 12 46 25 39 62 14 76 54 78 87 28 分組d=3排序后 12 28 14 39 46 25 76 54 78 87 62 分組d=1排序后 12 14 25 28 39 46 54 62 76 78 87 每1趟約2分，到出錯為止10.每趟調(diào)整約2分 11.初 始： 46 25 78 12 62 37 70 29 第一趟后： 25 46 12 78 37 62 29 70 第二趟后： 25 46 12 78 37 62 29 70 第三趟后： 12 25 46 78 29 37 62 70 第四趟后： 12 25 29 37 46 62 70 78 12 1）求事件最早、遲時間3分 事件 1 2 3 4 5 6最早發(fā)生時間 0 6 13 4 22 25最遲發(fā)生時間 0 6 13 4 22 25 2）求出活