【正文】 A．1 B．3 C．5 D．9 。表中已有四個(gè)記錄，關(guān)鍵字分別為13684，采用二次探測法解決沖突。 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)鍵字比較后，查找成功。二、選擇 1．在對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須 B 。 7．散列法中，如果兩個(gè)不同的關(guān)鍵字經(jīng)過散列函數(shù)的計(jì)算后，得到了相同的索引地址，那么這種現(xiàn)象被稱作“ 沖突 ”。 6．在散列查找中使用的函數(shù)，稱為“ 散列函數(shù) ”。 4．有序表和分塊有序表是一種 靜態(tài) 查找表；二叉查找樹是一種 動(dòng)態(tài) 查找表。 2．能夠唯一確定記錄的數(shù)據(jù)項(xiàng)，被稱為 關(guān)鍵字 。第8章習(xí)題解答一、填空1．記錄的集合是實(shí)施查找的數(shù)據(jù)基礎(chǔ)。 答：該網(wǎng)只有頂點(diǎn)v3的入度為0，所以只能從它開始進(jìn)行拓?fù)渑判?，其拓?fù)湫蛄袨椋? v3 v1 v4 v5 v2 v65．已知無向連通網(wǎng)的鄰接矩陣如下所示，試畫出該無向連通網(wǎng)以及所對(duì)應(yīng)的最小生成樹。如圖所示。3．利用Dijkstra算法，求圖726所示的圖中頂點(diǎn)v1到其他各頂點(diǎn)間的最短路徑長度。 2．利用Floyd算法，求圖725所示的有向網(wǎng)圖中各頂點(diǎn)對(duì)的最短路徑長度。這樣，該邊把MST里的頂點(diǎn)v6和v7連接在了一起，如圖(b)所示。 答：初始時(shí)，所求MST里只有七個(gè)各自孤立的連通分量，如圖(a)所示。 （8）如下圖(c)所示。 （6）如下圖(a)所示。 （4）一個(gè)長度為5的路徑是：v1 v2 v3 v6 v4 v5。 （2）邊集合E={ v1, v2, v2, v3, v2, v4, v3, v4, v3, v5, v4, v5, v3, v6, v4, v6}。 6．對(duì)圖724回答下列問題： （1）頂點(diǎn)集合V； （2）邊集合E； （3）每個(gè)頂點(diǎn)x的度D(x)；（4）一個(gè)長度為5的路徑； （5）一個(gè)長度為4的回路；（6）圖的一個(gè)生成樹； （7）鄰接矩陣； （8）鄰接表。那么，它們的主要區(qū)別是什么？ 答：這兩個(gè)算法的處理思路確實(shí)較為相似，主要區(qū)別在于：Prim算法是從VU里挑選出下一個(gè)與MST中某個(gè)頂點(diǎn)相距最近的頂點(diǎn)，而Dijkstra算法是從VU里挑選出下一個(gè)離源點(diǎn)最近的頂點(diǎn)。從頂點(diǎn)v1出發(fā)的深度優(yōu)先遍歷序列為：v1v2v4v5v7v6v3注意，該序列是不唯一的。 3．有如圖723所示的一個(gè)無向圖，給出它的鄰接矩陣以及從頂點(diǎn)v1出發(fā)的深度優(yōu)先遍歷序列。 答：簡單回路的定義是“如果一條路徑的第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，其他頂點(diǎn)不重復(fù)出現(xiàn)，那么這條路徑稱為簡單回路”；回路的定義是“如果一條路徑的第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，那么這條路徑稱為回路”。所以，MST不是唯一的。一個(gè)無向連通網(wǎng)圖的MST唯一嗎？ 圖722 無向連通網(wǎng)圖示例 圖723 無向圖示例 答：其MST如圖715(g)所示。 A．用鄰接表存儲(chǔ)圖，所用存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，與邊數(shù)無關(guān) B．用鄰接表存儲(chǔ)圖，所用存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，與頂點(diǎn)個(gè)數(shù)無關(guān) C．用鄰接矩陣存儲(chǔ)圖，所用存儲(chǔ)空間大小只與圖中頂點(diǎn)個(gè)數(shù)有關(guān)，與邊數(shù)無關(guān) D．用鄰接矩陣存儲(chǔ)圖，所用存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，與頂點(diǎn)個(gè)數(shù)無關(guān) 10．對(duì)如圖721所示的無向圖實(shí)施深度優(yōu)先搜索遍歷，可能的遍歷序列是 B 。 A．2n B．n C．n/2 D．0 8．一個(gè)有n個(gè)頂點(diǎn)的無向連通網(wǎng)圖，其生成樹里含有 C 條邊。 A．二分之一于 B．等于 C．兩倍于 D．四倍于 6．一個(gè)無向連通網(wǎng)圖的最小生成樹 A 。 A．n(n1) B．n(n+1) C．n(n1)/2 D．n(n+1)/2 4．在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和，是其所有邊數(shù)之和的 C 倍。 A．n(n1) B．n(n+1) C．n(n1)/2 D．n(n+1)/2 3．對(duì)于一個(gè)有向完全圖來說，它的每個(gè)不同頂點(diǎn)對(duì)之間，都存在有兩條弧。 A．n B．n+1 C．n1 D．n/2 2．對(duì)于一個(gè)無向完全圖來說，它的每個(gè)不同頂點(diǎn)對(duì)之間，都存在有一條邊。那么，在其鄰接表表示法中，鏈表結(jié)點(diǎn)數(shù)與單鏈表表頭結(jié)點(diǎn)數(shù)之和是 n+2e 。 14．拓?fù)渑判蚴堑玫紸OV網(wǎng)的一個(gè) 線性 序列，使得網(wǎng)中所有頂點(diǎn)間的優(yōu)先關(guān)系在序列中得以體現(xiàn)。12．只要在無向連通圖的生成樹里減少任意一條邊，它就成為了一個(gè) 非連通圖 。10．在無向圖G中，盡可能多地從集合V及E里收集頂點(diǎn)和邊，使它們成為該圖的一個(gè)極大的連通子圖，這個(gè)子圖就被稱為是無向圖G的一個(gè) 連通分量 。 8．在無向圖中，若從頂點(diǎn)vi到頂點(diǎn)vj之間有 路徑 存在，則稱vi與vj是連通的。 6．對(duì)于一個(gè)無向圖，其鄰接矩陣中第i行（或第i列）里非零或非∞元素的個(gè)數(shù)，正好是第i個(gè)頂點(diǎn)vi的 度 。 4．圖中頂點(diǎn)vi的“度”，是指與它 相鄰接 的頂點(diǎn)的個(gè)數(shù)，并記為D(vi)。 2．在一個(gè)具有4個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)，至少需要 3 條邊。6．將圖629所示的樹轉(zhuǎn)換成相對(duì)應(yīng)的二叉樹。5．將圖628所示的森林轉(zhuǎn)換成對(duì)應(yīng)的二叉樹。4．給出如圖627所示樹的先序遍歷序列和后序遍歷序列。3．將圖626所示的二叉樹轉(zhuǎn)換成相應(yīng)的森林。望能夠把兩者結(jié)合起來）；（3）孩子/兄弟鏈表表示法。 2．已知一棵樹如圖625所示。四、應(yīng)用 1．已知一棵樹的孩子鏈表表示法如圖624所示，試畫出該樹。 5．一棵度為2的樹與一棵二叉樹有什么區(qū)別？ 答：從形狀上看，一棵度為2的樹與一棵二叉樹沒有什么區(qū)別。所以，對(duì)一般的樹沒有中序遍歷。 3．為什么對(duì)于二叉樹有中序遍歷，而對(duì)一般樹卻沒有中序遍歷？答：二叉樹有中序遍歷，是因?yàn)槎鏄涞拿總€(gè)結(jié)點(diǎn)最多只有兩個(gè)子樹，且子樹有左、右之分，因此可以規(guī)定在訪問左子樹和右子樹的中間去訪問子樹的根結(jié)點(diǎn)。圖623 樹示例2．二叉樹與樹有什么不同？ 答：二叉樹是一種樹，但是一種特殊的樹。從圖623(b)知，該樹的根結(jié)點(diǎn)也是A，它的下面也有兩棵子樹，這兩棵子樹的構(gòu)成也與圖623(a)里的相同。 A．0 B．n C．n+1 D．n+2 9．下列說法中，正確的是 A 。 7．一棵有n個(gè)結(jié)點(diǎn)的樹，在把它轉(zhuǎn)換成對(duì)應(yīng)的二叉樹之后，該二叉樹根結(jié)點(diǎn)的左子樹上共有 B 個(gè)結(jié)點(diǎn)。在11個(gè)結(jié)點(diǎn)里，減去度為1的結(jié)點(diǎn)數(shù)5，剩下的就是度為0的結(jié)點(diǎn)。 A．5 B．8 C．6 D．9 注意：有n個(gè)結(jié)點(diǎn)的樹，樹中所有結(jié)點(diǎn)的度之和為n1。 A．n11 B．n1 C．n1+1 D．n1+n2 6．現(xiàn)有一棵度為3的樹，它有兩個(gè)度為3的結(jié)點(diǎn)，一個(gè)度為2的結(jié)點(diǎn)，兩個(gè)度為1的結(jié)點(diǎn)。與該森林相應(yīng)的二叉樹為Bt。把該森林轉(zhuǎn)換成對(duì)應(yīng)的二叉樹后，該二叉樹的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是 D 。 A．先序遍歷 B．中序遍歷 C．后序遍歷 D．無法確定 3．將一棵樹Tr轉(zhuǎn)換成相應(yīng)的二叉樹Bt，那么對(duì)Tr的后序遍歷是對(duì)Bt的 B 。把它還原成森林，應(yīng)該是 D 。它的根結(jié)點(diǎn)是 A ，葉結(jié)點(diǎn)是 E、G、I、J、K、L、N、O、P、Q、R ，這棵樹的度是 3 ，這棵樹的深度是 4 ，結(jié)點(diǎn)F的孩子結(jié)點(diǎn)是 J、K ，結(jié)點(diǎn)G的父結(jié)點(diǎn)是 C ，結(jié)點(diǎn) M、H、D、A 是結(jié)點(diǎn)R的祖先。 圖621 樹示例 圖622 樹示例 10．在樹中，一個(gè)結(jié)點(diǎn)的孩子個(gè)數(shù)，稱為該結(jié)點(diǎn)的 度 。 8．在數(shù)據(jù)結(jié)構(gòu)中，把n（n≥0）棵互不相交的樹的集合稱為 森林 。 6．所謂結(jié)點(diǎn)的深度，即是指該結(jié)點(diǎn)位于樹的 層次 數(shù)。 4．樹中一個(gè)結(jié)點(diǎn)的子樹中的任何結(jié)點(diǎn)，都被稱作是該結(jié)點(diǎn)的 子孫 結(jié)點(diǎn)。 2．樹中除根結(jié)點(diǎn)外，其他結(jié)點(diǎn)有且只有 一個(gè) 前驅(qū)結(jié)點(diǎn)，但可以有 零個(gè)或多個(gè) 后繼結(jié)點(diǎn)。序 號(hào)1234567891011Lchild6^7^8^5^2^^DataMFAKBLCRDSERchild^^^9^10411^^^ 答：二叉樹如圖所示，先序遍歷序列為：ACBRSEDFMLK，中序遍歷序列為：RBSCEAFDLKM，后序遍歷序列為：RSBECFKLMDA。7．一棵有11個(gè)結(jié)點(diǎn)的二叉樹的順序存儲(chǔ)情況如表所示，序號(hào)3的結(jié)點(diǎn)是根結(jié)點(diǎn)。 6．權(quán)值序列為：124，請(qǐng)用圖示來表達(dá)構(gòu)造一棵哈夫曼樹的全過程。試給出第2次組合后數(shù)組的情形，以及那時(shí)二叉樹的樣子。 5．理解算法510。請(qǐng)畫出這棵二叉樹。 答：這棵二叉樹如應(yīng)用題3答案圖所示。 3．已知前序遍歷序列為：ABCDEF，中序遍歷序列為：CBAEDF。試畫出這棵二叉樹。其先序遍歷序列是：ABDEGHCF；中序遍歷序列是：DBGEHACF；后許遍歷序列是：DGHEBFCA。四、應(yīng)用 1．對(duì)一個(gè)二叉樹進(jìn)行順序存儲(chǔ)，各結(jié)點(diǎn)的編號(hào)及數(shù)據(jù)如表所示：編號(hào)i1234571011數(shù)據(jù)xABCDEFGH 試畫出對(duì)應(yīng)的二叉樹，并給出先序、中序、后序遍歷該二叉樹后，所得到的各種結(jié)點(diǎn)序列。7．分別寫出如圖532所示二叉樹的先序、中序、后序遍歷序列。這可能嗎？如果可能的話，這樣一棵二叉樹應(yīng)該是個(gè)什么樣子呢？ 答：這是完全可能的，這種二叉樹是從根結(jié)點(diǎn)開始只有左子樹，或只有右子樹的單支二叉樹，如圖所示。所以，此人說的結(jié)論是完全正確的。對(duì)于滿二叉樹來說，所有的分支結(jié)點(diǎn)都是度為2的結(jié)點(diǎn)。這樣的一個(gè)結(jié)論正確嗎？請(qǐng)說明理由。 3．一棵高度為3的滿二叉樹有多少個(gè)葉結(jié)點(diǎn)？有多少個(gè)度為2的結(jié)點(diǎn)？總共有多少個(gè)結(jié)點(diǎn)？ 答：有23=8個(gè)葉結(jié)點(diǎn)，有度為2的結(jié)點(diǎn)231=7個(gè)，總共有23+11=241=15個(gè)結(jié)點(diǎn)。 2． 請(qǐng)畫出由3個(gè)結(jié)點(diǎn)構(gòu)成的所有二叉樹，它們的高度分別是多少？ 答：大小為3的不同的二叉樹共有5種，如下圖所示。如果一棵二叉樹不是完全二叉樹，那么它絕對(duì)不可能是一棵滿二叉樹。 A．6 B．7 C．8 D．9 10．在一棵二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最多是 C 個(gè)。 A．18 B．28 C．19 D．29 9．一棵二叉樹度2的結(jié)點(diǎn)數(shù)為7，度1的結(jié)點(diǎn)數(shù)為6。 A．只有左子樹上的部分 B．只有左子樹上的所有 C．只有右子樹上的部分 D．只有右子樹上的所有 7．在任何一棵二叉樹的各種遍歷序列中，葉結(jié)點(diǎn)的相對(duì)次序是 A 。 A．無左、右孩子 B．有左孩子，無右孩子 C．有右孩子，無左孩子 D．有左、有孩子 5．深度為6的二叉樹，最多可以有 A 個(gè)結(jié)點(diǎn)。 A．10 B．8 C．6 D．4 3．設(shè)有一棵5個(gè)結(jié)點(diǎn)的二叉樹，其先序遍歷序列為：ABCDE，中序遍歷序列為：BADCE，那么它的后序遍歷序列為 B 。二、選擇1．在所給的4棵二叉樹中， C 不是完全二叉樹。 10．在二叉樹中，有一個(gè)結(jié)點(diǎn)具有左、右兩個(gè)孩子。那么在所有存儲(chǔ)結(jié)點(diǎn)里，一共會(huì)有 2n 個(gè)指針域，其中有 n+1 個(gè)指針域是空的。那么，對(duì)編號(hào)為i的結(jié)點(diǎn)，如果有左孩子，則左孩子的編號(hào)應(yīng)該是 2i ；如果有右孩子，則右孩子的編號(hào)應(yīng)該是 2i+1 。 6．由n個(gè)帶權(quán)值的葉結(jié)點(diǎn)生成的哈夫曼樹，最終共有 2n1個(gè)結(jié)點(diǎn)。 4．如果一棵滿二叉樹的深度為6，那么它共有 127 個(gè)結(jié)點(diǎn)，有 64 個(gè)葉結(jié)點(diǎn)。 2．給定二叉樹的結(jié)點(diǎn)數(shù)，要使樹高為最大，那么該樹應(yīng)該是 單枝 形狀。 j++) C[i][j] = A[i][j] + B[i][j]。 i++) for (j=1。Add_Mt(A, B, C){ for (i=1。編寫一個(gè)算法，求C=A+B。} 算法是通過while循環(huán)，不斷修改指針ptr，以便指向鏈串Lt1的各個(gè)結(jié)點(diǎn)；指針rtr總是指向當(dāng)前已形成的新鏈串Lt2的最后一個(gè)結(jié)點(diǎn)；用指針qtr指向剛申請(qǐng)到的新存儲(chǔ)結(jié)點(diǎn)，并把它鏈入到rtr所指結(jié)點(diǎn)的后面。}rtrNext=NULL。 rtrNext=qtr。while (ptr != NULL){ qtr=malloc(size)。Lt2_h=rtr。rtr=malloc(size)。具體編寫如下。 答：復(fù)制一個(gè)完整的鏈串，是一件比較容易的事情。 free(ptr)。 j++){ ptr=rtr。for (j=1。請(qǐng)?jiān)囍凑者@一思路改寫那一小段算法。 把由指針ptr指向的最后一個(gè)要釋放空間的結(jié)點(diǎn)的Next域設(shè)置為NULL，然后通過while循環(huán)完成釋放。 /* 安放新的串結(jié)束符 */}elseprintf (“參數(shù)不合理，無法進(jìn)行刪除！”)。 St_len=St_lenj。 k=St_len。（提示：先要判斷所給參數(shù)是否合理，然后通過將第i+j開始往后的字符全部移動(dòng)j個(gè)位置，完成刪除的功能） 答：算法編寫如下。(St[i]=Z))