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