數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)題及答案

1、數(shù)據(jù)結(jié)構(gòu) 期末考試復(fù)習(xí)題及答案 1. 什么是最小生成樹？簡述最小生成樹的 Prime 算法的思想。 答：最小生成樹就是構(gòu)造一棵生成樹，使得樹上各邊的代價之和最小。 普里姆算法 （Prim） 的基本思想： 從連通網(wǎng)絡(luò) N = V, E 中的某一頂點 u0 出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊 （u0, v）， 將其頂點加入到生成樹的頂點集合 U 中。以后每一步從一個頂點在 U 中，而另一個頂點不 在 U 中的各條邊中選擇權(quán)值最小的邊 （u, v）, 把它的頂點加入到集合 U 中。如此繼續(xù)下去， 直 到網(wǎng)絡(luò)中的所有頂點都加入到生成樹頂點集合U 中為止。 BBFgn。 2. 簡述 AOV 網(wǎng)絡(luò)中為何

2、不能出現(xiàn)回路，如何判斷 AOV 網(wǎng)絡(luò)是否有回路？ 答：在 AOV 網(wǎng)絡(luò)中，如果活動 vi 必須在 vj 之前進行，則稱為存在有向邊；在 AOV 網(wǎng)絡(luò)中 不能出現(xiàn)有向回路，如果出現(xiàn)了，則意味著某項活動應(yīng)以自己作為先決條件。UrObH。 如何檢查AOV網(wǎng)是否存在有向環(huán)： 檢測有向環(huán)的一種方法是對 AOV網(wǎng)絡(luò)構(gòu)造它的拓?fù)溆行蛐蛄小＜磳⒏鱾€頂點（代表各個活動） 排列成一個線性有序的序列，使得 AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。 qUHWt （1 ）這種構(gòu)造AOV網(wǎng)絡(luò)全部頂點的拓?fù)溆行蛐蛄械倪\算就叫做拓?fù)渑判颉?（2 ）如果通過拓?fù)渑判蚰軐?AOV網(wǎng)絡(luò)的所有頂點都排入一個拓?fù)溆行虻男蛄?/p>

3、中，則該AOV 網(wǎng)絡(luò)中必定不會出現(xiàn)有向環(huán)；相反，如果得不到滿足要求的拓?fù)溆行蛐蛄?，則說明AOV網(wǎng)絡(luò) 中存在有向環(huán)，此 AOV網(wǎng)絡(luò)所代表的工程是不可行的。NN5HT 3. 為何需要采用循環(huán)隊列？ n 個空間的循環(huán)隊列，最多存儲多少個元素？為什 么？ 答：循環(huán)隊列以克服順序隊列的 假上溢 現(xiàn)象，能夠使存儲隊列的向量空間得到充分的利用， 所以采用循環(huán)隊列。 xKmAz。 n 個空間的循環(huán)隊列，最多存儲 n-1 個元素，那是為了區(qū)別循環(huán)隊列的隊空和隊滿的條件。 隊空的條件是 Q.front=Q.rear ，而隊滿的條件是 （Q.rear+1）%N=Q.front（N 是數(shù)組中單元的總 數(shù)），因此， Q

4、.rear 所指向的數(shù)組單元處于未用狀態(tài)。所以說，N 個單元的數(shù)組所存放的循 環(huán)隊列最大長度是 N-1 。 8hCzq。 4. 簡述堆的刪除算法，其刪除的是那個值？ 答：堆的刪除算法 ：首先，移除根節(jié)點的元素（并把根節(jié)點作為當(dāng)前結(jié)點）比較當(dāng)前結(jié) 點的兩個孩子結(jié)點的元素大小，把較大的那個元素移給當(dāng)前結(jié)點，接著把被移除元素的 孩子結(jié)點作為當(dāng)前結(jié)點，并再比較當(dāng)前結(jié)點的孩子的大小，以此循環(huán)，直到最后一個葉 子結(jié)點的值大于或等于當(dāng)前結(jié)點的孩子結(jié)點或孩子結(jié)點的位置超過了樹中元素的個數(shù)， 則退出循環(huán)。最后把最后葉子結(jié)點的元素移給當(dāng)前結(jié)點。1Zvnj 。 在堆的算法里面，刪除的值為根值 。 5. 線索二叉樹中

