【正文】 樹。第一，二叉樹的每個(gè)結(jié)點(diǎn)至多可以有兩棵子樹，但樹的每個(gè)結(jié)點(diǎn)可以有多棵子樹；第二，二叉樹的子樹有左、右之分（即是有序的），但樹的子樹通常是不分順序的。 3．為什么對(duì)于二叉樹有中序遍歷，而對(duì)一般樹卻沒(méi)有中序遍歷？答：二叉樹有中序遍歷，是因?yàn)槎鏄涞拿總€(gè)結(jié)點(diǎn)最多只有兩個(gè)子樹，且子樹有左、右之分，因此可以規(guī)定在訪問(wèn)左子樹和右子樹的中間去訪問(wèn)子樹的根結(jié)點(diǎn)。但對(duì)于一般的樹，其結(jié)點(diǎn)可以有任意數(shù)目的子樹，因此，無(wú)法規(guī)定怎樣的訪問(wèn)順序才算是“中序”。所以，對(duì)一般的樹沒(méi)有中序遍歷。 4．對(duì)于樹的各種遍歷，哪一種遍歷是（1）首先訪問(wèn)樹的根結(jié)點(diǎn)？（2）位于最左邊的結(jié)點(diǎn)最先訪問(wèn)？（3）根結(jié)點(diǎn)最后訪問(wèn)？（4）最右邊的結(jié)點(diǎn)最后訪問(wèn)？答：（1）層次遍歷和先序遍歷總是首先訪問(wèn)樹的根結(jié)點(diǎn)；（2）后序遍歷總是最先訪問(wèn)位于樹最左邊的結(jié)點(diǎn)；（3）后序遍歷總是最后訪問(wèn)樹的根結(jié)點(diǎn)；（4）前序遍歷總是最后訪問(wèn)樹的最右邊的結(jié)點(diǎn)。 5．一棵度為2的樹與一棵二叉樹有什么區(qū)別？ 答：從形狀上看，一棵度為2的樹與一棵二叉樹沒(méi)有什么區(qū)別。但度為2的樹結(jié)點(diǎn)的子樹一般是無(wú)序的，沒(méi)有左、右之分；而二叉樹結(jié)點(diǎn)的子樹是有序的，它們之間有左、右之分，不能隨意換位。四、應(yīng)用 1．已知一棵樹的孩子鏈表表示法如圖624所示，試畫出該樹。 圖624 一棵樹的孩子鏈表表示法 圖625 樹示例 答：該樹形狀如下圖所示。 2．已知一棵樹如圖625所示。請(qǐng)畫出該樹的以下存儲(chǔ)結(jié)構(gòu)：（1）雙親表示法；（2）帶雙親的孩子鏈表表示法（我們介紹過(guò)雙親表示法和孩子鏈表表示法，沒(méi)有介紹過(guò)帶雙親的孩子鏈表表示法。望能夠把兩者結(jié)合起來(lái)）；（3）孩子/兄弟鏈表表示法。 答：（1）雙親表示法如下圖(a)所示；（2）帶雙親的孩子鏈表表示法如圖下(b)所示；（3）孩子/兄弟鏈表表示法如下圖(c)所示。3．將圖626所示的二叉樹轉(zhuǎn)換成相應(yīng)的森林。 圖626 二叉樹示例 圖627 樹示例 答：轉(zhuǎn)換成的森林如下圖所示。4．給出如圖627所示樹的先序遍歷序列和后序遍歷序列。 答：該樹的先序遍歷序列為：ABEFKLMCGDHIJ；該樹的后序遍歷序列是：EKMLFBGCHIJDA。5．將圖628所示的森林轉(zhuǎn)換成對(duì)應(yīng)的二叉樹。 圖628 森林示例 圖629 樹示例答：對(duì)應(yīng)的二叉樹如下圖所示。6．將圖629所示的樹轉(zhuǎn)換成相對(duì)應(yīng)的二叉樹。答：對(duì)應(yīng)的二叉樹如下圖所示第7章習(xí)題解答一、填空1．由4個(gè)頂點(diǎn)組成的一個(gè)連通圖，應(yīng)該有邊 6 條。 2．在一個(gè)具有4個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)，至少需要 3 條邊。 3．在無(wú)向圖中，若頂點(diǎn)vi和vj之間有一條邊（vi，vj）存在，那么則稱頂點(diǎn)vi和vj互為 鄰接 點(diǎn)。 4．圖中頂點(diǎn)vi的“度”，是指與它 相鄰接 的頂點(diǎn)的個(gè)數(shù)，并記為D(vi)。 5．在有向圖中，把從頂點(diǎn)vi到頂點(diǎn)vj的弧記為 vi，vj ，而把從頂點(diǎn)vj到頂點(diǎn)vi的弧記為 vj，vi ，這是兩條不同的弧。 6．對(duì)于一個(gè)無(wú)向圖，其鄰接矩陣中第i行（或第i列）里非零或非∞元素的個(gè)數(shù)，正好是第i個(gè)頂點(diǎn)vi的 度 。 7．對(duì)于一個(gè)有向圖，其鄰接矩陣中第i行里非零或非∞元素的個(gè)數(shù)，正好是第i個(gè)頂點(diǎn)vi的 出度 ；其鄰接矩陣中第i列里非零或非∞元素的個(gè)數(shù)，正好是第i個(gè)頂點(diǎn)vi的 入度 。 8．在無(wú)向圖中，若從頂點(diǎn)vi到頂點(diǎn)vj之間有 路徑 存在，則稱vi與vj是連通的。 9．如果無(wú)向圖G中 任意 一對(duì)頂點(diǎn)之間都是連通的，則稱該圖G為連通圖，否則是非連通圖。10．在無(wú)向圖G中，盡可能多地從集合V及E里收集頂點(diǎn)和邊，使它們成為該圖的一個(gè)極大的連通子圖，這個(gè)子圖就被稱為是無(wú)向圖G的一個(gè) 連通分量 。 11．包含無(wú)向連通圖G的所有n個(gè)頂點(diǎn)在內(nèi)的極小連通子圖，是這個(gè)圖的 生成樹 。12．只要在無(wú)向連通圖的生成樹里減少任意一條邊，它就成為了一個(gè) 非連通圖 。 13．對(duì)圖的廣度優(yōu)先搜索，類似于對(duì)樹進(jìn)行 按層次 遍歷。 14．拓?fù)渑判蚴堑玫紸OV網(wǎng)的一個(gè) 線性 序列，使得網(wǎng)中所有頂點(diǎn)間的優(yōu)先關(guān)系在序列中得以體現(xiàn)。 15．已知無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，邊數(shù)為e。那么，在其鄰接表表示法中，鏈表結(jié)點(diǎn)數(shù)與單鏈表表頭結(jié)點(diǎn)數(shù)之和是 n+2e 。二、選擇 1．在一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)，至少需要 C 條邊。 A．n B．n+1 C．n1 D．n/2 2．對(duì)于一個(gè)無(wú)向完全圖來(lái)說(shuō)，它的每個(gè)不同頂點(diǎn)對(duì)之間，都存在有一條邊。因此，有n個(gè)頂點(diǎn)的無(wú)向完全圖包含有 C 條邊。 A．n(n1) B．n(n+1) C．n(n1)/2 D．n(n+1)/2 3．對(duì)于一個(gè)有向完全圖來(lái)說(shuō)，它的每個(gè)不同頂點(diǎn)對(duì)之間，都存在有兩條弧。因此，有n個(gè)頂點(diǎn)的有向完全圖包含有 A 條邊。 A．n(n1) B．n(n+1) C．n(n1)/2 D．n(n+1)/2 4．在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和，是其所有邊數(shù)之和的 C 倍。 A．1/2 B．1 C．2 D．4 5．在一個(gè)有向圖中，所有頂點(diǎn)的入度之和 B 所有頂點(diǎn)的出度之和。 A．二分之一于 B．等于 C．兩倍于 D．四倍于 6．一個(gè)無(wú)向連通網(wǎng)圖的最小生成樹 A 。 A．有一棵或多棵 B．只有一棵 C．一定有多棵 D．可能不存在 7．一個(gè)無(wú)向圖有n個(gè)頂點(diǎn)，那么該圖擁有的邊數(shù)至少是 D 。 A．2n B．n C．n/2 D．0 8．一個(gè)有n個(gè)頂點(diǎn)的無(wú)向連通網(wǎng)圖，其生成樹里含有 C 條邊。 A．4n1 B．2n1 C．n1 D．n/2 9．下面關(guān)于圖的存儲(chǔ)的敘述中，正確的是 C 。 A．用鄰接表存儲(chǔ)圖，所用存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，與邊數(shù)無(wú)關(guān) B．用鄰接表存儲(chǔ)圖，所用存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，與頂點(diǎn)個(gè)數(shù)無(wú)關(guān) C．用鄰接矩陣存儲(chǔ)圖，所用存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，與邊數(shù)無(wú)關(guān) D．用鄰接矩陣存儲(chǔ)圖，所用存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，與頂點(diǎn)個(gè)數(shù)無(wú)關(guān) 10．對(duì)如圖721所示的無(wú)向圖實(shí)施深度優(yōu)先搜索遍歷，可能的遍歷序列是 B 。圖721 無(wú)向圖示例三、問(wèn)答1． 試求圖722所示的無(wú)向連通網(wǎng)圖的MST。一個(gè)無(wú)向連通網(wǎng)圖的MST唯一嗎？ 圖722 無(wú)向連通網(wǎng)圖示例 圖723 無(wú)向圖示例 答：其MST如圖715(g)所示。如果使用邊（v4, v6）代替邊（v3, v6），就可以得到另一個(gè)MST。所以，MST不是唯一的。 2．試述簡(jiǎn)單回路、回路兩者間的聯(lián)系與不同。 答：簡(jiǎn)單回路的定義是“如果一條路徑的第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，其他頂點(diǎn)不重復(fù)出現(xiàn)，那么這條路徑稱為簡(jiǎn)單回路”；回路的定義是“如果一條路徑的第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，那么這條路徑稱為回路”。比較后可知，一條路徑是簡(jiǎn)單回路，那么它一定是回路，因?yàn)榛芈分灰舐窂降钠鹗柬旤c(diǎn)和終端頂點(diǎn)相同，簡(jiǎn)單路徑是滿足這一要求的；但一條路徑是回路，則不一定是簡(jiǎn)單回路，因?yàn)榛芈窌r(shí)并不去理會(huì)路徑中的其他頂點(diǎn)是否重復(fù)出現(xiàn)，可是簡(jiǎn)單路徑是不允許其他頂點(diǎn)重復(fù)出現(xiàn)的。 3．有如圖723所示的一個(gè)無(wú)向圖，給出它的鄰接矩陣以及從頂點(diǎn)v1出發(fā)的深度優(yōu)先遍歷序列。答：它的鄰接矩陣如圖所示。從頂點(diǎn)v1出發(fā)的深度優(yōu)先遍歷序列為：v1v2v4v5v7v6v3注意，該序列是不唯一的。 4．構(gòu)造最小生成樹的Prim算法與求單源最短路徑的Dijkstra算法十分相似，它們都把圖中的頂點(diǎn)分成U和VU兩個(gè)部分，都是在VU里挑選出一個(gè)頂點(diǎn)，并將它從VU移到U中。那么，它們的主要區(qū)別是什么？ 答：這兩個(gè)算法的處理思路確實(shí)較為相似，主要區(qū)別在于：Prim算法是從VU里挑選出下一個(gè)與MST中某個(gè)頂點(diǎn)相距最近的頂點(diǎn)，而Dijkstra算法是從VU里挑選出下一個(gè)離源點(diǎn)最近的頂點(diǎn)。 5．對(duì)有m個(gè)頂點(diǎn)的無(wú)向圖G，如何通過(guò)它的鄰接矩陣判定下列問(wèn)題： （1）圖中有多少條邊？ （2）任意兩個(gè)頂點(diǎn)i和j之間是否有邊相連？ （3）任意一個(gè)頂點(diǎn)i的度是多少？ 答：（1）鄰接矩陣中非零元素個(gè)數(shù)的一半，是圖中邊的數(shù)目；（2）通過(guò)判斷鄰接矩陣中元素A{[i,j]和A[j,i]是否不為0，可知頂點(diǎn)i和j之間是否有邊相連；（3）第i行或第i列上非零元素的個(gè)數(shù)，就是頂點(diǎn)i的度。 6．對(duì)圖724回答下列問(wèn)題： （1）頂點(diǎn)集合V； （2）邊集合E； （3）每個(gè)頂點(diǎn)x的度D(x)；（4）一個(gè)長(zhǎng)度為5的路徑； （5）一個(gè)長(zhǎng)度為4的回路；（6）圖的一個(gè)生成樹； （7）鄰接矩陣； （8）鄰接表。圖724 圖示例 答：（1）頂點(diǎn)集合V={v1, v2, v3, v4, v5, v6}。 （2）邊集合E={ v1, v2, v2, v3, v2, v4, v3, v4, v3, v5, v4, v5, v3, v6, v4, v6}。 （3）每個(gè)頂點(diǎn)的度：D(v1)=1，D(v2)=3，D(v3)=D(v4)=4，D(v5)=D(v6)=2。 （4）一個(gè)長(zhǎng)度為5的路徑是：v1 v2 v3 v6 v4 v5。 （5）一個(gè)長(zhǎng)度為4的回路是：v2 v3 v5 v4 v2。 （6）如下圖(a)所示。 （7）如下圖(b)所示。 （8）如下圖(c)所示。問(wèn)答5的（6）~（8）答案四、應(yīng)用 1．利用Kruskal算法，求圖714(a)所給無(wú)向連通網(wǎng)圖的最小生成樹。 答：初始時(shí)，所求MST里只有七個(gè)各自孤立的連通分量，如圖(a)所示。開始執(zhí)行Kruskal算法時(shí)，從圖的邊E里挑選邊（v6,v7），因?yàn)檫@兩個(gè)頂點(diǎn)分屬M(fèi)ST中的不同連通分量，且權(quán)值為最小。這樣，該邊把MST里的頂點(diǎn)v6和v7連接在了一起，如圖(b)所示。接著，從圖的邊E里挑選邊（v1,v3）、挑選邊（v1,v2）、挑選邊（v4,v6）挑選邊（v5,v7）挑選邊（v3,v6），最終得到如圖(g)所示的最小生成樹。 2．利用Floyd算法，求圖725所示的有向網(wǎng)圖中各頂點(diǎn)對(duì)的最短路徑長(zhǎng)度。圖725 有向網(wǎng)圖示例 答：Floyd算法基于的鄰接矩陣，以及推演出的各個(gè)矩陣、最終結(jié)果如下所示。3．利用Dijkstra算法，求圖726所示的圖中頂點(diǎn)v1到其他各頂點(diǎn)間的最短路徑長(zhǎng)度。 答：v1到v2的最短路徑長(zhǎng)度是4；v1到v3的最短路徑長(zhǎng)度是4；v1到v4的最短路徑長(zhǎng)度是1；v1到v5的最短路徑長(zhǎng)度是6；v1到v6的最短路徑長(zhǎng)度是3；v1到v7的最短路徑長(zhǎng)度是6；v1到v8的最短路徑長(zhǎng)度是7。如圖所示。 圖726 圖示例 圖727 AOV網(wǎng)4．寫出圖727所示的AOV網(wǎng)的拓?fù)渑判蛐蛄小?答：該網(wǎng)只有頂點(diǎn)v3的入度為0，所以只能從它開始進(jìn)行拓?fù)渑判?，其拓?fù)湫蛄袨椋? v3 v1 v4 v5 v2 v65．已知無(wú)向連通網(wǎng)的鄰接矩陣如下所示，試畫出該無(wú)向連通網(wǎng)以及所對(duì)應(yīng)的最小生成樹。 答：無(wú)向連通網(wǎng)以及所對(duì)應(yīng)的最小生成樹如圖(a)、(b)所示。第8章習(xí)題解答一、填空1．記錄的集合是實(shí)施查找的數(shù)據(jù)基礎(chǔ)。在討論查找問(wèn)題時(shí)，常把T稱為 查找表 。 2．能夠唯一確定記錄的數(shù)據(jù)項(xiàng)，被稱為 關(guān)鍵字 。 3．如果查找只是為了得知是否成功或獲取相應(yīng)的記錄信息，并不去改變查找表的內(nèi)容，那么這種查找稱為 靜態(tài) 查找；如果查找過(guò)程會(huì)伴隨著對(duì)數(shù)據(jù)元素的變更，那么這種查找稱為 動(dòng)態(tài) 查找。 4．有序表和分塊有序表是一種 靜態(tài) 查找表；二叉查找樹是一種 動(dòng)態(tài) 查找表。5．在AVL樹的平衡調(diào)整中，稱離插入結(jié)點(diǎn)最近且其平衡因子絕對(duì)值大于1的那個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹為“　最小不平衡樹　”。 6．在散列查找中使用的函數(shù)，稱為“ 散列函數(shù) ”。在散列法中的查找表，稱為散列表或哈希表。 7．散列法中，如果兩個(gè)不同的關(guān)鍵字經(jīng)過(guò)散列函數(shù)的計(jì)算后，得到了相同的索引地址，那么這種現(xiàn)象被稱作“ 沖突 ”。8．散列法中，計(jì)算后得到相同索引地址的那些不同關(guān)鍵字，被稱作“ 同義詞 ”。二、選擇 1．在對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須 B 。 A．以順序方式存儲(chǔ)B．以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列C．以鏈?zhǔn)椒绞酱鎯?chǔ)D．以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列 2．采用順序查找法查找長(zhǎng)度為n的線性表時(shí)，其平均查找長(zhǎng)度為 C 。 A．n B．n/2 C．(n+1)/2 D．(n1)/2 3．有一個(gè)有序表： 1，3，9，12，32，41，45，62，75，77，82，95，100采用折半查找法查找值為82的記錄時(shí)，要經(jīng) C 次關(guān)鍵字比較后，查找成功。 A．1 B．2 C．4 D．8 4．設(shè)散列表長(zhǎng)m=14，散列函數(shù)h(key)=key%11。表中已有四個(gè)記錄，關(guān)鍵字分別為13684，采用二次探測(cè)法解決沖突。那么關(guān)鍵字為49的記錄的散列地址為 D 。 A．1 B．3 C．5 D．9