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

1、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中為止。2. 簡述AOV網(wǎng)絡(luò)中為何不能出現(xiàn)回路，如何判斷AOV網(wǎng)絡(luò)是否有回路？答：在AOV網(wǎng)絡(luò)中，如果活動vi必須在vj之前進行，

2、則稱為存在有向邊；在AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路，如果出現(xiàn)了，則意味著某項活動應(yīng)以自己作為先決條件。如何檢查AOV網(wǎng)是否存在有向環(huán)：檢測有向環(huán)的一種方法是對AOV網(wǎng)絡(luò)構(gòu)造它的拓?fù)溆行蛐蛄?。即將各個頂點(代表各個活動)排列成一個線性有序的序列，使得AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。 （1）這種構(gòu)造AOV網(wǎng)絡(luò)全部頂點的拓?fù)溆行蛐蛄械倪\算就叫做拓?fù)渑判颉?（2）如果通過拓?fù)渑判蚰軐OV網(wǎng)絡(luò)的所有頂點都排入一個拓?fù)溆行虻男蛄兄?，則該AOV網(wǎng)絡(luò)中必定不會出現(xiàn)有向環(huán)；相反，如果得不到滿足要求的拓?fù)溆行蛐蛄?，則說明AOV網(wǎng)絡(luò)中存在有向環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。 3. 為何需

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ù)組所存放的循環(huán)隊列最大長度是N-1。4. 簡述堆的刪除算法，其刪除的是那個值？答：堆的刪除算法：首先，移除根節(jié)點的元素（并把根節(jié)點作為當(dāng)前結(jié)點

4、）比較當(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é)點。在堆的算法里面，刪除的值為根值。5. 線索二叉樹中，什么是線索，它是否唯一？可有根據(jù)什么順序得到？答：指向直接前驅(qū)結(jié)點和指向直接后續(xù)結(jié)點的指針被稱為線索（Thread），加了線索的二叉樹稱為線索二叉樹。線索二叉樹是唯一的，因為知道先序遍歷后，第一個根是唯一確定的，然后在中序遍歷里這個根將它分為兩個部分，第一個

5、根的兩棵子樹的根也會唯一確定，依次此類推，所有子樹的根都唯一確定,二叉樹就是唯一的。6. 鏈?zhǔn)讲迦肱判驅(qū)Ρ戎苯硬迦肱判蛴泻蝺?yōu)點和缺點？答：鏈?zhǔn)讲迦肱判騼?yōu)點是速度極快，特別是在數(shù)據(jù)量大的時候效果尤為明顯；其缺點是在數(shù)據(jù)量少的情況下內(nèi)存相對消耗較多。直接插入排序優(yōu)點是排序比較簡單，穩(wěn)定性高；缺點是在數(shù)據(jù)量很大的情況下效率很低。所以鏈?zhǔn)讲迦肱判蜻m合數(shù)據(jù)量大的情況，直接插入排序適合數(shù)據(jù)量少的情況。7. 畫出該圖的鄰接矩陣和鄰接表。根據(jù)鄰接表從A開始求DFS（深度優(yōu)先搜索）和BFS（廣度優(yōu)先搜索）序列。ABCDEF答：DFS：A->C->F->E->D->BBFS: A-&

6、gt;C->B->F->D->E8. 已知序列70,73,69,23,93,18,11,68,請給出直接插入排序作升序排序每一趟的結(jié)果和快速排序作為升序排序時一趟的結(jié)果。答：直接插入排序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 93 18 11 68 18 23 69 70 73 93 11 68 11 18 23 69 70 73 93 68 11 18 23 68 69 70 73 93快速排序

7、R1 R2 R3 R4 R5 R6 R7 R8 left right 70 73 69 23 93 18 11 68 1 1068 11 69 23 18 70 93 73 1 518 11 23 68 69 70 93 73 1 311 18 23 68 69 70 93 73 7 811 18 23 68 69 70 73 93 9下圖表示一個地區(qū)的交通網(wǎng)，頂點表示城市，邊表示連結(jié)城市間的公路，邊上的權(quán)表示修建公路花費的代價。怎樣選擇能夠溝通每個城市且總造價最省的n-1條公路，畫出所有可能的方案。答：2113645111510. 已知一個無向圖的鄰接表如下圖所示： (1) 畫出這個圖。(2

8、) 以v1為出發(fā)點，對圖進行廣度優(yōu)先搜索和深度優(yōu)先搜索。給出搜索的結(jié)點序列。523104答： （1）（2）.DFS: 0->1->3->4->5->2BFS: 0->1->2->3->5->411. 設(shè)有一組關(guān)鍵字（70,73,69,23,93,18,11,68）,設(shè)提供的散列表長度為12，用除留余數(shù)法設(shè)計散列函數(shù)，取的較恰當(dāng)除數(shù)應(yīng)為多少。采用線性探測方法解決散列沖突，請構(gòu)造其散列表并將所有關(guān)鍵字入表。答：因為散列表長度為12，且除數(shù)應(yīng)盡量取基數(shù)；所以為11.經(jīng)檢驗：70%11=4；73%11=7；69%11=3；23%11=1; 9

9、3%11=3; 18%11=7; 11%11=0; 18%11=2;采用線性探測的哈希表（12個桶，每個桶一個槽）112318697093731812. 用最短路徑算法Dijkstra計算單源多目標(biāo)最短路徑。圖中的“1”號結(jié)點為源結(jié)點。按提示圖表給出每一步計算時最短路徑的變化。10432101003050206010510答：dist6存放從頂點v0到其他各頂點的當(dāng)前最短路徑。Path6存放在最短路徑上該定點的前一頂點。S6存放以求得的在最短路徑上的定點集合V6存放所有頂點012345SV-SDistpath150111110,2,3,4,5Distpath6021111,20,3,4,5Di

10、stpath900160011,2,03,4,5Distpath150311031,2,0,34,5Distpath12051,2,0,3,54Distpath1,2,0,3,5,413.完成下面二叉搜索樹查找插入程序（說明含義）。此程序使用的是什么算法?根據(jù)給出的結(jié)點圖給出結(jié)點類的數(shù)據(jù)成員描述。LchilddataRchildtemplate <class Elem>bool BST<Elem>:search_and_insert( Binnode<Elem> *&sub_root, const Elem &new_data) if (su

11、b_root = NULL) sub_root = new Binnode<Elem>(new_data); return ture; else if (new_data < sub_root->data) return search_and_insert(sub_root->lchild, new_data); else if (new_data > sub_root->data)return search_and_insert(sub_root->rchild, new_data); 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_data<sub_root->data,則遞歸調(diào)用該函數(shù)，并把sub_root->lchild作為引用指針；如果sub_root->data<new_data，則sub_rchild作為引用指針