南昌航空大學(xué)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料

1、南昌航空大學(xué)期末考試(計(jì)算機(jī)科學(xué)與技術(shù)) 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料 計(jì)算題 一. 一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。試求出 空格處的內(nèi)容，并畫出該二叉樹。 先序序列：_B_F_ICEH_G 中序序列：D_KFIA_EJC 后序序列：_K_FBHJ_G_A 解：在先序序列空格中依次填A(yù)DKJ,中序中依次填BHG,后序中依次填DIECa 二叉樹自畫！ 二. 試列出如下圖中全部可能的拓?fù)渑判蛐蛄小?解：全部可能的柘撲排序序列為:1523634. 152634、156234、561234、516234、512634、 512364 三已知哈希表地址空間為0.8,哈希函數(shù)為H(k

2、ey)=key%7,采用線性探測(cè)再散列處 理沖究，將數(shù)據(jù)序列100,20,21,35,3, 78,99,45依次存入此哈希表中，列出插入?yún)嫉谋容^ 次數(shù)，并求出在等概率下的平均查找長(zhǎng)度以及查找因子。 解：哈希表及查找各關(guān)鍵字要比較的次數(shù)如下所示： 哈希地址 0 1 2 3 45 6 7 8 關(guān)鍵字 21 35 100 3 78 99 20 25 比較次數(shù) 1 2 1 1 4 5 1 5 ASL=1 (4X1+1 X 2+1 X 4+2X5) = 8 五.設(shè)有序列：w= 23, 24,27,80,28,試給出哈夫曼樹; 哈夫曼樹如下圖所示: 六：已知一棵二義樹的先序序列與中序序列分別如下，試畫出此

3、二義樹。 先序序列:ABCDEFGHIJ 中序序列：CBEDAGHFJI 解：先由先序序列的第一個(gè)結(jié)點(diǎn)確定二叉樹的根結(jié)點(diǎn)，再由根結(jié)點(diǎn)在中序序列中左側(cè)部 分為左子樹結(jié)點(diǎn)，在右側(cè)部分為右子樹結(jié)點(diǎn)，再由先序序列的第一個(gè)結(jié)點(diǎn)確定根結(jié)點(diǎn)的左右 七(本題8分) 對(duì)于如下圖所示的G,用Kruskal算法構(gòu)造罠小生成樹，要求圖示出每一步的變化情況。 解：用Kruskal算法構(gòu)造最小生成樹的過程如下圖所示: 八. 給出一組關(guān)鍵字29. 18、25、47、58、12、51. 10,寫出歸并排序方法進(jìn)行排序 時(shí)的變化過程。 解： (I8.29) (25,47) (12,58) (10,51) (I8, 25,29,

4、47) (10,12.51,58) (I0,12,18,25, 29.47.51.58) 九. 三、(本題8分) 請(qǐng)畫出如下圖所示的鄰接表。 解：鄰接表如下圖所示: 十.判斷以下序列是否是小根堆 如果不是，將它調(diào)整為小根堆。 (1) 12, 70, 33,65,24,56,48, 92, 86, 33 (2) 05, 23, 20,2&40,3&29, 61, 35, 76, 47,100 解：(1)不是小根堆。調(diào)整為：12,24, 33,65, 33,56,48,92,86, 70 (2)是小根堆。 十一.設(shè)有如下圖所示的A0E網(wǎng)(其中vi (i = l, 2,6)表示爭(zhēng)件，弧上表示活動(dòng) 的天數(shù))。 找出所有的關(guān)鍵路徑。 解：所有的關(guān)鍵路徑有：v1Tv2Tv3Tv5Tv6,以及v1Tv4Tv6 十二.對(duì)給定的有7個(gè)頂點(diǎn)的有向圖的鄰接矩陣如下： (1) 畫出該有向圖； (2) 若將圖看成是A0E-網(wǎng)，畫出關(guān)鍵路徑。 OC 2 5 2 00 0C 0C OC CC 2 00 00 8 0C OC CC 00 1 3 5 00 CC 8 00 00 5 0C 0C OC 8 00 00 00 3 9 OC 0