數(shù)據(jù)結(jié)構(gòu)與算法 習題及解答 機械自考版 -第5-8章 樹與二叉樹-查找

第五章樹與二叉樹一、單項選擇題1．下列關(guān)于二叉樹的敘述中，正確的是________。A．二叉樹的度為2 B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個結(jié)點的度為2 D．二叉樹中任何一個結(jié)點的度都為2答案：B。樹中結(jié)點的度的最大值是樹的度。對于二叉樹，每個結(jié)點的度可以是0、1或2。如果二叉樹僅含有根結(jié)點，則它的度為0。如果二叉樹中所有分支結(jié)點均僅含有一個子結(jié)點，則二叉樹的度為1。如果二叉樹中有的分支結(jié)點含有2個子結(jié)點，則二叉樹的度為2。所以二叉樹的度可以是0，可以是1，也可以是2。2．下列存儲形式中，不是樹的存儲形式的是________。A．父結(jié)點表示法 B．孩子結(jié)點表示法C．孩子-兄弟表示法 D．順序存儲表示法答案：D。二叉樹有順序存儲表示，它針對每層的最多結(jié)點數(shù)，在數(shù)組中預(yù)留出相應(yīng)的位置。但對于樹而言，因為每層結(jié)點的個數(shù)沒有上限，所以沒有辦法在數(shù)組中預(yù)留空間。另外三種存儲形式都是樹的存儲形式。3．下列關(guān)于二叉樹的敘述中，正確的是________。I．只有一個結(jié)點的二叉樹的度為0II．二叉樹的度為2III．二叉樹的左右子樹可任意交換IV．深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹A．僅I、IV B．僅II、IV C．僅I、II、III D．僅II、III、IV答案：A。單結(jié)點的二叉樹只含有根結(jié)點，這個結(jié)點也是葉結(jié)點，度為0，所以樹的度為0。I是正確的。但二叉樹中結(jié)點的度可以是0、1或2，所以樹的度不一定必須是2。II不正確。二叉樹中左子樹與右子樹是不同的，不能任意交換。III不正確。滿二叉樹是完全二叉樹的特例，深度一樣的完全二叉樹與滿二叉樹，只在最后一層可能存在差異，在這一層上，完全二叉樹可能是不滿的，而滿二叉樹一定是滿的，前面的所有層中，完全二叉樹的結(jié)點個數(shù)與滿二叉樹的結(jié)點個數(shù)都是相同的。IV是正確的。4．一棵二叉樹共有20個結(jié)點，其中度為l的結(jié)點個數(shù)是7個，則葉結(jié)點個數(shù)是________。A．4 B．7 C．9 D．13答案：B。二叉樹中，設(shè)n0是葉結(jié)點的個數(shù)，n1是度為1的結(jié)點的個數(shù)，n2是度為2的結(jié)點的個數(shù)，由性質(zhì)3可知，n0=n2+1，由題目條件知n1=7，則n0+n2=20-n1=13，解得n0=7。5．深度為4的二叉樹中，結(jié)點個數(shù)最多是________。A．10 B．16 C．31 D．32答案：C。相同高度的滿二叉樹中結(jié)點個數(shù)最多。深度為4的滿二叉樹的高度是5。6．對含n個結(jié)點的完全二叉樹從上到下且從左至右進行1至n編號，根結(jié)點編號為1，則對樹中任意一個編號為i的結(jié)點，正確的是________。A．若2i>=n，則結(jié)點i無左子結(jié)點B．若2i+1>=n，則結(jié)點i無右子結(jié)點C．若i為偶數(shù)，則i是其父結(jié)點的左子結(jié)點D．若i為奇數(shù)，則i是其父結(jié)點的右子結(jié)點答案：C。按照題目中給出的編號規(guī)則，結(jié)點i的左子結(jié)點是2i，右子結(jié)點是2i+1，故選項A和B中，不等式中取等號時，結(jié)論是錯誤的。反過來看，偶數(shù)編號的結(jié)點是其父結(jié)點的左子結(jié)點，奇數(shù)編號的結(jié)點是其父結(jié)點的右子結(jié)點，唯一的例外是根結(jié)點，根的編號是奇數(shù)，沒有父結(jié)點，所以選項D也是錯誤的。7．采用順序存儲方式保存一棵二叉樹，根結(jié)點保存在數(shù)組的A[0]中，若編號為i結(jié)點有右子結(jié)點，則該子結(jié)點的下標為________。A．2i-1 B．2i C．2i+1 D．2i+2答案：D?；靖拍睢Ｏ聵藦?開始。8．在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊________。A．只有左子樹上的所有結(jié)點 B．只有右子樹上的所有結(jié)點C．只有左子樹上的部分結(jié)點 D．只有右子樹上的部分結(jié)點答案：B。中序遍歷序列中，根的前面是左子樹中所有結(jié)點的中序遍歷序列，后面是右子樹中所有結(jié)點的中序遍歷序列。9．若一棵滿二叉樹有m個葉結(jié)點，n個結(jié)點，高度為h，則下列關(guān)系式中正確的是________。A．h+m==2n B．n==h+m C．m==h-1 D．n==2h-1答案：D。滿二叉樹中，高度為h時，結(jié)點個數(shù)n=2h-1。10．一棵二叉樹高度為h，所有結(jié)點的度或為0或為2，則這棵二叉樹的結(jié)點數(shù)最少為________。A．h+1 B．2h-1 C．2h D．2h+1答案：B?；靖拍?。沒有度為1的結(jié)點，滿二叉樹中結(jié)點個數(shù)最多。11．設(shè)n、m為二叉樹T中的兩個結(jié)點，在中序遍歷序列中，n出現(xiàn)在m之前的條件是________。A．n在m左側(cè) B．n在m右側(cè) C．n是m子孫 D．n是m祖先答案：A。將二叉樹中的各結(jié)點向下投影成一個序列，二叉樹中若結(jié)點n在m的左側(cè)，則中序遍歷時先遍歷到n后遍歷到m。12．由3個結(jié)點可以構(gòu)造出不同形態(tài)的二叉樹的數(shù)量是________。A．3個 B．4個 C．5個 D．6個答案：C。基本概念。13．下列四個序列中，能構(gòu)成最大堆的是________。A．75,65,30,15,25,45,20,10 B．75,65,45,10,30,25,20,15C．75,45,65,30,15,25,20,10 D．75,45,65,10,25,30,20,15答案：C。將4個選項中給定的數(shù)據(jù)序列對應(yīng)到完全二叉樹中。如圖5-1所示?？梢钥闯?，選項C對應(yīng)的是堆，且是最大堆。b)選項b)選項B對應(yīng)的完全二叉樹7565103020254515a)選項A對應(yīng)的完全二叉樹7565152520453010c)選項c)選項C對應(yīng)的完全二叉樹7545301520256510d)選項D對應(yīng)的完全二叉樹7545102520306515圖5-1各圖5-1各選項對應(yīng)的完全二叉樹選項A中，元素30既小于其父結(jié)點75，也小于其左子結(jié)點45。選項B中，元素10既小于其父結(jié)點65，也小于其左子結(jié)點15。選項D中，元素10既小于其父結(jié)點45，也小于其左子結(jié)點15。都不符合堆的定義。14．在13題的最大堆中刪除堆頂后，得到的最大堆是________。A．65,30,15,25,45,20,10 B．65,45,25,30,15,10,20C．65,45,30,15,25,20,10 D．65,45,10,25,30,20,15答案：B。圖圖5-2刪除堆頂后的新堆65453015201025刪除堆頂75后，由最后一個元素10遞補，然后進行整堆，10先后與65、25進行交換，得到的新堆如圖5-2所示。15．在13題的最大堆中插入新元素55后，得到的最大堆是________。A．75,55,65,45,15,25,20,10,30 B．75,65,55,45,10,30,25,20,15C．75,55,45,65,30,15,25,20,10 D．75,45,65,55,10,25,30,20,15答案：A。新元素55先保存在最后的位置，作為30的右子結(jié)點。由于55大于30，故兩者相交換。同樣的原因，55與45相交換。得到最終的新堆，如圖5-3所示。圖圖5-3插入新元素后的新堆7555451520256510303016．與樹的后根遍歷序列相同的是對應(yīng)二叉樹的________。A．先序遍歷序列 B．中序遍歷序列C．后序遍歷序列 D．按層遍歷序列答案：B?；靖拍?。17．設(shè)森林F中有3棵樹，第1棵、第2棵和第3棵樹的結(jié)點個數(shù)分別為M1、M2和M3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是________。A．M1 B．M3 C．M1+M2 D．M2+M3答案：D。森林F中的第2棵和第3棵樹將轉(zhuǎn)換為對應(yīng)二叉樹的右子樹。所以二叉樹根結(jié)點右子樹上的結(jié)點個數(shù)等于第2棵和第3棵樹中的結(jié)點個數(shù)之和。18．一個非空二叉樹的先序遍歷序列與后序遍歷序列正好互為逆序序列，則該二叉樹的形狀應(yīng)為________。A．從樹根結(jié)點開始左右子樹相互對稱 B．所有非葉結(jié)點只有向左的一個分支C．所有非葉結(jié)點只有向右的一個分支 D．所有非葉結(jié)點全部是度為1的結(jié)點答案：D。二叉樹退化為單鏈樹時，先序遍歷序列與后序遍歷序列正好互為逆序序列。19．設(shè)給定權(quán)值總數(shù)為n個，用其構(gòu)造的哈夫曼樹的結(jié)點總數(shù)為________。A．不確定 B．2n-1 C．2n D．2n+1答案：B。給定的權(quán)值為n個，意味著哈夫曼樹中的葉子結(jié)點個數(shù)為n個。哈夫曼樹中沒有度為1的結(jié)點，由滿二叉樹定理可知，度為2的結(jié)點個數(shù)比葉結(jié)點個數(shù)少1，為n-1，故哈夫曼樹中結(jié)點總數(shù)為n+n-1=2n-1。20．下列編碼集中，不具有前綴特性的是________。A．{0,10,110,1111} B．{00,10,011,110,111}C．{00,010,0110,1000} D．{10,11,001,101,0001}答案：D。對于選項D中給出的編碼方案，10是101的前綴，所以不具有前綴特性。對于其他3種編碼方案，可以分別畫出對應(yīng)的編碼樹，以驗證它們都具有前綴特性。例如，選項A所示編碼方案對應(yīng)的編碼樹樹形如圖5-4所示，可以看出，編碼對應(yīng)的各結(jié)點都是葉結(jié)點，以方形結(jié)點表示。類似地，選項B所示編碼方案對應(yīng)的編碼樹樹形如圖5-5所示。圖5圖5-4對應(yīng)于選項A的編碼樹圖5圖5-5對應(yīng)于選項B的編碼樹21．一棵哈夫曼樹共有215個結(jié)點，則樹中編碼的字符個數(shù)是________。A．107 B．108 C．215 D．214答案：B。二、填空題1．具有18個結(jié)點的完全二叉樹，它的高度是__________。答案：5。高度為4的滿二叉樹含有15個結(jié)點，小于18，所以含18個結(jié)點的完全二叉樹，必有結(jié)點位于4層（3個結(jié)點），所以高度為5。也可以根據(jù)二叉樹的性質(zhì)4進行推導(dǎo)。具有n個結(jié)點的完全二叉樹的高度為log2n+1，根據(jù)題意，log22．已知完全二叉樹的5層（根在0層）有8個葉結(jié)點，則整個二叉樹的結(jié)點數(shù)最多是__________。答案：111。由完全二叉樹的定義可知，葉結(jié)點只能出現(xiàn)在最后兩層中。根據(jù)題意，“5層有8個葉結(jié)點”，而最后兩層中都可能有葉結(jié)點，所以5層既可能是指二叉樹的最后一層（樹共有6層），也可能是指樹的倒數(shù)第二層（樹共有7層）。而題目中要求含“結(jié)點個數(shù)最多”，顯然，對于完全二叉樹來說，7層的樹所含的結(jié)點個數(shù)要多于6層的樹所含的結(jié)點個數(shù)，所以該題中對應(yīng)到的完全二叉樹應(yīng)該有7層。前6層的結(jié)點總數(shù)N=除掉8個葉結(jié)點外，5層還有25-8=24個分支結(jié)點，其中每一個結(jié)點都有2個子結(jié)點（位于6層中），所以6層還有24×2=48個葉結(jié)點，故該完全二叉樹總的結(jié)點數(shù)M＝63+24×2=111。3．已知一棵二叉樹的先序遍歷結(jié)果為A,B,C,D,E,F，中序遍歷結(jié)果為C,B,A,E,D,F，則后序遍歷的結(jié)果為__________。答案：C,B,E,F,D,A。給定二叉樹的先序遍歷序列和中序遍歷序列，可以唯一還原該二叉樹。根據(jù)題意，二叉樹的先序遍歷結(jié)果為A,B,C,D,E,F，意味著根是A。而其中序遍歷結(jié)果為C,B,A,E,D,F，表明A的左子樹中有C,B兩個結(jié)點，右子樹中有E,D,F三個結(jié)點。對于含兩個結(jié)點的左子樹，其先序遍歷序列是B,C，中序遍歷序列是C,B。B是根，C是左子結(jié)點。對于含三個結(jié)點的右子樹，先序遍歷是D,E,F，中序遍歷是E,D,F。故右子樹的根是D，左子結(jié)點是E，右子結(jié)點是F。得到的二叉樹如圖5-6所示。AACBDFE圖5-6習題3的二叉樹4．二叉樹的先序遍歷結(jié)果是E,F,H,I,G,J,K，中序遍歷結(jié)果是H,F,I,E,J,K,G，該二叉樹根的右子樹的根是__________。答案：G。由先序遍歷序列E,F,H,I,G,J,K可知，E是根。從中序遍歷序列H,F,I,E,J,K,G中可知，右子樹中含有J,K,G三個結(jié)點，而這三個結(jié)點的先序遍歷序列是G,J,K，即G是該子樹的根。圖5圖5-7習題4的二叉樹EFHIKJG5．若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是__________。答案：11。根據(jù)二叉樹的性質(zhì)3（滿二叉樹定理），有n0=n2+1。由題意知，n2=10，故n0=11。與度為1的結(jié)點個數(shù)5無關(guān)。6．設(shè)樹T的度為4，其中度為1、2、3和4的結(jié)點個數(shù)分別為4、2、1和1，則T中的葉子結(jié)點個數(shù)為__________。答案：8?？梢詫M二叉樹定理推廣到任意k叉樹中。設(shè)k叉樹中葉結(jié)點個數(shù)為n0，度為1的結(jié)點個數(shù)為n1，…，度為k的結(jié)點個數(shù)為nk，則。根據(jù)題意，k=4，度為1的結(jié)點個數(shù)為4，度為2的結(jié)點個數(shù)為2，度為3的結(jié)點個數(shù)為1，度為4的結(jié)點個數(shù)為1個。葉結(jié)點個數(shù)=(2-1)×2+(3-1)×1+(4-1)×1+1=8。7．與算術(shù)表達式a+b*(c+d/e)對應(yīng)的后綴表達式為__________。答案：abcde/++。使用第三章第三節(jié)介紹的表達式轉(zhuǎn)換算法，可以得到對應(yīng)于a+b*(c+d/e)的后綴表達式。或是畫出對應(yīng)于表達式的表達式樹，如圖5-8所示，然后再進行后序遍歷，也可以得到相應(yīng)的后綴表達式。++c/de*b+a圖5-8表示a+b*(c+d/e)的表達式樹8．設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p，p的右子樹結(jié)點個數(shù)為n，則森林F中第一棵樹的結(jié)點個數(shù)是__________。答案：m-n。森林F與其對應(yīng)的二叉樹B中結(jié)點數(shù)是相同的，都是m個結(jié)點。B的右子樹是由F中除第一棵樹外的其他樹轉(zhuǎn)換而來的。F中全部結(jié)點個數(shù)減去B中右子樹中的全部結(jié)點個數(shù)，即為F中第一棵樹中的結(jié)點個數(shù)。9．已知二叉樹的后序遍歷序列為D,G,E,B,F,C,A，中序遍歷序列為D,B,G,E,A,C,F，則先序遍歷序列是__________。答案：A,B,D,E,G,C,F。二叉樹如圖5-9所示。圖5-9習題9的二叉樹圖5-9習題9的二叉樹ACFDGEB10．對于任何一棵二叉樹，若它有n0個葉結(jié)點，n2個度為2的結(jié)點，則n0=__________。答案：n2+1。11．如果深度為k的二叉樹為滿二叉樹，則樹中結(jié)點的個數(shù)是__________。答案：2k+1-1。深度為k的滿二叉樹的高度h=k+1，滿二叉樹中的結(jié)點個數(shù)為2h-1。12．若用二叉鏈表存儲二叉樹，則含有n個結(jié)點的二叉樹中的空指針個數(shù)為__________。答案：n+1。13．設(shè)有含n個結(jié)點的完全二叉樹，如果對結(jié)點按照自上到下、從左到右的次序從1開始進行連續(xù)的編號，則第i（2≤i≤n）個結(jié)點的父結(jié)點編號為__________。答案：i/2。14．設(shè)有含n個結(jié)點的完全二叉樹，如果對結(jié)點按照自上到下、從左到右的次序從1開始進行連續(xù)的編號，則第i個結(jié)點有左子結(jié)點的條件是__________。答案：2i≤n。15．假設(shè)用孩子-兄弟表示法存儲一個森林，則對森林進行的先序遍歷，等同于對其孩子-兄弟鏈表進行的__________。答案：先序遍歷。16．假設(shè)用孩子-兄弟表示法存儲一個森林，則森林進行的后序遍歷，等同于對其孩子-兄弟鏈表進行的__________。答案：中序遍歷。三、解答題1．請使用一棵樹表示你所在學(xué)校的院系機構(gòu)?！緟⒖即鸢浮恳粋€學(xué)校的院系機構(gòu)數(shù)目眾多，通常劃分為專業(yè)院系、職能部門、直屬單位及研究機構(gòu)等幾大類。每一類中選擇一個單位，如圖5-10所示。學(xué)校學(xué)校計算機專業(yè)網(wǎng)絡(luò)安全專業(yè)教學(xué)管理科學(xué)籍管理科多媒體服務(wù)部古籍特藏部理論物理室微分幾何室計算機學(xué)院教務(wù)部圖書館數(shù)學(xué)研究所圖5-10一個學(xué)校的院系機構(gòu)2．當使用一棵樹描述本章目錄（第五章、節(jié)、小節(jié)）時，請回答下列問題：（1）樹中共有多少個結(jié)點？（2）每個結(jié)點的度分別是多少？（3）樹的深度是多少？【參考答案】使用縮進形式描述第五章的目錄，如下所示。第五章樹與二叉樹（5） 第一節(jié)樹的基本概念（0） 第二節(jié)二叉樹（2） 一、二叉樹的定義及其主要特性（0） 二、二叉樹的存儲（0） 第三節(jié)二叉樹的操作（3） 一、二叉樹的生成（0） 二、二叉樹的遍歷（0） 三、二叉樹的應(yīng)用（0） 第四節(jié)樹和森林（3） 一、樹的存儲結(jié)構(gòu)（0） 二、樹、森林與二叉樹的轉(zhuǎn)換（0） 三、樹和森林的遍歷（0） 第五節(jié)哈夫曼樹及哈夫曼編碼（3） 一、編碼（0） 二、哈夫曼樹（0） 三、哈夫曼編碼（0）（1）根在0層，1個結(jié)點。本章共有5節(jié)，即1層有5個結(jié)點。第一節(jié)沒有子結(jié)點，第二節(jié)到第五節(jié)分別有2、3、3、3個子結(jié)點。樹中共有1+5+2+3+3+3=17個結(jié)點。（2）各結(jié)點的度列在結(jié)點后的括號內(nèi)。（3）樹的深度是2。3．有4個結(jié)點的二叉樹共有多少種不同的樹形？分別畫出。【參考答案】有4個結(jié)點的二叉樹共有14種不同的樹形。所圖5-11所示。圖5圖5-11含4個結(jié)點的不同二叉樹樹形4．若某棵樹有n1個度為1的結(jié)點，n2個度為2的結(jié)點，…，nm個度為m的結(jié)點，問這棵樹共有多少個葉結(jié)點？給出推導(dǎo)過程?！緟⒖即鸢浮咳~結(jié)點個數(shù)n0滿二叉樹定理可以推廣到任意m叉樹中。設(shè)m叉樹中葉結(jié)點數(shù)為n0，度為1的結(jié)點數(shù)為n1，…，度為m的結(jié)點數(shù)為nm。結(jié)點總數(shù)n=i=0mni，樹中含有的分支數(shù)B而對于度為k的結(jié)點，可以帶有k個分支，故樹中分支數(shù)B=i=1min5．使用同樣結(jié)構(gòu)的結(jié)點構(gòu)造的雙向鏈表和二叉鏈表，有什么不同？【參考答案】雙向鏈表和二叉鏈表都是鏈式存儲結(jié)構(gòu)，它們的結(jié)點結(jié)構(gòu)都是含有一個數(shù)據(jù)類型域及兩個指針類型域，結(jié)構(gòu)是相同的，但指針指向的含義是不同的。構(gòu)造的雙向鏈表是線性結(jié)構(gòu)，鏈表結(jié)點中的兩個指針，一個指針指向其前驅(qū)，另一個指針指向其后繼。鏈表中相鄰的兩個結(jié)點，可以分別通過向前的指針和向后的指針互相指示。二叉鏈表是層次結(jié)構(gòu)，結(jié)點中所含的兩個指針都是指向子結(jié)點的，任意兩個結(jié)點都不會出現(xiàn)相互指示的情況。knceshpknceshpad圖5圖5-12習題6的二叉樹【參考答案】先序遍歷序列：k,c,a,e,d,h,n,s,p。中序遍歷序列：a,c,d,e,h,k,n,p,s。后序遍歷序列：a,d,h,e,c,p,s,n,k。7．現(xiàn)有某二叉樹，其先序遍歷序列是：A,B,C,D,E,F,G,H,I，中序遍歷序列是：B,C,A,E,D,G,H,F,I，畫出該二叉樹。【參考答案】得到的二叉樹如圖5-13所示。AADHBECFGI圖5-13習題7的二叉樹8．將圖5-12（習題6）所示的二叉樹還原為森林。knceshknceshpad圖5圖5-14圖5-12所示的二叉樹對應(yīng)的森林9．樹的集合表示法能用來表示二叉樹嗎？修改集合表示法，使之能表示二叉樹，以圖5-43所示的二叉樹為例，給出其集合表示?！緟⒖即鸢浮繕涞募媳硎痉ú荒苤苯颖硎径鏄洹Ｊ褂眉媳硎痉ū硎緲涞囊话阈问饺缦拢?根結(jié)點,(子樹1),(子樹2),…,(子樹n))當根只有一棵子樹時，樹可以表示為(根結(jié)點,(子樹1))。但對于二叉樹，一棵子樹既可能是左子樹，也可能是右子樹，使用集合表示法區(qū)分不了這種差別?？梢愿倪M集合表示法，使用一個特殊符號作為占位符，表示空的子樹。使用改進的集合表示法表示二叉樹的一般形式如下：(根結(jié)點,(左子樹),(右子樹))即使子樹為空，也需要表示出來，即要占位。圖5-12（習題6）所示二叉樹的集合表示如下所示：(k,(c,(a,(),())(e,(d,(),())(h,(),()))),(n,(),(s,(p,(),()),())))可以再簡化這個表示方法。當子樹為空時，可以使用一個特殊符號表示，例如使用#替代()。采用簡化表示方式后，圖5-12（習題6）所示二叉樹的集合表示如下所示：(k,(c,(a,#,#)(e,(d,#,#)(h,#,#))),(n,#,(s,(p,#,#),#)))10．給定一組權(quán)值：15,22,14,6,7,5,7，構(gòu)造一棵哈夫曼樹，并計算樹的外部帶權(quán)路徑長度?！緟⒖即鸢浮砍跏紩r，如圖5-15所示。55714152267圖5-15構(gòu)造哈夫曼樹的初始步驟合并權(quán)值最小的兩棵樹，如圖5-16所示。圖5-16合并權(quán)圖5-16合并權(quán)值最小的兩棵樹714152275611持續(xù)合并權(quán)值最小的兩棵樹，直到最終得到哈夫曼樹，如圖5-17所示。注意所構(gòu)造的哈夫曼樹不是唯一的，但樹的WPL是唯一的。222256117714254714152976圖5-17圖5-17哈夫曼樹WPL=142+152+222+54+64+74+74=202。11．假設(shè)字符a,b,c,d,e,f在某文本中出現(xiàn)的頻率分別為7,9,12,22,23,27，求這些字符的哈夫曼編碼?！緟⒖即鸢浮繕?gòu)造的哈夫曼樹如圖5-18所示。哈夫曼編碼如表5-1所示。ffcab162855de45100圖5圖5-18哈夫曼樹表5-1哈夫曼編碼字符abcdef編碼11101111110000110注意，哈夫曼樹和哈夫曼編碼都不是唯一的。12．畫出算術(shù)表達式((a+b)+c*(d+e)+f)*(g+h)的表達式樹。fcedfced*+ba+++hg+*圖5圖5-19習題11的表達式樹13．已知一棵二叉樹T，請回答下列問題。（1）如果知道T的先序遍歷序列和層序遍歷序列，是否可以唯一還原T？為什么？（2）如果知道T的中序遍歷序列和層序遍歷序列，是否可以唯一還原T？為什么？【參考答案】（1）如果知道T的先序遍歷序列和層序遍歷序列，不能唯一還原二叉樹T。圖5-20a和圖5-20b是兩棵不同的二叉樹，但它們的先序遍歷序列相同，層序遍歷序列也相同。aa)二叉樹1ABb)二叉樹1AB圖5-20兩棵二叉樹（2）如果知道T的中序遍歷序列和層序遍歷序列，可以唯一還原一棵二叉樹。層序遍歷的第一個結(jié)點是根，在中序遍歷序列中，根的前面是左子樹中的全部結(jié)點，后面是右子樹中的全部結(jié)點。根據(jù)這些結(jié)點的信息，將層序遍歷序列中除根以外的全部結(jié)點分為兩組，一組是由左子樹中的全部結(jié)點組成的，這個即是左子樹的層序遍歷序列，另一組是由右子樹中的全部結(jié)點組成的，這個即是右子樹的層序遍歷序列。原問題劃分為規(guī)模更小的兩個問題，使用遞歸方法即可求解。14．將圖5-27所示的兩棵樹合并為一棵樹，令W為R的第三個子結(jié)點，畫出保存該樹的存儲結(jié)構(gòu)?！緟⒖即鸢浮勘４鎯煽脴涞拇鎯Y(jié)構(gòu)是：下標012345678910dataRABCDEFWXYZparent-7001124-4777合并后的存儲結(jié)構(gòu)是：下標012345678910dataRABCDEFWXYZparent-110011240777四、算法閱讀題二叉鏈表中結(jié)點類的定義及二叉樹的定義如下所示。typedefintELEMType;typedefstructBNode //二叉樹結(jié)點{ ELEMTypedata; //數(shù)據(jù)域 structBNode*left,*right; //指向左子結(jié)點、右子結(jié)點的指針}BinTNode;typedefBinTNode*BTree; //二叉樹以下程序?qū)崿F(xiàn)了二叉樹的若干基本操作，請在空白處填上適當內(nèi)容將算法補充完整。1．返回二叉樹的高度。inthigh(BTreeroot){ inti,j; if(（1）)return0; i=（2）; j=（3）; if(i>=j)returni+1; elsereturnj+1;}【參考答案】（1）root==NULL（2）high(root->left)（3）high(root->right)2．返回二叉樹中度為1的結(jié)點個數(shù)。intoneDNodeNumber(BTreeroot){ if(root==NULL)（1）; if((（2）)||(root->left!=NULL&&root->right==NULL)) return（3）; elsereturnoneDNodeNumber(root->left)+oneDNodeNumber(root->right);}【參考答案】（1）return0（2）root->left==NULL&&root->right!=NULL（3）oneDNodeNumber(root->left)+oneDNodeNumber(root->right)+13．二叉鏈表中結(jié)點類的定義及二叉樹的定義如下所示。typedefintELEMType;typedefstructBNode //二叉樹結(jié)點{ ELEMTypedata; //數(shù)據(jù)域 structBNode*left,*right; //指向左子結(jié)點、右子結(jié)點的指針}BinTNode;typedefBinTNode*BTree; //二叉樹說明change函數(shù)的功能。voidchange(BTreeroot){ BinTNode*temp; if(root==NULL)return; change(root->left); change(root->right); temp=root->left; root->left=root->right; root->right=temp; return;}【參考答案】change函數(shù)的功能是將二叉樹中所有結(jié)點的左、右子樹相互交換。4．函數(shù)CountLeave的功能是計算二叉樹中葉結(jié)點的數(shù)量。typedefstructBiTNode{ ElemTypedata; structBiTNode*lchild,*rchild;}*BiTree; //二叉樹結(jié)點定義intCountLeave(BiTreeT) //返回值為二叉樹T中葉結(jié)點的個數(shù){ if(!T)return（1）; if(T->lchild==NULL&&T->rchild==NULL) return（2）; else return（3）;}為使函數(shù)能夠完成指定的功能，請在程序中的橫線處填入適當?shù)膬?nèi)容?！緟⒖即鸢浮浚?）0（2）1（3）CountLeave(T->lchild)+CountLeave(T->rchild)五、算法設(shè)計題1．設(shè)二叉樹以二叉鏈表的形式存儲，試設(shè)計算法，返回二叉樹中度為2結(jié)點的個數(shù)?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。typedefintELEMType;typedefstructBNode //二叉樹結(jié)點{ ELEMTypedata; //數(shù)據(jù)域 structBNode*left,*right; //指向左子結(jié)點、右子結(jié)點的指針}BinTNode;typedefBinTNode*BTree; //二叉樹inttwoDNodeNumber(BTreeroot){ if(root==NULL)return0; if((root->left!=NULL&&root->right!=NULL)) returntwoDNodeNumber(root->left)+twoDNodeNumber(root->right)+1; elsereturntwoDNodeNumber(root->left)+twoDNodeNumber(root->right);}2．設(shè)二叉樹以二叉鏈表的形式存儲，每個結(jié)點的數(shù)據(jù)域中存放一個整數(shù)。試設(shè)計算法，求二叉樹中所有結(jié)點中所保存的整數(shù)之和?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。intsumofTree(BTreeroot){ if(root==NULL)return0; returnsumofTree(root->left)+sumofTree(root->right)+root->data;}3．將二叉樹中每層的結(jié)點個數(shù)定義為該層的寬度，各層最寬的寬度定義為二叉樹的寬度。設(shè)二叉樹以二叉鏈表的形式存儲，試設(shè)計算法，返回二叉樹的寬度?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。intWidthofTree(BTreeroot){ BinTNodetemp,interval; SeqBTreeQueuemyq; //使用第三章實現(xiàn)的隊列 inttreewidth=-1,count=0; printf("\nwidth\n"); initQueue(&myq); //初始化隊列myq interval.data=NA; if(root==NULL)return0; enqueue(&myq,root); //根入隊列 enqueue(&myq,&interval); //treewidth=1; printf("width1\n"); while(!isEmptyQ(&myq)){//隊列不空，意味著還有結(jié)點待遍歷 dequeue(&myq,&temp); if(temp.data!=NA){ printf("%d\t",temp.data); count++; if(temp.left!=NULL)enqueue(&myq,temp.left); if(temp.right!=NULL)enqueue(&myq,temp.right); } elseif(!isEmptyQ(&myq)){ if(count>treewidth) treewidth=count; count=0; enqueue(&myq,&interval); } } returntreewidth;}

