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

1. 什么是最小生成樹？簡述最小生成樹的Prime算法的思想。答：最小生成樹就是構(gòu)造一棵生成樹，使得樹上各邊的代價(jià)之和最小。普里姆算法(Prim)的基本思想： 從連通網(wǎng)絡(luò) N = V, E 中的某一頂點(diǎn) u0 出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0, v)，將其頂點(diǎn)加入到生成樹的頂點(diǎn)集合U中。以后每一步從一個(gè)頂點(diǎn)在U中，而另一個(gè)頂點(diǎn)不在U中的各條邊中選擇權(quán)值最小的邊(u, v),把它的頂點(diǎn)加入到集合U中。如此繼續(xù)下去，直到網(wǎng)絡(luò)中的所有頂點(diǎn)都加入到生成樹頂點(diǎn)集合U中為止。2. 簡述AOV網(wǎng)絡(luò)中為何不能出現(xiàn)回路，如何判斷AOV網(wǎng)絡(luò)是否有回路？答：在AOV網(wǎng)絡(luò)中，如果活動(dòng)vi必須在vj之前進(jìn)行，則稱為存在有向邊；在AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路，如果出現(xiàn)了，則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先決條件。如何檢查AOV網(wǎng)是否存在有向環(huán)：檢測有向環(huán)的一種方法是對AOV網(wǎng)絡(luò)構(gòu)造它的拓?fù)溆行蛐蛄?。即將各個(gè)頂點(diǎn)(代表各個(gè)活動(dòng))排列成一個(gè)線性有序的序列，使得AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。 （1）這種構(gòu)造AOV網(wǎng)絡(luò)全部頂點(diǎn)的拓?fù)溆行蛐蛄械倪\(yùn)算就叫做拓?fù)渑判颉?（2）如果通過拓?fù)渑判蚰軐OV網(wǎng)絡(luò)的所有頂點(diǎn)都排入一個(gè)拓?fù)溆行虻男蛄兄?，則該AOV網(wǎng)絡(luò)中必定不會(huì)出現(xiàn)有向環(huán)；相反，如果得不到滿足要求的拓?fù)溆行蛐蛄?，則說明AOV網(wǎng)絡(luò)中存在有向環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。 3. 為何需要采用循環(huán)隊(duì)列？n個(gè)空間的循環(huán)隊(duì)列，最多存儲(chǔ)多少個(gè)元素？為什么？答：循環(huán)隊(duì)列以克服順序隊(duì)列的"假上溢"現(xiàn)象，能夠使存儲(chǔ)隊(duì)列的向量空間得到充分的利用，所以采用循環(huán)隊(duì)列。n個(gè)空間的循環(huán)隊(duì)列，最多存儲(chǔ)n-1個(gè)元素，那是為了區(qū)別循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿的條件。隊(duì)空的條件是Q.front=Q.rear，而隊(duì)滿的條件是(Q.rear+1)%N=Q.front(N是數(shù)組中單元的總數(shù))，因此，Q.rear所指向的數(shù)組單元處于未用狀態(tài)。所以說，N個(gè)單元的數(shù)組所存放的循環(huán)隊(duì)列最大長度是N-1。4. 簡述堆的刪除算法，其刪除的是那個(gè)值？答：堆的刪除算法：首先，移除根節(jié)點(diǎn)的元素（并把根節(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)）比較當(dāng)前結(jié)點(diǎn)的兩個(gè)孩子結(jié)點(diǎn)的元素大小，把較大的那個(gè)元素移給當(dāng)前結(jié)點(diǎn)，接著把被移除元素的孩子結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)，并再比較當(dāng)前結(jié)點(diǎn)的孩子的大小，以此循環(huán)，直到最后一個(gè)葉子結(jié)點(diǎn)的值大于或等于當(dāng)前結(jié)點(diǎn)的孩子結(jié)點(diǎn)或孩子結(jié)點(diǎn)的位置超過了樹中元素的個(gè)數(shù)，則退出循環(huán)。最后把最后葉子結(jié)點(diǎn)的元素移給當(dāng)前結(jié)點(diǎn)。在堆的算法里面，刪除的值為根值。5. 線索二叉樹中，什么是線索，它是否唯一？可有根據(jù)什么順序得到？答：指向直接前驅(qū)結(jié)點(diǎn)和指向直接后續(xù)結(jié)點(diǎn)的指針被稱為線索（Thread），加了線索的二叉樹稱為線索二叉樹。線索二叉樹是唯一的，因?yàn)橹老刃虮闅v后，第一個(gè)根是唯一確定的，然后在中序遍歷里這個(gè)根將它分為兩個(gè)部分，第一個(gè)根的兩棵子樹的根也會(huì)唯一確定，依次此類推，所有子樹的根都唯一確定,二叉樹就是唯一的。6. 鏈?zhǔn)讲迦肱判驅(qū)Ρ戎苯硬迦肱判蛴泻蝺?yōu)點(diǎn)和缺點(diǎn)？答：鏈?zhǔn)讲迦肱判騼?yōu)點(diǎn)是速度極快，特別是在數(shù)據(jù)量大的時(shí)候效果尤為明顯；其缺點(diǎn)是在數(shù)據(jù)量少的情況下內(nèi)存相對消耗較多。直接插入排序優(yōu)點(diǎn)是排序比較簡單，穩(wěn)定性高；缺點(diǎ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->C->B->F->D->E8. 已知序列70,73,69,23,93,18,11,68,請給出直接插入排序作升序排序每一趟的結(jié)果和快速排序作為升序排序時(shí)一趟的結(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快速排序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下圖表示一個(gè)地區(qū)的交通網(wǎng)，頂點(diǎn)表示城市，邊表示連結(jié)城市間的公路，邊上的權(quán)表示修建公路花費(fèi)的代價(jià)。怎樣選擇能夠溝通每個(gè)城市且總造價(jià)最省的n-1條公路，畫出所有可能的方案。答：2113645111510. 已知一個(gè)無向圖的鄰接表如下圖所示： (1) 畫出這個(gè)圖。(2) 以v1為出發(fā)點(diǎn)，對圖進(jìn)行廣度優(yōu)先搜索和深度優(yōu)先搜索。給出搜索的結(jié)點(diǎn)序列。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è)計(jì)散列函數(shù)，取的較恰當(dāng)除數(shù)應(yīng)為多少。采用線性探測方法解決散列沖突，請構(gòu)造其散列表并將所有關(guān)鍵字入表。答：因?yàn)樯⒘斜黹L度為12，且除數(shù)應(yīng)盡量取基數(shù)；所以為11.經(jīng)檢驗(yàn)：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個(gè)桶，每個(gè)桶一個(gè)槽）112318697093731812. 用最短路徑算法Dijkstra計(jì)算單源多目標(biāo)最短路徑。圖中的“1”號(hào)結(jié)點(diǎn)為源結(jié)點(diǎn)。按提示圖表給出每一步計(jì)算時(shí)最短路徑的變化。10432101003050206010510答：dist6存放從頂點(diǎn)v0到其他各頂點(diǎn)的當(dāng)前最短路徑。Path6存放在最短路徑上該定點(diǎn)的前一頂點(diǎn)。S6存放以求得的在最短路徑上的定點(diǎn)集合V6存放所有頂點(diǎn)012345SV-SDistpath150111110,2,3,4,5Distpath6021111,20,3,4,5Distpath900160011,2,03,4,5Distpath150311031,2,0,34,5Distpath12051,2,0,3,54Distpath1,2,0,3,5,413.完成下面二叉搜索樹查找插入程序（說明含義）。此程序使用的是什么算法?根據(jù)給出的結(jié)點(diǎn)圖給出結(jié)點(diǎn)類的數(shù)據(jù)成員描述。LchilddataRchildtemplate <class Elem>bool BST<Elem>:search_and_insert( Binnode<Elem> *&sub_root, const Elem &new_data) if (sub_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ù)中引用一個(gè)指向Binnode指針sub_root和指向ELEM類型的指針new_data，如果指向Binonode的指針sub_root為空，則該指針指向一個(gè)帶ELEM類型數(shù)據(jù)的新結(jié)點(diǎn)。如果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作為引用指針。2 用堆排序方法將下列數(shù)據(jù)從小到大排序。以樹的形式給出前兩趟排序結(jié)果。（6分）35, 57,23,78, 6, 11答：A:輸入數(shù)值 B:初始堆7835 2357235711356116783557231135236116a堆大小=5b堆大小=4已排序=78已排序=57,7823116611A 堆大小=3b堆大小=2已排序=35,57,78已排序=23,35,57,78