數(shù)據(jù)結構期末考試復習題及答案

1、精品文檔 1. 什么是最小生成樹？簡述最小生成樹的 Prime 算法的思想。 答：最小生成樹就是構造一棵生成樹，使得樹上各邊的代價之和最小。 普里姆算法 （Prim） 的基本思想： 從連通網(wǎng)絡 N = V, E 中的某一頂點 u0 出發(fā)，選擇與它關聯(lián)的具有最小權值的邊 （u0, v）， 將其頂點加入到生成樹的頂點集合 U 中。以后每一步從一個頂點在 U 中，而另一個頂點不 在 U 中的各條邊中選擇權值最小的邊 （u, v）, 把它的頂點加入到集合 U 中。如此繼續(xù)下去， 直 到網(wǎng)絡中的所有頂點都加入到生成樹頂點集合 U 中為止。 2. 簡述 AOV 網(wǎng)絡中為何不能出現(xiàn)回路，如何判斷 AOV 網(wǎng)

2、絡是否有回路？ 答：在 AOV 網(wǎng)絡中，如果活動 vi 必須在 vj 之前進行，則稱為存在有向邊；在 AOV 網(wǎng)絡中 不能出現(xiàn)有向回路，如果出現(xiàn)了，則意味著某項活動應以自己作為先決條件。 如何檢查AOV網(wǎng)是否存在有向環(huán)： 檢測有向環(huán)的一種方法是對 AOV網(wǎng)絡構造它的拓撲有序序列。即將各個頂點（代表各個活動） 排列成一個線性有序的序列，使得 AOV網(wǎng)絡中所有應存在的前驅(qū)和后繼關系都能得到滿足。 （1 ）這種構造AOV網(wǎng)絡全部頂點的拓撲有序序列的運算就叫做拓撲排序。 （2 ）如果通過拓撲排序能將 AOV網(wǎng)絡的所有頂點都排入一個拓撲有序的序列中，則該AOV 網(wǎng)絡中必定不會出現(xiàn)有向環(huán)；相反，如果得不到

3、滿足要求的拓撲有序序列， 則說明AOV網(wǎng)絡 中存在有向環(huán)，此 AOV網(wǎng)絡所代表的工程是不可行的。 3. 為何需要采用循環(huán)隊列？ n 個空間的循環(huán)隊列，最多存儲多少個元素？為什 么？ 答：循環(huán)隊列以克服順序隊列的 假上溢 現(xiàn)象，能夠使存儲隊列的向量空間得到充分的利用， 所以采用循環(huán)隊列。 n 個空間的循環(huán)隊列，最多存儲 n-1 個元素，那是為了區(qū)別循環(huán)隊列的隊空和隊滿的條件。 隊空的條件是 Q.front=Q.rear ，而隊滿的條件是 （Q.rear+1）%N=Q.front（N 是數(shù)組中單元的總 數(shù)），因此， Q.rear 所指向的數(shù)組單元處于未用狀態(tài)。所以說， N 個單元的數(shù)組所存放的循

4、環(huán)隊列最大長度是 N-1 。 4. 簡述堆的刪除算法，其刪除的是那個值？ 答：堆的刪除算法 ：首先，移除根節(jié)點的元素（并把根節(jié)點作為當前結點）比較當前結 點的兩個孩子結點的元素大小，把較大的那個元素移給當前結點，接著把被移除元素的 孩子結點作為當前結點，并再比較當前結點的孩子的大小，以此循環(huán)，直到最后一個葉 子結點的值大于或等于當前結點的孩子結點或孩子結點的位置超過了樹中元素的個數(shù)， 則退出循環(huán)。最后把最后葉子結點的元素移給當前結點。 在堆的算法里面，刪除的值為根值 。 5. 線索二叉樹中，什么是線索，它是否唯一？可有根據(jù)什么順序得到？ 答：指向直接前驅(qū)結點和指向直接后續(xù)結點的指針被稱為線索（

5、Thread）,加了線索的二叉 樹稱為線索二叉樹。線索二叉樹是唯一的，因為知道先序遍歷后，第一個根是唯一確定的， 然后在中序遍歷里這個根將它分為兩個部分，第一個根的兩棵子樹的根也會唯一確定，依次 此類推，所有子樹的根都唯一確定，二叉樹就是唯一的。 6. 鏈式插入排序?qū)Ρ戎苯硬迦肱判蛴泻蝺?yōu)點和缺點？ 答:鏈式插入排序優(yōu) 點是速度極快，特別是在數(shù)據(jù)量大的時候效果尤為明顯；其|缺點是在數(shù)據(jù)量少的情況 下內(nèi)存相對消耗較多。直接插入排序優(yōu)點是排序比較簡單，穩(wěn)定性高；缺點是在數(shù)據(jù)量很大的情況下效率 很低。 所以鏈式插入排序適合數(shù)據(jù)量大的情況，直接插入排序適合數(shù)據(jù)量少的情況。 7. 畫出該圖的鄰接矩陣和鄰接

6、表。根據(jù)鄰接表從A開始求DFS（深度優(yōu)先搜索） DFS: A-C-F-E-D-B BFS: A-C-B-F-D-E 8. 已知序列70,73,69,23,93,18,11,68請給出直接插入排序作升序排序每一趟的 結果和快速排序作為升序排序時一趟的結果。 答： 直接插入排序 70 73 69 23 93 18 11 68 70 73 69 23 93 18 11 68 69 70 73 23 93 18 11 68 23 69 70 73 93 18 11 68 23 69 70 73 9318 11 68 18 23 69 70 73 9311 68 11 18 23 69 70 73 93

7、68 11 18 23 68 69 70 73 93 快速排序 R1 R2 R3 R4 R5 R6 R7 R8 left right 70 73 69 23 93 18 11 68 1 10 68 11 69 23 18 70 93 73 1 5 18 11 23 68 69 70 93 73 1 3 11 18 23 68 69 70 93 73 7 8 11 18 23 68 69 70 73 93 9下圖表示一個地區(qū)的交通網(wǎng)，頂點表示城市，邊表示連結城市間的公路，邊 上的權表示修建公路花費的代價。怎樣選擇能夠溝通每個城市且總造價最省的 n-1條公路，畫出所有可能的方案。 10.已知一個無向圖的鄰接表如下圖所示: 精品文檔 （1）畫出這個圖。 以V1為出發(fā)點，對圖