第六章圖結(jié)構(gòu)一、單項選擇題1．設(shè)無向圖的頂點個數(shù)為n，則該圖所含的邊數(shù)最多是________。A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．n2答案：B。完全圖所含的邊數(shù)最多。對于無向圖，每個頂點都和其他頂點之間有邊相連，不含有頂點到自己的邊。每對頂點之間僅能有一條邊。2．含n個頂點的連通無向圖中，邊數(shù)至少是________。A．n-1 B．n C．n+1 D．nlogn；答案：A。含n個頂點的無向圖中，如果邊數(shù)少于n-1，則必定是不連通的。邊數(shù)等于n-1時，可以構(gòu)成一個連通圖。邊數(shù)多于n-1時，不僅能構(gòu)成連通圖，還一定會出現(xiàn)回路。所以n-1條邊是最少的。但并不是至少含有n-1條邊的圖一定是連通圖。比如，一個三角形加一個孤立點構(gòu)成的圖中，頂點個數(shù)為n=4，邊數(shù)為3=n-1，但圖是不連通的。含有至少n-1條邊的圖，要看邊與頂點的關(guān)聯(lián)情況，才能知道是不是構(gòu)成連通圖。當邊數(shù)足夠多時，比如，含n個頂點的圖中至少有(n-1)(n-2)/2+1條邊時，圖一定是連通圖。(n-1)(n-2)/2條邊使得n-1個頂點的子圖成為完全圖，現(xiàn)在得到兩個連通分量，還剩余一條邊，在含n-1個頂點的連通分量中不能再增加邊了，所以這條邊只能是連接n-1個頂點中的任一個與唯一的孤立頂點，使得孤立頂點與這個完全子圖連通，圖成為連通圖。3．下列敘述中錯誤的是________。A．圖的深度優(yōu)先搜索遍歷是一個遞歸過程B．圖的深度優(yōu)先搜索遍歷不適用于有向圖C．深度優(yōu)先遍歷和廣度優(yōu)先遍歷是圖遍歷的兩種基本算法D．圖的遍歷是從給定的頂點出發(fā)每一個頂點僅被訪問一次答案：B。圖的深度優(yōu)先搜索和廣度優(yōu)先搜索是圖遍歷的兩種基本策略（選項C正確）。深度優(yōu)先搜索通常采用遞歸方式實現(xiàn)（選項A正確），既適用于對無向圖的遍歷，也適用于對有向圖的遍歷（選項B錯誤）。選項D是圖遍歷的定義。4．無向圖G=(V,E)，其中，V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對該圖進行深度優(yōu)先遍歷，得到的頂點序列是________。A．a(chǎn),b,e,c,d,f B．a(chǎn),c,f,e,b,d C．a(chǎn),e,b,c,f,d D．a(chǎn),e,d,f,c,b答案：D。要完成這個題，可以先畫出題目中所給的圖，如圖6-1所示。bbeadcf圖圖6-1習題4的圖根據(jù)深度優(yōu)先搜索策略，遍歷了a,b,e三個頂點后，接下來應(yīng)該尋找頂點e的未遍歷鄰接點（d）進行遍歷，而不會遍歷到頂點c（選項A是錯誤的）。在遍歷了a,c,f三個頂點后，接下來應(yīng)該尋找頂點f的未遍歷鄰接點（d）進行遍歷，而不會遍歷到頂點e（選項B是錯誤的）。在遍歷了a,e,b三個頂點后，頂點b的所有鄰接點均已遍歷，應(yīng)該回退到頂點e，選擇e的下一個未遍歷的鄰接點（d）進行遍歷，而不會遍歷到頂點c（選項C是錯誤的）。對于選項D，從頂點a開始遍歷，依次訪問了頂點a,e,d,f,c后，c的鄰接點都被遍歷過了，開始回退，到達頂點e后，它還有未遍歷的鄰接點b，訪問b，遍歷完成。5．已知有向圖G=(V,E)，其中V={v1,v2,v3,v4,v5,v6,v7}，E={(v1,v2),(v1,v3),(v1,v4),(v2,v5),(v3,v5),(v3,v6),(v4,v6),(v5,v7),(v6,v7)}，G的拓撲序列是________。A．v1,v3,v4,v6,v2,v5,v7 B．v1,v3,v2,v6,v4,v5,v7C．v1,v3,v4,v5,v2,v6,v7 D．v1,v2,v5,v3,v4,v6,v7答案：A。要完成這個題，可以先畫出題目中所給的圖，如圖6-2所示。vv2v7v5v4v1v3v6圖圖6-2習題5的圖對于選項B，v6出現(xiàn)在v4之前，但圖中存在邊(v4,v6)，這是矛盾的，故選項B錯誤。對于選項C，v5出現(xiàn)在v2之前，但圖中存在邊(v2,v5)，這是矛盾的，故選項C錯誤。對于選項D，v5出現(xiàn)在v3之前，但圖中存在邊(v3,v5)，這是矛盾的，故選項D錯誤。6．在有向圖G的拓撲排序中，若頂點vi在頂點vj之前，則下列情形不可能出現(xiàn)的是________。A．G中有弧(vi,vj) B．G中有一條從vi到vj的路徑C．G中沒有弧(vi,vj) D．G中有一條從vj到vi的路徑答案：D。在拓撲排序中，若有一條從vj到vi的路徑，則表明vj是vi的先決條件，必須先完成vj后才能開始vi，那么在拓撲排序中，頂點vi不可能出現(xiàn)在頂點vj之前。二、解答題1．舉例說明，帶權(quán)圖中的權(quán)值可以表示什么含義?！緟⒖即鸢浮繖?quán)值可以表示圖中很多的信息。比如，在一個反映城市間公路網(wǎng)的圖中，可以用頂點表示城市，邊表示道路，用邊上的權(quán)值表示兩城市間道路的里程數(shù)、走行時間、所需費用等等，權(quán)還可以用來表示該條公路的車流量、公路等級、道路的限速等其他信息。對于一個電子線路圖，邊上的權(quán)值可以表示兩個端點之間的電阻、電流或電壓值。對于反映工程進度的圖而言，邊上的權(quán)值可以表示從前一個工程到后一個工程所需要的時間等等。圖6-4一個無向圖和一個有向圖a)無向圖145321圖6-4一個無向圖和一個有向圖a)無向圖1453214532b)有向圖【參考答案】鄰接矩陣的定義如下：圖6-4a的鄰接矩陣A如下所示。A=頂點下標指針頂點下標指針圖6-4a的鄰接表如圖6-5a所示。圖6-4b的鄰接矩陣A如下所示。A=12001321200132403123450123443a)圖6-4a的鄰接表1012412∧345∧012344b)圖6-4b的鄰接表圖圖6-5圖6-4的鄰接表3．求圖6-4a各頂點的度及圖6-4b各頂點的入度和出席。【參考答案】圖6-4a各頂點的度如表6-1所示。表6-1圖6-4a各頂點的度頂點12345度32232圖6-4b各頂點的入度和出度如表6-2所示。表6-2圖6-4b各頂點的入度和出度頂點12345入度12102出度201304．給出帶權(quán)圖6-6的鄰接矩陣和鄰接表。vv0v1v3v4v2v5v6v7627414105567326圖圖6-6帶權(quán)圖【參考答案】帶權(quán)圖鄰接矩陣的定義如下所示。圖6-6的鄰接矩陣A如下所示。A頂點下標權(quán)值頂點下標權(quán)值指針圖6-7圖6-6的鄰接表v圖6-7圖6-6的鄰接表v00163624v11065747v22046635v33v44v55v77v66066525414177331451017724102672354362525．給出圖6-4a的幾個不同的子圖。圖6-8圖6-4a的幾個不同的子圖14圖6-8圖6-4a的幾個不同的子圖1453214521453214532第一個是包含原圖中全部頂點，但沒有任何邊的子圖。第二個是包含了部分頂點和部分邊的子圖。第三個是包含了全部頂點及部分邊的子圖。第四個是原圖，圖也是自身的子圖。2314523145圖6-9無向圖【參考答案】從頂點1開始的深度優(yōu)先搜索遍歷序列是12354、12453、14235、14532、13245、13542。給出其中的5種即可。7．對圖6-9，從頂點1開始進行廣度優(yōu)先搜索，試給出5種不同的遍歷序列?！緟⒖即鸢浮繌捻旤c1開始的廣度優(yōu)先搜索遍歷序列是12345、12435、13245、13425、14235、14325。給出其中的5種即可。8．對圖6-9，給出它的幾棵不同的深度優(yōu)先生成樹。23145圖6-11對應(yīng)于12453的生成樹23145圖6-10對應(yīng)于23145圖6-11對應(yīng)于12453的生成樹23145圖6-10對應(yīng)于12354的生成樹231423145圖6-15對應(yīng)于13542的生成樹23145圖6-14對應(yīng)于13245的生成樹23145圖6-13對應(yīng)于14532的生成樹23145圖6-12對應(yīng)于14235的生成樹9．對圖6-9，給出它的幾棵不同的廣度優(yōu)先生成樹。23145圖6-17廣度優(yōu)先23145圖6-17廣度優(yōu)先生成樹23145圖6-16廣度優(yōu)先生成樹10．對圖6-18，使用普里姆算法求最小生成樹?！緟⒖即鸢浮?523352314527988圖6-18帶權(quán)無向圖表6-3使用普里姆算法求最小生成樹Vclosedge2345UV-U選中的邊vexlowcost171518{1}{2,3,4,5}(1,3)vexlowcost331839{1,3}{2,4,5}(2,3)vexlowcost1839{1,2,3}{4,5}(1,4)vexlowcost42{1,2,3,4}{5}(4,5)vexlowcost{1,2,3,4,5}Φ35231352314528圖6-20最小生成樹352314528圖6-19最小生成樹在第二步選中了邊(2,3)而將頂點2加入最小生成樹T后，到頂點4的有最小權(quán)值的邊有兩條，分別是(1,4)和(2,4)，邊上的權(quán)都是8。所以，第三步選擇權(quán)值為8的邊時，既可以選中(1,4)也可以選中(2,4)。如果選中的是(2,4)，則得到的最小生成樹如圖6-20所示。11．對圖6-18，使用克魯斯卡爾算法求最小生成樹?！緟⒖即鸢浮肯葘⑦叞礄?quán)值進行升序排序，如表6-4所示。表6-4按權(quán)值排序的各條邊是否選中邊權(quán)值(4,5)2(2,3)3(1,3)5(1,2)7(1,4)8(2,4)8(3,5)9得到的最小生成樹如圖6-21所示。35352314528圖6-22最小生成樹352314528圖6-21最小生成樹對邊進行排序時，如果邊(2,4)排在邊(1,4)的前面，則選中的邊是(2,4)而不是(1,4)，得到的最小生成樹如圖6-22所示。①②④③⑤⑥⑦⑧⑨①②④③⑤⑥⑦⑧⑨⑩圖6-23一個有向無環(huán)圖【參考答案】拓撲排序如下所示。1,2,3,4,5,6,7,8,9,101,2,4,3,5,6,7,8,9,101,4,3,2,5,6,7,8,9,101,2,3,4,6,5,7,8,9,101,2,4,3,6,5,7,8,9,101,4,3,2,5,6,7,8,9,10實際上，還可以寫出更多的拓撲排序，比如：1,2,3,4,5,6,8,7,9,101,2,4,3,5,6,9,8,7,101,4,3,2,5,6,8,9,7,101,4,3,2,6,5,9,8,7,10圖6-24一個帶權(quán)圖3012453圖6-24一個帶權(quán)圖30124536782510153863107102016【參考答案】圖6-24的鄰接矩陣如下。A使用Dijkstra算法求解從頂點1到其余各頂點最短路徑的過程如圖6-25所示。終點從頂點1到各頂點的dist值和最短路徑230(1,2)25(1,5,2)25(1,5,2)25(1,5,2)3∞∞20(1,5,6,3)4∞∞∞45(1,5,6,3,4)45(1,5,6,3,4)31(1,5,6,7,4)510(1,5)6∞17(1,5,6)7∞∞25(1,5,6,7)25(1,5,6,7)25(1,5,6,7)8∞∞∞∞∞35(1,5,6,7)35(1,5,6,7)vj5632748S1,51,5,61,5,6,31,5,6,3,21,5,6,3,2,71,5,6,3,2,7,41,5,6,3,2,7,4,8圖6-25圖6-25求最短路徑過程14．求圖6-25所示的AOE網(wǎng)各事件的最早開始時間和最遲開始時間。3030124356251015386310710201678910814121833圖6-25圖6-25AOE網(wǎng)【參考答案】圖6-25所示AOE網(wǎng)各事件的最早開始時間和最遲開始時間如表6-5所示。表6-5各事件的最早開始時間和最遲開始時間事件最早開始時間最遲開始時間10021212388421215181862727三、算法設(shè)計題1．對于給定的無向圖G，采用鄰接矩陣存儲，試設(shè)計算法intgetD(MGraphg,VTypeu)，返回頂點u的度?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。intgetD(MGraphg,VTypeu){ //返回頂點u的度 intdegree=0,i,j; i=VerToNum(g,u); for(j=0;j<g.numVertices;j++)degree+=g.AdjMatrix[i][j]; returndegree;}無向圖中，鄰接矩陣的一行中非零元的個數(shù)即為該對應(yīng)頂點的度。也可以統(tǒng)計鄰接矩陣的一列中非零元的個數(shù)。2．對于給定的無向圖G，采用鄰接矩陣存儲，試設(shè)計算法isPath(MGraphg,VType*path)，判定給定的頂點序列path是否是圖中的路徑。【參考答案】程序?qū)崿F(xiàn)如下所示。intisPath(MGraphg,VType*path){ inti,k,len,start,end; len=sizeof(path); if(len==0)returnFALSE; for(i=0;i<len-1;i++){ start=VerToNum(g,path[i]); end=VerToNum(g,path[i+1]); if(g.AdjMatrix[start][end]==0)returnFALSE; } returnTRUE;}

第7章內(nèi)部排序一、單項選擇題1．下列關(guān)于穩(wěn)定排序方法的敘述中，正確的是________。I．該排序算法可以處理相同的關(guān)鍵字II．該排序算法不可以處理相同的關(guān)鍵字III．該排序算法處理相同的關(guān)鍵字時能確定它們的排序結(jié)果IV．該排序算法處理相同的關(guān)鍵字時不能確定它們的排序結(jié)果A．僅I、III B．僅I、IV C．僅II、III D．僅II、IV答案：A。具有相等關(guān)鍵字的兩個記錄，經(jīng)過穩(wěn)定的排序后，它們的相對次序不改變。初始序列中是什么樣的相對次序，排序后的相對次序也是什么樣的。這是穩(wěn)定排序具有的特性。根據(jù)排序方法穩(wěn)定性的定義，可知I和III是正確的。2．下列排序方法中，排序趟數(shù)與序列的初始狀態(tài)有關(guān)的是________。A．插入排序 B．選擇排序 C．起泡排序 D．快速排序答案：D。對n個數(shù)據(jù)項，插入排序、選擇排序和起泡排序都需要進行n-1趟排序。對于快速排序，序列的初始狀態(tài)不同，可能會影響劃分過程的結(jié)果，即經(jīng)過劃分后，兩個子段中所含數(shù)據(jù)的個數(shù)會不同。比如，如果每次都大致將數(shù)據(jù)一分為二，劃分的兩個子段中所含的數(shù)據(jù)個數(shù)相當，則排序的趟數(shù)約為logn。而如果每次劃分都出現(xiàn)極端情況，一個子段為空，則排序趟數(shù)為n-1。3．若用起泡排序?qū)﹃P(guān)鍵字序列18,16,14,12,10,8進行升序排序，所需進行的關(guān)鍵字比較總次數(shù)是________。A．10 B．15 C．21 D．34答案：B。給定的關(guān)鍵字序列呈降序排列，要求進行升序排序。按照起泡排序的算法，元素18要與后面的全部5個元素進行比較，然后位于最終的排序位置。在這一趟中需要進行5次比較。類似的，元素16要與后面的除18之外的4個元素進行比較，最后排在18的前面。這一趟排序需要進行4次比較。元素14排序到位的話，需要進行3次比較。元素12排序到位的話，需要進行2次比較。元素10排序到位的話，需要進行1次比較。其他元素都到位了，意味著元素8也到位了。所以總的比較次數(shù)=5+4+3+2+1=15。實際上，題目中所給的關(guān)鍵字序列是降序的，對于升序序列來說，這是最壞的初始排列。所以關(guān)鍵字比較次數(shù)最多，需要n(n-1)/2次比較。n=6時，需要15次比較。4．下列排序算法中，不能保證每趟排序至少能將一個元素放到其最終的位置上的是________。A．快速排序 B．希爾排序 C．堆排序 D．起泡排序答案：B。采用快速排序，每趟排序都至少有一個樞軸放置到最終位置上。堆排序中，每趟都將堆頂元素放置到最終位置上。起泡排序中，每趟會選出本趟的極值（最大或最?。┓胖迷谧罱K位置上。但希爾排序不能保證。5．一組記錄的關(guān)鍵字值為46,79,56,38,40,84，利用partition劃分算法，以第一個記錄為樞軸，得到的一次劃分結(jié)果為________。A．38,40,46,56,79,84 B．40,38,46,79,84,56C．40,38,46,56,79,84 D．40,38,46,84,56,79答案：B。初始：467956384084選擇第一個元素做樞軸并將樞軸放到最后的位置：pivot:46847956384046此時，left對應(yīng)于84，right對應(yīng)于40。接下來，從left開始向右尋找大于樞軸的元素，當前元素即大于樞軸，停在84處。然后從right開始向左尋找小于樞軸的元素，也是在當前位置，停在40處。如下所示。847956384046↑↑leftright交換兩個元素，如下所示。407956388446↑↑leftright接下來，尋找第二對滿足條件的數(shù)據(jù)，如下所示。407956388446↑↑leftright交換兩個元素，如下所示。403856798446↑↑leftright繼續(xù)尋找下一對數(shù)據(jù)，如下所示。403856798446↑↑rightleft此時，right>left，需要將樞軸歸位，交換56與46，得到劃分結(jié)果403846798456。6．在下面的排序方法中，輔助空間為O(n)的是________。A．希爾排序 B．堆排序 C．選擇排序 D．歸并排序答案：D。希爾排序、堆排序及選擇排序都可以實現(xiàn)“原地排序”，即只需要若干個輔助變量，在保存數(shù)據(jù)的原數(shù)組空間上完成排序操作，空間復(fù)雜度是O(1)。歸并排序過程中，需要申請一個與原數(shù)組等大的輔助數(shù)組，空間復(fù)雜度是O(n)的。7．下列排序算法中，當待排序數(shù)據(jù)已有序時，花費時間反而最多的是________。A．起泡排序 B．希爾排序 C．快速排序 D．堆排序答案：C。當待排序數(shù)據(jù)已有序時，采用最原始的樞軸選擇方法，可能導(dǎo)致所選的樞軸是數(shù)據(jù)中最小或最大的元素，這樣的樞軸將原始數(shù)據(jù)劃分為一個為空、另一個含其余全部數(shù)據(jù)的兩組，因此排序的趟數(shù)最多，花費的時間最多。另外三個排序方法，當待排序數(shù)據(jù)已有序時，數(shù)據(jù)交換次數(shù)達到最少，花費的時間均能達到各排序方法的最優(yōu)情況。8．數(shù)組中有10000個元素，如果僅要求求出其中最大的4個元素，則最節(jié)省時間的算法是________。A．直接插入排序 B．希爾排序 C．快速排序 D．選擇排序答案：D。有的排序方法需要將所有數(shù)據(jù)全部排序完畢，才能知道最大的元素是哪個。有些排序方法，邊排序邊得到部分最終結(jié)果。題意要求選出10000個元素中最大的4個，顯然，使用后一類的排序方法更能節(jié)省時間，因為除最大的4個數(shù)據(jù)外，其余的數(shù)據(jù)不需要完全排序。選項中給出的4個排序方法中，直接插入排序和希爾排序都需要將全部數(shù)據(jù)排序后才能知道最大的4個元素是什么。對于快速排序，使用樞軸將全部數(shù)據(jù)劃分為整體有序的兩部分。如果樞軸是所有數(shù)據(jù)中第k大的元素，且k<9996，則需要在較大的部分中繼續(xù)進行劃分。劃分的趟數(shù)是不確定的。對于選擇排序，每趟排序都能選出本趟中的最大值，4趟排序后即可選出最大的4個元素。它屬于不完全排序方法（即邊排序邊得到部分最終結(jié)果）。4趟選擇排序中，需要進行的比較操作是n-1+n-2+n-3+n-4=4n-10，交換次數(shù)不會超過比較次數(shù)。9．從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在已排序序列的合適位置，該排序方法稱為________。A．直接插入排序 B．選擇排序 C．希爾排序 D．二路歸并排序答案：A。題目中描述的正是直接插入排序的含義。10．使用數(shù)據(jù)序列10,15,20,25,30建立初始最大堆時，數(shù)據(jù)對交換的次數(shù)是________。A．1 B．2 C．3 D．4答案：C。建立初始最大堆的過程如圖7-1所示。101030251520a)初始完全二叉樹1015253020b)30與15交換3015251020c)30與10交換3015251020d)10與25交換圖7-1建初始最大堆的過程二、填空題1．對含n個數(shù)據(jù)的序列進行排序，直接插入排序在最好情況下的時間復(fù)雜度為__________。答案：O(n)。初始數(shù)據(jù)已有序時，直接插入排序能達到最優(yōu)時間復(fù)雜度，從第二個元素到最后一個元素，每個元素僅需和其直接前驅(qū)進行比較，不需要交換，即能完成排序。排序中關(guān)鍵字比較次數(shù)為n-1，交換次數(shù)為0。2．現(xiàn)有含9個關(guān)鍵字的最小堆，排在關(guān)鍵字升序第3位的元素（第3?。┧幍奈恢脗€數(shù)可能是__________。答案：6。含9個關(guān)鍵字的最小堆如圖7-2所示。堆中，a0是最小值，a1和a2都可能是第3小的值。如果a1<a2，則a3和a4也可能是第3小的值。如果a1>a2，則a5和a6也可能是第3小的值。所以，第3小的值可能位于從a1到a6的任一位置中，共6個。aa7a0a4a3a1a6a5a2a8圖7-2含9個關(guān)鍵字的最小堆3．一組記錄的關(guān)鍵字值為45,79,59,63,65,26,80,17，利用partition劃分算法，以第一個記錄為樞軸，劃分過程中，與元素79相交換的關(guān)鍵字是__________。答案：26。根據(jù)partition算法，劃分過程如下所示。初始：4579596365268017選擇第一個元素做樞軸并將樞軸放到最后的位置：pivot:451779596365268045此時，left對應(yīng)于17，right對應(yīng)于80。接下來，從left開始向右尋找大于樞軸的元素，當前元素即大于樞軸，停在79處。然后從right開始向左尋找小于樞軸的元素，停在26處。如下所示。1779596365268045↑↑leftright交換兩個元素（79和26）。4．已知一組關(guān)鍵字為：45,78,57,30,40,89，利用堆排序?qū)ζ溥M行升序排序，建立的初始堆是__________。答案：89,78,57,30,40,45。5．設(shè)關(guān)鍵字序列為16,15,32,11,6,30,22,46,7，采用基數(shù)排序進行升序排序。若關(guān)鍵字序列保存在含9個元素的數(shù)組A中，則一趟基數(shù)排序后，元素16的下標位置為__________。答案：5。一趟分配與收集后，得到的結(jié)果是30,11,32,22,15,16,6,46,7，元素16在下標5處。三、解答題1．設(shè)一維整數(shù)數(shù)組內(nèi)保存整數(shù)序列，回答下列問題：（1）試寫出整數(shù)序列2,3,8,6,1中的所有逆序?qū)?。?）什么情況下，由1,2,…,n組成的序列中逆序?qū)ψ疃?？【參考答案】?）逆序?qū)Γ?2,1),(3,1),(8,1),(6,1),(8,6)。（2）數(shù)據(jù)序列為n,n-1,…,3,2,1時，逆序?qū)ψ疃唷Ｃ總€元素都和其后面的所有元素呈逆序，所以總的逆序?qū)€數(shù)=n-1+n-2+…+2+1=n(n-1)/2。2．有關(guān)鍵字序列：38,19,65,13,97,49,41,95,1,73，采用起泡排序方法進行升序排序，請寫出每趟排序的結(jié)果?！緟⒖即鸢浮棵刻似鹋菖判虻慕Y(jié)果如下所示。初始：3819651397494195173第1趟：1938136549419517397第2趟：1913384941651739597第3趟：1319384149165739597第4趟：1319384114965739597第5趟：1319381414965739597第6趟：1319138414965739597第7趟：1311938414965739597第8趟：1131938414965739597第9趟：11319384149657395973．對數(shù)據(jù)序列：66,61,200,30,80,150,4,8,100,12,20,31,1,5,44，寫出采用希爾排序算法排序的每一趟結(jié)果。設(shè)增量序列d={5,3,1}。【參考答案】每趟希爾排序的結(jié)果如下所示。初始：66612003080150481001220311544第1趟：d=520415126631830441506120010080第2趟：d=354120830311261441006620015080第3趟：d=1145812203031446166801001502004．有關(guān)鍵字序列：38,19,65,13,97,49,41,95,1,73，采用直接插入排序方法進行升序排序，請寫出每趟排序的結(jié)果?！緟⒖即鸢浮棵刻酥苯硬迦肱判虻慕Y(jié)果如下所示。初始：3819651397494195173第1趟：1938651397494195173第2趟：1938651397494195173第3趟：1319386597494195173第4趟：1319386597494195173第5趟：1319384965974195173第6趟：1319384149659795173第7趟：1319384149659597173第8趟：1131938414965959773第9趟：11319384149657395975．有關(guān)鍵字序列：38,19,65,13,97,49,41,95,1,73，采用簡單選擇排序方法進行升序排序，請寫出每趟排序的結(jié)果。【參考答案】每趟簡單選擇排序的結(jié)果如下所示。初始：3819651397494195173第1趟：1196513974941953873第2趟：1136519974941953873第3趟：1131965974941953873第4趟：1131938974941956573第5趟：1131938414997956573第6趟：1131938414997956573第7趟：1131938414965959773第8趟：1131938414965959773第9趟：11319384149659597736．對數(shù)據(jù)序列：31,5,44,55,61,200,30,60,20,1,80,150,4,29，采用改進的起泡排序方法進行降序排序，請寫出每趟排序的結(jié)果?！緟⒖即鸢浮棵刻烁倪M的起泡排序的結(jié)果如下所示。初始：315445561200306020180150429第1趟：531445561306020180150429200第2趟：531445530602016180429150200第3趟：531443055201606142980150200第4趟：531304420155604296180150200第5趟：530312014455429606180150200第6趟：530201314442955606180150200第7趟：520130314294455606180150200第8趟：512030429314455606180150200第9趟：152042930314455606180150200第10趟：154202930314455606180150200第11趟：145202930314455606180150200第12趟：1452029303144556061801502007．對數(shù)據(jù)序列：31,5,44,55,61,200,30,60,20,1,80,150,4,29，寫出采用快速排序算法排序的過程?！緟⒖即鸢浮坎捎胮artition劃分算法，快速排序算法排序的過程如下所示。初始：315445561200306020180150429第1次：295412030316061558015044200第2次：205412930316061558015044200第3次：154202930316061558015044200第4次：154202930316061558015044200第5次：145202930316061558015044200第6次：145202930314455608015020061第7次：145202930314455608015020061第8次：145202930314455606180200150第9次：1452029303144556061801502008．將數(shù)據(jù)序列：70,12,30,1,5,31,44,56,61建成一個最大堆。【參考答案】建最大堆的過程如圖7-3所示。56705670561112443130b)調(diào)整以1為根的子樹5670516112443130a)初始完全二叉樹56705670561112303144c)調(diào)整以30為根的子樹1270556161303144d)調(diào)整以12為根的子樹121270556161303144e)調(diào)整以70為根的子樹，即最大堆圖7圖7-3建最大堆的過程9．對數(shù)據(jù)序列：70,12,30,1,5,31,44,56,61，采用堆排序方法進行升序排序，請寫出每趟排序的結(jié)果。