5、，什么是線索，它是否唯一？可有根據(jù)什么順序得到？ 答：指向直接前驅(qū)結(jié)點和指向直接后續(xù)結(jié)點的指針被稱為線索（Thread），加了線索的二叉 樹稱為線索二叉樹。線索二叉樹是唯一的，因為知道先序遍歷后，第一個根是唯一確定的， 然后在中序遍歷里這個根將它分為兩個部分，第一個根的兩棵子樹的根也會唯一確定，依次 此類推，所有子樹的根都唯一確定，二叉樹就是唯一的。8TsdS 6. 鏈?zhǔn)讲迦肱判驅(qū)Ρ戎苯硬迦肱判蛴泻蝺?yōu)點和缺點？ 答:鏈?zhǔn)讲迦肱判騼?yōu) 點是速度極快，特別是在數(shù)據(jù)量大的時候效果尤為明顯；其缺點是在數(shù)據(jù)量少的情況 下內(nèi)存相對消耗較多。直接插入排序優(yōu)點是排序比較簡單，穩(wěn)定性高；缺點是在數(shù)據(jù)量很大的情況下

6、效率 很低。NeeAl。 所以鏈?zhǔn)讲迦肱判蜻m合數(shù)據(jù)量大的情況，直接插入排序適合數(shù)據(jù)量少的情況。 7. 畫出該圖的鄰接矩陣和鄰接表。根據(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請給出直接插入排序作升序排序每一趟的 結(jié)果和快速排序作為升序排序時一趟的結(jié)果。skiFU。 答： 直接插入排序 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

7、68 23 69 70 73 9318 11 68 18 23 69 70 73 9311 68 11 18 23 69 70 73 9368 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)，頂點表示城市，邊表示連結(jié)城

8、市間的公路，邊 上的權(quán)表示修建公路花費的代價。怎樣選擇能夠溝通每個城市且總造價最省的 n-1條公路，畫出所有可能的方案。VbeAh 答: 10. 已知一個無向圖的鄰接表如下圖所示: 0 A 1 _* 2 A 1 B 0 3 A 2 C * 10 5 3 D K 1 4 4 E 3 ” 5 A 5 F 2 4 A （1）畫出這個圖。 以V1為出發(fā)點，對圖進行廣度優(yōu)先搜索和深度優(yōu)先搜索。給出搜索的 70, 73, 69, 23, 93, 1 93%11=3; 18%11=7xdbY4. 11%11=0; 18%11=2; 采用線性探測的哈希表（12個桶，每個桶一個槽） 11 23 18 69 70

9、 93 73 18 12. 用最短路徑算法Dijkstra計算單源多目標(biāo)最短路徑。圖中的“ T號結(jié)點為 源結(jié)點。按提示圖表給出每一步計算時最短路徑的變化。RJYSZ 答： dist6存放從頂點vO到其他各頂點的當(dāng)前最短路徑。 Path 6存放在最短路徑上該定點的前一頂點。 S6存放以求得的在最短路徑上的定點集合V6存放所有頂點 0 1 2 3 4 5 S V-S Dist path oo 1 50 1 OO 1 OO 1 OO 1 1 0,2,3,4,5 Dist path 60 2 oo 1 oo 1 oo 1 1,2 0,3,4,5 Dist path 90 0 160 0 oo 1 1,

10、2,0 3,4,5 Dist path 150 3 110 3 120,3 4,5 Dist path 120 5 120,3,5 4 Dist path 120,3,5,4 13. 完成下面二叉搜索樹查找插入程序（說明含義）。此程序使用的是什么算法？ 根據(jù)給出的結(jié)點圖給出結(jié)點類的數(shù)據(jù)成員描述。4HxgD Lchild data Rchild template vclass Elem bool BST:search_a nd_i nsert( Binno de * retur n ture; else if (n ew_data data) return search_a nd_i nsert

11、(ub_root-lchild, n ew_data)dQzv2 else if (n ew_data sub_root-data) return search_a nd_i nsertrchild, n ew_data) ;Asthc。 else return false; 算法：在該函數(shù)中引用一個指向Binnode指針sub_root和指向ELEM類型的指 針new_data,如果指向 Binonode的指針sub_root為空，則該指針指向一個帶 ELEM類型數(shù)據(jù)的新結(jié)點。如果sub_root所指向的不為空，則比較sub_root-data 與new-data的大小，當(dāng)new_datadata則遞歸調(diào)用該函數(shù)，并把 sub_root-lchild 作為弓丨用指針；如果 sub_root-datanew_