《數(shù)據(jù)結構期末考試復習題及答案》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構期末考試復習題及答案（7頁珍藏版）》請在裝配圖網上搜索。

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

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

3、存在有向環(huán)，此AOV網絡所代表的工程是不可行的。 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. 簡述堆的刪除算法，其刪

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

5、叉樹是唯一的，因為知道先序遍歷后，第一個根是唯一確定的，然后在中序遍歷里這個根將它分為兩個部分，第一個根的兩棵子樹的根也會唯一確定，依次此類推，所有子樹的根都唯一確定,二叉樹就是唯一的。 6. 鏈式插入排序對比直接插入排序有何優(yōu)點和缺點？ 答：鏈式插入排序優(yōu)點是速度極快，特別是在數(shù)據(jù)量大的時候效果尤為明顯；其缺點是在數(shù)據(jù)量少的情況下內存相對消耗較多。直接插入排序優(yōu)點是排序比較簡單，穩(wěn)定性高；缺點是在數(shù)據(jù)量很大的情況下效率很低。 所以鏈式插入排序適合數(shù)據(jù)量大的情況，直接插入排序適合數(shù)據(jù)量少的情況。 7. 畫出該圖的鄰接矩陣和鄰接表。根據(jù)鄰接表從A開始求DFS（

6、深度優(yōu)先搜索）和BFS（廣度優(yōu)先搜索）序列。 A B C D E F 答： 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

7、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 快速排序 R1 R2 R3 R4 R5 R6 R7 R8 left right [70 73 69 23 93 18 11 68] 1

8、 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ū)的交通網，頂點表示城市，邊表示連結城市間的公路，邊上的權表示修建公路花費的代價。怎樣選擇能夠溝通每個城市且總造價最省的n-1條公路，畫出所有可能的方案。 答： 2

9、 1 1 3 6 4 5 1 1 1 5 10. 已知一個無向圖的鄰接表如下圖所示： (1) 畫出這個圖。 (2) 以v1為出發(fā)點，對圖進行廣度優(yōu)先搜索和深度優(yōu)先搜索。給出搜索的結點序列。 5 2 3 1 0 4 答： （1） （2）. DFS: 0->1->3->4->5->2 BFS: 0->1->2->3->5->4 11. 設有一組關鍵字（70,7

10、3,69,23,93,18,11,68）,設提供的散列表長度為12，用除留余數(shù)法設計散列函數(shù)，取的較恰當除數(shù)應為多少。采用線性探測方法解決散列沖突，請構造其散列表并將所有關鍵字入表。 答： 因為散列表長度為12，且除數(shù)應盡量取基數(shù)；所以為11. 經檢驗：70%11=4；73%11=7；69%11=3；23%11=1; 93%11=3; 18%11=7; 11%11=0; 18%11=2; 采用線性探測的哈希表（12個桶，每個桶一個槽） 11 23 18 69 70 93 73 18 12

11、. 用最短路徑算法Dijkstra計算單源多目標最短路徑。圖中的“1”號結點為源結點。按提示圖表給出每一步計算時最短路徑的變化。 1 0 4 3 2 10 100 30 50 20 60 10 5 10 答： dist[6]存放從頂點v0到其他各頂點的當前最短路徑。 Path[6]存放在最短路徑上該定點的前一頂點。 S[6]存放以求得的在最短路徑上的定點集合V[6]存放所有頂點 0 1 2 3 4 5 S V-S Dist path ∞ 1 50 1 ∞ 1 ∞ 1 ∞ 1 1 0,2,3,4,5 D

12、ist path 60 2 ∞ 1 ∞ 1 ∞ 1 1,2 0,3,4,5 Dist path 90 0 160 0 ∞ 1 1,2,0 3,4,5 Dist path 150 3 110 3 1,2,0,3 4,5 Dist path 120 5 1,2,0,3,5 4 Dist path 1,2,0,3,5,4 13.完成下面二叉搜索樹查找插入程序（說明含義）。此程序使用的是什么算法?根據(jù)給出的結點圖給出結點類

13、的數(shù)據(jù)成員描述。 Lchild data Rchild template bool BST::search_and_insert( Binnode *&sub_root, const Elem &new_data) { if (sub_root == NULL) { sub_root = new Binnode(new_data); return ture; } else if (new_data < sub_root->data)

14、 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ù)的新結點。如果sub_root

15、所指向的不為空，則比較sub_root->data與new-data的大小，當new_datadata,則遞歸調用該函數(shù)，并把sub_root->lchild作為引用指針；如果sub_root->data