【參考答案】習題8中已經(jīng)將數(shù)據(jù)序列建成最大堆，在此基礎(chǔ)上，進行堆排序，如圖7-4所示。1611615127056303144b)輸出堆頂70并整堆后1270556161303144a)初始最大堆61446144517012563031d)輸出堆頂56并整堆后61566517012303144c)輸出堆頂61并整堆后61306130311701256445f)輸出堆頂31并整堆后6131517012564430e)輸出堆頂44并整堆后6156153130701564412h)輸出堆頂12并整堆后6112313070156445g)輸出堆頂30并整堆后616113130705564412i)輸出堆頂5后得到排序結(jié)果圖圖7-4堆排序過程10．對數(shù)據(jù)序列：31,5,44,55,61,30,60,20,1,4,29，采用基數(shù)排序方法進行升序排序，請寫出每趟排序的結(jié)果?！緟⒖即鸢浮康谝惶朔峙涞慕Y(jié)果如圖7-5所示。6060302061311444555290123456789圖7-5圖7-5基數(shù)排序第1趟（按個位數(shù)進行排序）一趟收集的結(jié)果是：30,60,20,31,61,1,44,4,5,55,29。再進行第二趟分配，結(jié)果如圖7-6所示。01012345678941529292031313044445555616160圖7-6圖7-6基數(shù)排序第2趟（按十位數(shù)進行排序）得到排序結(jié)果：1,4,5,20,29,30,31,44,55,60,61。四、算法閱讀題1．設(shè)一系列正整數(shù)存放在一個數(shù)組中，算法evenOddSort將所有偶數(shù)存放在數(shù)組的前半部分，將所有的奇數(shù)存放在數(shù)組的后半部分。請在空白處填上適當內(nèi)容將算法補充完整。voidevenOddSort(int*data,intn) //奇偶排序{ intleft,right,mostleft=0,mostright=n-1; left=mostleft; //left從左向右找 right=mostright; //right從右向左找 for(;;){ while(（1）&&left<mostright){ left++; } while(data[right]%2!=0&&（2）){ right--; } if(left<right) swap(（3）); else break; } display(data,n); return;}【參考答案】（1）data[left]%2==0（2）right>=mostleft（3）&data[left],&data[right]五、算法設(shè)計題1．將3個關(guān)鍵字進行排序，關(guān)鍵字之間的比較次數(shù)最多為多少？試實現(xiàn)這樣一個排序方法。【參考答案】對3個關(guān)鍵字進行排序，關(guān)鍵字之間的比較次數(shù)最多為3次?？梢允褂枚鏄涿枋鲈刂g的比較過程及結(jié)果，這樣的二叉樹稱為比較樹。不妨設(shè)3個元素為a,b,c，其排序過程的比較樹如圖7-7所示。圖7-73個圖7-73個元素排序的比較樹a<b<ca<c<bc<a<bb<a<cb<c<ac<b<aa<bb<cb<ca<ca<c比較樹的葉結(jié)點表示的是排序結(jié)果，分支結(jié)點表示的是要進行的比較操作，左分支表示條件成立，右分支表示條件不成立。從根結(jié)點到葉結(jié)點的路徑上，經(jīng)過的分支結(jié)點的個數(shù)，即是能得到該葉結(jié)點所表示的排序結(jié)果而需要進行的比較操作次數(shù)。最大為3，即3個元素最多需要3次比較操作就能得到排序結(jié)果。程序?qū)崿F(xiàn)如下所示。voidthreeSort(inta,intb,intc){ if(a<b) if(b<c)printf("排序結(jié)果：%d%d%d\n",a,b,c); elseif(a<c)printf("排序結(jié)果：%d%d%d\n",a,c,b); elseprintf("排序結(jié)果：%d%d%d\n",c,a,b); elseif(b<c) if(a<c)printf("排序結(jié)果：%d%d%d\n",b,a,c); elseprintf("排序結(jié)果：%d%d%d\n",b,c,a); elseprintf("排序結(jié)果：%d%d%d\n",c,b,a);}2．設(shè)計一個算法，計算含n個元素的數(shù)據(jù)序列中的逆序數(shù)?！緟⒖即鸢浮咳绻吃豼大于其后面的任一個元素v，則u與v構(gòu)成逆序?qū)?。設(shè)數(shù)據(jù)序列保存在數(shù)組a中，元素個數(shù)為len。使用count統(tǒng)計逆序個數(shù)，初始時值為0。對a中的每個元素a[i]，查看排在其后面的每個元素a[j]，如果a[i]>a[j]，則count加1。程序?qū)崿F(xiàn)如下所示。intrever(int*a,intlen){ intcount=0; inti,j; for(i=0;i<len;i++)