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

1、南昌航空大學(xué)期末考試（計(jì)算機(jī)科學(xué)與技術(shù)）數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料計(jì)算題一. 一棵二叉樹(shù)的先序、中序和后序序列分別如下，其中有一部分未顯示出來(lái)。試求出空格處的內(nèi)容，并畫(huà)出該二叉樹(shù)。先序序列： B F ICEH G中序序列：D KFIA EJC后序序列： K FBHJ G A解：在先序序列空格中依次填A(yù)DKJ，中序中依次填BHG，后序中依次填DIEC。二叉樹(shù)自畫(huà)！二試列出如下圖中全部可能的拓?fù)渑判蛐蛄小＝猓喝靠赡艿耐負(fù)渑判蛐蛄袨椋?523634、152634、156234、561234、516234、512634、512364三已知哈希表地址空間為0.8，哈希函數(shù)為H(key)=key%7，采用線性探測(cè)

2、再散列處理沖突，將數(shù)據(jù)序列100,20,21,35,3,78,99,45依次存入此哈希表中，列出插入時(shí)的比較次數(shù)，并求出在等概率下的平均查找長(zhǎng)度以及查找因子。解：哈希表及查找各關(guān)鍵字要比較的次數(shù)如下所示：ASL=(4×1+1×2+1×4+2×5)=2.5a=8/9 四已知關(guān)鍵字序列23，13，5，28，14，25，試構(gòu)造二叉排序樹(shù)。 解： 五設(shè)有序列：w=23,24,27,80,28，試給出哈夫曼樹(shù)；哈夫曼樹(shù)如下圖所示：六：已知一棵二叉樹(shù)的先序序列與中序序列分別如下，試畫(huà)出此二叉樹(shù)。先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI解：先由先序

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

4、7,51,58)九三、（本題8分）請(qǐng)畫(huà)出如下圖所示的鄰接表。解：鄰接表如下圖所示：十判斷以下序列是否是小根堆? 如果不是，將它調(diào)整為小根堆。（1） 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 （2） 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 解：（1）不是小根堆。調(diào)整為：12,24,33,65,33,56,48,92,86,70 （2）是小根堆。十一 設(shè)有如下圖所示的AOE網(wǎng)（其中vi（i=l，2，6）表示事件，弧上表示活動(dòng)的天數(shù)）。找出所有的關(guān)鍵路徑。 解：所有的關(guān)鍵路徑有：v1v2v3v5v6，以及v1v4v6。十二. 對(duì)給定的有7個(gè)頂點(diǎn)的有向圖的鄰接矩陣如下：（l）畫(huà)出