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

第五章樹(shù)與二叉樹(shù)一、單項(xiàng)選擇題1．下列關(guān)于二叉樹(shù)的敘述中，正確的是________。A．二叉樹(shù)的度為2 B．一棵二叉樹(shù)的度可以小于2C．二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2 D．二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為2答案：B。樹(shù)中結(jié)點(diǎn)的度的最大值是樹(shù)的度。對(duì)于二叉樹(shù)，每個(gè)結(jié)點(diǎn)的度可以是0、1或2。如果二叉樹(shù)僅含有根結(jié)點(diǎn)，則它的度為0。如果二叉樹(shù)中所有分支結(jié)點(diǎn)均僅含有一個(gè)子結(jié)點(diǎn)，則二叉樹(shù)的度為1。如果二叉樹(shù)中有的分支結(jié)點(diǎn)含有2個(gè)子結(jié)點(diǎn)，則二叉樹(shù)的度為2。所以二叉樹(shù)的度可以是0，可以是1，也可以是2。2．下列存儲(chǔ)形式中，不是樹(shù)的存儲(chǔ)形式的是________。A．父結(jié)點(diǎn)表示法 B．孩子結(jié)點(diǎn)表示法C．孩子-兄弟表示法 D．順序存儲(chǔ)表示法答案：D。二叉樹(shù)有順序存儲(chǔ)表示，它針對(duì)每層的最多結(jié)點(diǎn)數(shù)，在數(shù)組中預(yù)留出相應(yīng)的位置。但對(duì)于樹(shù)而言，因?yàn)槊繉咏Y(jié)點(diǎn)的個(gè)數(shù)沒(méi)有上限，所以沒(méi)有辦法在數(shù)組中預(yù)留空間。另外三種存儲(chǔ)形式都是樹(shù)的存儲(chǔ)形式。3．下列關(guān)于二叉樹(shù)的敘述中，正確的是________。I．只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0II．二叉樹(shù)的度為2III．二叉樹(shù)的左右子樹(shù)可任意交換IV．深度為K的完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹(shù)A．僅I、IV B．僅II、IV C．僅I、II、III D．僅II、III、IV答案：A。單結(jié)點(diǎn)的二叉樹(shù)只含有根結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)也是葉結(jié)點(diǎn)，度為0，所以樹(shù)的度為0。I是正確的。但二叉樹(shù)中結(jié)點(diǎn)的度可以是0、1或2，所以樹(shù)的度不一定必須是2。II不正確。二叉樹(shù)中左子樹(shù)與右子樹(shù)是不同的，不能任意交換。III不正確。滿二叉樹(shù)是完全二叉樹(shù)的特例，深度一樣的完全二叉樹(shù)與滿二叉樹(shù)，只在最后一層可能存在差異，在這一層上，完全二叉樹(shù)可能是不滿的，而滿二叉樹(shù)一定是滿的，前面的所有層中，完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)與滿二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)都是相同的。IV是正確的。4．一棵二叉樹(shù)共有20個(gè)結(jié)點(diǎn)，其中度為l的結(jié)點(diǎn)個(gè)數(shù)是7個(gè)，則葉結(jié)點(diǎn)個(gè)數(shù)是________。A．4 B．7 C．9 D．13答案：B。二叉樹(shù)中，設(shè)n0是葉結(jié)點(diǎn)的個(gè)數(shù)，n1是度為1的結(jié)點(diǎn)的個(gè)數(shù)，n2是度為2的結(jié)點(diǎn)的個(gè)數(shù)，由性質(zhì)3可知，n0=n2+1，由題目條件知n1=7，則n0+n2=20-n1=13，解得n0=7。5．深度為4的二叉樹(shù)中，結(jié)點(diǎn)個(gè)數(shù)最多是________。A．10 B．16 C．31 D．32答案：C。相同高度的滿二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)最多。深度為4的滿二叉樹(shù)的高度是5。6．對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下且從左至右進(jìn)行1至n編號(hào)，根結(jié)點(diǎn)編號(hào)為1，則對(duì)樹(shù)中任意一個(gè)編號(hào)為i的結(jié)點(diǎn)，正確的是________。A．若2i>=n，則結(jié)點(diǎn)i無(wú)左子結(jié)點(diǎn)B．若2i+1>=n，則結(jié)點(diǎn)i無(wú)右子結(jié)點(diǎn)C．若i為偶數(shù)，則i是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)D．若i為奇數(shù)，則i是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)答案：C。按照題目中給出的編號(hào)規(guī)則，結(jié)點(diǎn)i的左子結(jié)點(diǎn)是2i，右子結(jié)點(diǎn)是2i+1，故選項(xiàng)A和B中，不等式中取等號(hào)時(shí)，結(jié)論是錯(cuò)誤的。反過(guò)來(lái)看，偶數(shù)編號(hào)的結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)，奇數(shù)編號(hào)的結(jié)點(diǎn)是其父結(jié)點(diǎn)的右子結(jié)點(diǎn)，唯一的例外是根結(jié)點(diǎn)，根的編號(hào)是奇數(shù)，沒(méi)有父結(jié)點(diǎn)，所以選項(xiàng)D也是錯(cuò)誤的。7．采用順序存儲(chǔ)方式保存一棵二叉樹(shù)，根結(jié)點(diǎn)保存在數(shù)組的A[0]中，若編號(hào)為i結(jié)點(diǎn)有右子結(jié)點(diǎn)，則該子結(jié)點(diǎn)的下標(biāo)為_(kāi)_______。A．2i-1 B．2i C．2i+1 D．2i+2答案：D。基本概念。下標(biāo)從0開(kāi)始。8．在一非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊________。A．只有左子樹(shù)上的所有結(jié)點(diǎn) B．只有右子樹(shù)上的所有結(jié)點(diǎn)C．只有左子樹(shù)上的部分結(jié)點(diǎn) D．只有右子樹(shù)上的部分結(jié)點(diǎn)答案：B。中序遍歷序列中，根的前面是左子樹(shù)中所有結(jié)點(diǎn)的中序遍歷序列，后面是右子樹(shù)中所有結(jié)點(diǎn)的中序遍歷序列。9．若一棵滿二叉樹(shù)有m個(gè)葉結(jié)點(diǎn)，n個(gè)結(jié)點(diǎn)，高度為h，則下列關(guān)系式中正確的是________。A．h+m==2n B．n==h+m C．m==h-1 D．n==2h-1答案：D。滿二叉樹(shù)中，高度為h時(shí)，結(jié)點(diǎn)個(gè)數(shù)n=2h-1。10．一棵二叉樹(shù)高度為h，所有結(jié)點(diǎn)的度或?yàn)?或?yàn)?，則這棵二叉樹(shù)的結(jié)點(diǎn)數(shù)最少為_(kāi)_______。A．h+1 B．2h-1 C．2h D．2h+1答案：B。基本概念。沒(méi)有度為1的結(jié)點(diǎn)，滿二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)最多。11．設(shè)n、m為二叉樹(shù)T中的兩個(gè)結(jié)點(diǎn)，在中序遍歷序列中，n出現(xiàn)在m之前的條件是________。A．n在m左側(cè) B．n在m右側(cè) C．n是m子孫 D．n是m祖先答案：A。將二叉樹(shù)中的各結(jié)點(diǎn)向下投影成一個(gè)序列，二叉樹(shù)中若結(jié)點(diǎn)n在m的左側(cè)，則中序遍歷時(shí)先遍歷到n后遍歷到m。12．由3個(gè)結(jié)點(diǎn)可以構(gòu)造出不同形態(tài)的二叉樹(shù)的數(shù)量是________。A．3個(gè) B．4個(gè) C．5個(gè) D．6個(gè)答案：C。基本概念。13．下列四個(gè)序列中，能構(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個(gè)選項(xiàng)中給定的數(shù)據(jù)序列對(duì)應(yīng)到完全二叉樹(shù)中。如圖5-1所示?？梢钥闯?，選項(xiàng)C對(duì)應(yīng)的是堆，且是最大堆。b)選項(xiàng)b)選項(xiàng)B對(duì)應(yīng)的完全二叉樹(shù)7565103020254515a)選項(xiàng)A對(duì)應(yīng)的完全二叉樹(shù)7565152520453010c)選項(xiàng)c)選項(xiàng)C對(duì)應(yīng)的完全二叉樹(shù)7545301520256510d)選項(xiàng)D對(duì)應(yīng)的完全二叉樹(shù)7545102520306515圖5-1各圖5-1各選項(xiàng)對(duì)應(yīng)的完全二叉樹(shù)選項(xiàng)A中，元素30既小于其父結(jié)點(diǎn)75，也小于其左子結(jié)點(diǎn)45。選項(xiàng)B中，元素10既小于其父結(jié)點(diǎn)65，也小于其左子結(jié)點(diǎn)15。選項(xiàng)D中，元素10既小于其父結(jié)點(diǎn)45，也小于其左子結(jié)點(diǎn)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后，由最后一個(gè)元素10遞補(bǔ)，然后進(jìn)行整堆，10先后與65、25進(jìn)行交換，得到的新堆如圖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é)點(diǎn)。由于55大于30，故兩者相交換。同樣的原因，55與45相交換。得到最終的新堆，如圖5-3所示。圖圖5-3插入新元素后的新堆7555451520256510303016．與樹(shù)的后根遍歷序列相同的是對(duì)應(yīng)二叉樹(shù)的________。A．先序遍歷序列 B．中序遍歷序列C．后序遍歷序列 D．按層遍歷序列答案：B。基本概念。17．設(shè)森林F中有3棵樹(shù)，第1棵、第2棵和第3棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為M1、M2和M3。與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是________。A．M1 B．M3 C．M1+M2 D．M2+M3答案：D。森林F中的第2棵和第3棵樹(shù)將轉(zhuǎn)換為對(duì)應(yīng)二叉樹(shù)的右子樹(shù)。所以二叉樹(shù)根結(jié)點(diǎn)右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)等于第2棵和第3棵樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)之和。18．一個(gè)非空二叉樹(shù)的先序遍歷序列與后序遍歷序列正好互為逆序序列，則該二叉樹(shù)的形狀應(yīng)為_(kāi)_______。A．從樹(shù)根結(jié)點(diǎn)開(kāi)始左右子樹(shù)相互對(duì)稱 B．所有非葉結(jié)點(diǎn)只有向左的一個(gè)分支C．所有非葉結(jié)點(diǎn)只有向右的一個(gè)分支 D．所有非葉結(jié)點(diǎn)全部是度為1的結(jié)點(diǎn)答案：D。二叉樹(shù)退化為單鏈樹(shù)時(shí)，先序遍歷序列與后序遍歷序列正好互為逆序序列。19．設(shè)給定權(quán)值總數(shù)為n個(gè)，用其構(gòu)造的哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為_(kāi)_______。A．不確定 B．2n-1 C．2n D．2n+1答案：B。給定的權(quán)值為n個(gè)，意味著哈夫曼樹(shù)中的葉子結(jié)點(diǎn)個(gè)數(shù)為n個(gè)。哈夫曼樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)，由滿二叉樹(shù)定理可知，度為2的結(jié)點(diǎn)個(gè)數(shù)比葉結(jié)點(diǎn)個(gè)數(shù)少1，為n-1，故哈夫曼樹(shù)中結(jié)點(diǎn)總數(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。對(duì)于選項(xiàng)D中給出的編碼方案，10是101的前綴，所以不具有前綴特性。對(duì)于其他3種編碼方案，可以分別畫(huà)出對(duì)應(yīng)的編碼樹(shù)，以驗(yàn)證它們都具有前綴特性。例如，選項(xiàng)A所示編碼方案對(duì)應(yīng)的編碼樹(shù)樹(shù)形如圖5-4所示，可以看出，編碼對(duì)應(yīng)的各結(jié)點(diǎn)都是葉結(jié)點(diǎn)，以方形結(jié)點(diǎn)表示。類似地，選項(xiàng)B所示編碼方案對(duì)應(yīng)的編碼樹(shù)樹(shù)形如圖5-5所示。圖5圖5-4對(duì)應(yīng)于選項(xiàng)A的編碼樹(shù)圖5圖5-5對(duì)應(yīng)于選項(xiàng)B的編碼樹(shù)21．一棵哈夫曼樹(shù)共有215個(gè)結(jié)點(diǎn)，則樹(shù)中編碼的字符個(gè)數(shù)是________。A．107 B．108 C．215 D．214答案：B。二、填空題1．具有18個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的高度是__________。答案：5。高度為4的滿二叉樹(shù)含有15個(gè)結(jié)點(diǎn)，小于18，所以含18個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，必有結(jié)點(diǎn)位于4層（3個(gè)結(jié)點(diǎn)），所以高度為5。也可以根據(jù)二叉樹(shù)的性質(zhì)4進(jìn)行推導(dǎo)。具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為log2n+1，根據(jù)題意，log22．已知完全二叉樹(shù)的5層（根在0層）有8個(gè)葉結(jié)點(diǎn)，則整個(gè)二叉樹(shù)的結(jié)點(diǎn)數(shù)最多是__________。答案：111。由完全二叉樹(shù)的定義可知，葉結(jié)點(diǎn)只能出現(xiàn)在最后兩層中。根據(jù)題意，“5層有8個(gè)葉結(jié)點(diǎn)”，而最后兩層中都可能有葉結(jié)點(diǎn)，所以5層既可能是指二叉樹(shù)的最后一層（樹(shù)共有6層），也可能是指樹(shù)的倒數(shù)第二層（樹(shù)共有7層）。而題目中要求含“結(jié)點(diǎn)個(gè)數(shù)最多”，顯然，對(duì)于完全二叉樹(shù)來(lái)說(shuō)，7層的樹(shù)所含的結(jié)點(diǎn)個(gè)數(shù)要多于6層的樹(shù)所含的結(jié)點(diǎn)個(gè)數(shù)，所以該題中對(duì)應(yīng)到的完全二叉樹(shù)應(yīng)該有7層。前6層的結(jié)點(diǎn)總數(shù)N=除掉8個(gè)葉結(jié)點(diǎn)外，5層還有25-8=24個(gè)分支結(jié)點(diǎn)，其中每一個(gè)結(jié)點(diǎn)都有2個(gè)子結(jié)點(diǎn)（位于6層中），所以6層還有24×2=48個(gè)葉結(jié)點(diǎn)，故該完全二叉樹(shù)總的結(jié)點(diǎn)數(shù)M＝63+24×2=111。3．已知一棵二叉樹(shù)的先序遍歷結(jié)果為A,B,C,D,E,F，中序遍歷結(jié)果為C,B,A,E,D,F，則后序遍歷的結(jié)果為_(kāi)_________。答案：C,B,E,F,D,A。給定二叉樹(shù)的先序遍歷序列和中序遍歷序列，可以唯一還原該二叉樹(shù)。根據(jù)題意，二叉樹(shù)的先序遍歷結(jié)果為A,B,C,D,E,F，意味著根是A。而其中序遍歷結(jié)果為C,B,A,E,D,F，表明A的左子樹(shù)中有C,B兩個(gè)結(jié)點(diǎn)，右子樹(shù)中有E,D,F三個(gè)結(jié)點(diǎn)。對(duì)于含兩個(gè)結(jié)點(diǎn)的左子樹(shù)，其先序遍歷序列是B,C，中序遍歷序列是C,B。B是根，C是左子結(jié)點(diǎn)。對(duì)于含三個(gè)結(jié)點(diǎn)的右子樹(shù)，先序遍歷是D,E,F，中序遍歷是E,D,F。故右子樹(shù)的根是D，左子結(jié)點(diǎn)是E，右子結(jié)點(diǎn)是F。得到的二叉樹(shù)如圖5-6所示。AACBDFE圖5-6習(xí)題3的二叉樹(shù)4．二叉樹(shù)的先序遍歷結(jié)果是E,F,H,I,G,J,K，中序遍歷結(jié)果是H,F,I,E,J,K,G，該二叉樹(shù)根的右子樹(shù)的根是__________。答案：G。由先序遍歷序列E,F,H,I,G,J,K可知，E是根。從中序遍歷序列H,F,I,E,J,K,G中可知，右子樹(shù)中含有J,K,G三個(gè)結(jié)點(diǎn)，而這三個(gè)結(jié)點(diǎn)的先序遍歷序列是G,J,K，即G是該子樹(shù)的根。圖5圖5-7習(xí)題4的二叉樹(shù)EFHIKJG5．若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是__________。答案：11。根據(jù)二叉樹(shù)的性質(zhì)3（滿二叉樹(shù)定理），有n0=n2+1。由題意知，n2=10，故n0=11。與度為1的結(jié)點(diǎn)個(gè)數(shù)5無(wú)關(guān)。6．設(shè)樹(shù)T的度為4，其中度為1、2、3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4、2、1和1，則T中的葉子結(jié)點(diǎn)個(gè)數(shù)為_(kāi)_________。答案：8?？梢詫M二叉樹(shù)定理推廣到任意k叉樹(shù)中。設(shè)k叉樹(shù)中葉結(jié)點(diǎn)個(gè)數(shù)為n0，度為1的結(jié)點(diǎn)個(gè)數(shù)為n1，…，度為k的結(jié)點(diǎn)個(gè)數(shù)為nk，則。根據(jù)題意，k=4，度為1的結(jié)點(diǎn)個(gè)數(shù)為4，度為2的結(jié)點(diǎn)個(gè)數(shù)為2，度為3的結(jié)點(diǎn)個(gè)數(shù)為1，度為4的結(jié)點(diǎn)個(gè)數(shù)為1個(gè)。葉結(jié)點(diǎn)個(gè)數(shù)=(2-1)×2+(3-1)×1+(4-1)×1+1=8。7．與算術(shù)表達(dá)式a+b*(c+d/e)對(duì)應(yīng)的后綴表達(dá)式為_(kāi)_________。答案：abcde/++。使用第三章第三節(jié)介紹的表達(dá)式轉(zhuǎn)換算法，可以得到對(duì)應(yīng)于a+b*(c+d/e)的后綴表達(dá)式。或是畫(huà)出對(duì)應(yīng)于表達(dá)式的表達(dá)式樹(shù)，如圖5-8所示，然后再進(jìn)行后序遍歷，也可以得到相應(yīng)的后綴表達(dá)式。++c/de*b+a圖5-8表示a+b*(c+d/e)的表達(dá)式樹(shù)8．設(shè)森林F對(duì)應(yīng)的二叉樹(shù)為B，它有m個(gè)結(jié)點(diǎn)，B的根為p，p的右子樹(shù)結(jié)點(diǎn)個(gè)數(shù)為n，則森林F中第一棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)是__________。答案：m-n。森林F與其對(duì)應(yīng)的二叉樹(shù)B中結(jié)點(diǎn)數(shù)是相同的，都是m個(gè)結(jié)點(diǎn)。B的右子樹(shù)是由F中除第一棵樹(shù)外的其他樹(shù)轉(zhuǎn)換而來(lái)的。F中全部結(jié)點(diǎn)個(gè)數(shù)減去B中右子樹(shù)中的全部結(jié)點(diǎn)個(gè)數(shù)，即為F中第一棵樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)。9．已知二叉樹(shù)的后序遍歷序列為D,G,E,B,F,C,A，中序遍歷序列為D,B,G,E,A,C,F，則先序遍歷序列是__________。答案：A,B,D,E,G,C,F。二叉樹(shù)如圖5-9所示。圖5-9習(xí)題9的二叉樹(shù)圖5-9習(xí)題9的二叉樹(shù)ACFDGEB10．對(duì)于任何一棵二叉樹(shù)，若它有n0個(gè)葉結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，則n0=__________。答案：n2+1。11．如果深度為k的二叉樹(shù)為滿二叉樹(shù)，則樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)是__________。答案：2k+1-1。深度為k的滿二叉樹(shù)的高度h=k+1，滿二叉樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)為2h-1。12．若用二叉鏈表存儲(chǔ)二叉樹(shù)，則含有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中的空指針個(gè)數(shù)為_(kāi)_________。答案：n+1。13．設(shè)有含n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果對(duì)結(jié)點(diǎn)按照自上到下、從左到右的次序從1開(kāi)始進(jìn)行連續(xù)的編號(hào)，則第i（2≤i≤n）個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為_(kāi)_________。答案：i/2。14．設(shè)有含n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果對(duì)結(jié)點(diǎn)按照自上到下、從左到右的次序從1開(kāi)始進(jìn)行連續(xù)的編號(hào)，則第i個(gè)結(jié)點(diǎn)有左子結(jié)點(diǎn)的條件是__________。答案：2i≤n。15．假設(shè)用孩子-兄弟表示法存儲(chǔ)一個(gè)森林，則對(duì)森林進(jìn)行的先序遍歷，等同于對(duì)其孩子-兄弟鏈表進(jìn)行的__________。答案：先序遍歷。16．假設(shè)用孩子-兄弟表示法存儲(chǔ)一個(gè)森林，則森林進(jìn)行的后序遍歷，等同于對(duì)其孩子-兄弟鏈表進(jìn)行的__________。答案：中序遍歷。三、解答題1．請(qǐng)使用一棵樹(shù)表示你所在學(xué)校的院系機(jī)構(gòu)?！緟⒖即鸢浮恳粋€(gè)學(xué)校的院系機(jī)構(gòu)數(shù)目眾多，通常劃分為專業(yè)院系、職能部門(mén)、直屬單位及研究機(jī)構(gòu)等幾大類。每一類中選擇一個(gè)單位，如圖5-10所示。學(xué)校學(xué)校計(jì)算機(jī)專業(yè)網(wǎng)絡(luò)安全專業(yè)教學(xué)管理科學(xué)籍管理科多媒體服務(wù)部古籍特藏部理論物理室微分幾何室計(jì)算機(jī)學(xué)院教務(wù)部圖書(shū)館數(shù)學(xué)研究所圖5-10一個(gè)學(xué)校的院系機(jī)構(gòu)2．當(dāng)使用一棵樹(shù)描述本章目錄（第五章、節(jié)、小節(jié)）時(shí)，請(qǐng)回答下列問(wèn)題：（1）樹(shù)中共有多少個(gè)結(jié)點(diǎn)？（2）每個(gè)結(jié)點(diǎn)的度分別是多少？（3）樹(shù)的深度是多少？【參考答案】使用縮進(jìn)形式描述第五章的目錄，如下所示。第五章樹(shù)與二叉樹(shù)（5） 第一節(jié)樹(shù)的基本概念（0） 第二節(jié)二叉樹(shù)（2） 一、二叉樹(shù)的定義及其主要特性（0） 二、二叉樹(shù)的存儲(chǔ)（0） 第三節(jié)二叉樹(shù)的操作（3） 一、二叉樹(shù)的生成（0） 二、二叉樹(shù)的遍歷（0） 三、二叉樹(shù)的應(yīng)用（0） 第四節(jié)樹(shù)和森林（3） 一、樹(shù)的存儲(chǔ)結(jié)構(gòu)（0） 二、樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換（0） 三、樹(shù)和森林的遍歷（0） 第五節(jié)哈夫曼樹(shù)及哈夫曼編碼（3） 一、編碼（0） 二、哈夫曼樹(shù)（0） 三、哈夫曼編碼（0）（1）根在0層，1個(gè)結(jié)點(diǎn)。本章共有5節(jié)，即1層有5個(gè)結(jié)點(diǎn)。第一節(jié)沒(méi)有子結(jié)點(diǎn)，第二節(jié)到第五節(jié)分別有2、3、3、3個(gè)子結(jié)點(diǎn)。樹(shù)中共有1+5+2+3+3+3=17個(gè)結(jié)點(diǎn)。（2）各結(jié)點(diǎn)的度列在結(jié)點(diǎn)后的括號(hào)內(nèi)。（3）樹(shù)的深度是2。3．有4個(gè)結(jié)點(diǎn)的二叉樹(shù)共有多少種不同的樹(shù)形？分別畫(huà)出。【參考答案】有4個(gè)結(jié)點(diǎn)的二叉樹(shù)共有14種不同的樹(shù)形。所圖5-11所示。圖5圖5-11含4個(gè)結(jié)點(diǎn)的不同二叉樹(shù)樹(shù)形4．若某棵樹(shù)有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，…，nm個(gè)度為m的結(jié)點(diǎn)，問(wèn)這棵樹(shù)共有多少個(gè)葉結(jié)點(diǎn)？給出推導(dǎo)過(guò)程?！緟⒖即鸢浮咳~結(jié)點(diǎn)個(gè)數(shù)n0滿二叉樹(shù)定理可以推廣到任意m叉樹(shù)中。設(shè)m叉樹(shù)中葉結(jié)點(diǎn)數(shù)為n0，度為1的結(jié)點(diǎn)數(shù)為n1，…，度為m的結(jié)點(diǎn)數(shù)為nm。結(jié)點(diǎn)總數(shù)n=i=0mni，樹(shù)中含有的分支數(shù)B而對(duì)于度為k的結(jié)點(diǎn)，可以帶有k個(gè)分支，故樹(shù)中分支數(shù)B=i=1min5．使用同樣結(jié)構(gòu)的結(jié)點(diǎn)構(gòu)造的雙向鏈表和二叉鏈表，有什么不同？【參考答案】雙向鏈表和二叉鏈表都是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它們的結(jié)點(diǎn)結(jié)構(gòu)都是含有一個(gè)數(shù)據(jù)類型域及兩個(gè)指針類型域，結(jié)構(gòu)是相同的，但指針指向的含義是不同的。構(gòu)造的雙向鏈表是線性結(jié)構(gòu)，鏈表結(jié)點(diǎn)中的兩個(gè)指針，一個(gè)指針指向其前驅(qū)，另一個(gè)指針指向其后繼。鏈表中相鄰的兩個(gè)結(jié)點(diǎn)，可以分別通過(guò)向前的指針和向后的指針互相指示。二叉鏈表是層次結(jié)構(gòu)，結(jié)點(diǎn)中所含的兩個(gè)指針都是指向子結(jié)點(diǎn)的，任意兩個(gè)結(jié)點(diǎn)都不會(huì)出現(xiàn)相互指示的情況。knceshpknceshpad圖5圖5-12習(xí)題6的二叉樹(shù)【參考答案】先序遍歷序列：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)有某二叉樹(shù)，其先序遍歷序列是：A,B,C,D,E,F,G,H,I，中序遍歷序列是：B,C,A,E,D,G,H,F,I，畫(huà)出該二叉樹(shù)。【參考答案】得到的二叉樹(shù)如圖5-13所示。AADHBECFGI圖5-13習(xí)題7的二叉樹(shù)8．將圖5-12（習(xí)題6）所示的二叉樹(shù)還原為森林。knceshknceshpad圖5圖5-14圖5-12所示的二叉樹(shù)對(duì)應(yīng)的森林9．樹(shù)的集合表示法能用來(lái)表示二叉樹(shù)嗎？修改集合表示法，使之能表示二叉樹(shù)，以圖5-43所示的二叉樹(shù)為例，給出其集合表示?！緟⒖即鸢浮繕?shù)的集合表示法不能直接表示二叉樹(shù)。使用集合表示法表示樹(shù)的一般形式如下：(根結(jié)點(diǎn),(子樹(shù)1),(子樹(shù)2),…,(子樹(shù)n))當(dāng)根只有一棵子樹(shù)時(shí)，樹(shù)可以表示為(根結(jié)點(diǎn),(子樹(shù)1))。但對(duì)于二叉樹(shù)，一棵子樹(shù)既可能是左子樹(shù)，也可能是右子樹(shù)，使用集合表示法區(qū)分不了這種差別?？梢愿倪M(jìn)集合表示法，使用一個(gè)特殊符號(hào)作為占位符，表示空的子樹(shù)。使用改進(jìn)的集合表示法表示二叉樹(shù)的一般形式如下：(根結(jié)點(diǎn),(左子樹(shù)),(右子樹(shù)))即使子樹(shù)為空，也需要表示出來(lái)，即要占位。圖5-12（習(xí)題6）所示二叉樹(shù)的集合表示如下所示：(k,(c,(a,(),())(e,(d,(),())(h,(),()))),(n,(),(s,(p,(),()),())))可以再簡(jiǎn)化這個(gè)表示方法。當(dāng)子樹(shù)為空時(shí)，可以使用一個(gè)特殊符號(hào)表示，例如使用#替代()。采用簡(jiǎn)化表示方式后，圖5-12（習(xí)題6）所示二叉樹(shù)的集合表示如下所示：(k,(c,(a,#,#)(e,(d,#,#)(h,#,#))),(n,#,(s,(p,#,#),#)))10．給定一組權(quán)值：15,22,14,6,7,5,7，構(gòu)造一棵哈夫曼樹(shù)，并計(jì)算樹(shù)的外部帶權(quán)路徑長(zhǎng)度?！緟⒖即鸢浮砍跏紩r(shí)，如圖5-15所示。55714152267圖5-15構(gòu)造哈夫曼樹(shù)的初始步驟合并權(quán)值最小的兩棵樹(shù)，如圖5-16所示。圖5-16合并權(quán)圖5-16合并權(quán)值最小的兩棵樹(shù)714152275611持續(xù)合并權(quán)值最小的兩棵樹(shù)，直到最終得到哈夫曼樹(shù)，如圖5-17所示。注意所構(gòu)造的哈夫曼樹(shù)不是唯一的，但樹(shù)的WPL是唯一的。222256117714254714152976圖5-17圖5-17哈夫曼樹(shù)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)造的哈夫曼樹(shù)如圖5-18所示。哈夫曼編碼如表5-1所示。ffcab162855de45100圖5圖5-18哈夫曼樹(shù)表5-1哈夫曼編碼字符abcdef編碼11101111110000110注意，哈夫曼樹(shù)和哈夫曼編碼都不是唯一的。12．畫(huà)出算術(shù)表達(dá)式((a+b)+c*(d+e)+f)*(g+h)的表達(dá)式樹(shù)。fcedfced*+ba+++hg+*圖5圖5-19習(xí)題11的表達(dá)式樹(shù)13．已知一棵二叉樹(shù)T，請(qǐng)回答下列問(wèn)題。（1）如果知道T的先序遍歷序列和層序遍歷序列，是否可以唯一還原T？為什么？（2）如果知道T的中序遍歷序列和層序遍歷序列，是否可以唯一還原T？為什么？【參考答案】（1）如果知道T的先序遍歷序列和層序遍歷序列，不能唯一還原二叉樹(shù)T。圖5-20a和圖5-20b是兩棵不同的二叉樹(shù)，但它們的先序遍歷序列相同，層序遍歷序列也相同。aa)二叉樹(shù)1ABb)二叉樹(shù)1AB圖5-20兩棵二叉樹(shù)（2）如果知道T的中序遍歷序列和層序遍歷序列，可以唯一還原一棵二叉樹(shù)。層序遍歷的第一個(gè)結(jié)點(diǎn)是根，在中序遍歷序列中，根的前面是左子樹(shù)中的全部結(jié)點(diǎn)，后面是右子樹(shù)中的全部結(jié)點(diǎn)。根據(jù)這些結(jié)點(diǎn)的信息，將層序遍歷序列中除根以外的全部結(jié)點(diǎn)分為兩組，一組是由左子樹(shù)中的全部結(jié)點(diǎn)組成的，這個(gè)即是左子樹(shù)的層序遍歷序列，另一組是由右子樹(shù)中的全部結(jié)點(diǎn)組成的，這個(gè)即是右子樹(shù)的層序遍歷序列。原問(wèn)題劃分為規(guī)模更小的兩個(gè)問(wèn)題，使用遞歸方法即可求解。14．將圖5-27所示的兩棵樹(shù)合并為一棵樹(shù)，令W為R的第三個(gè)子結(jié)點(diǎn)，畫(huà)出保存該樹(shù)的存儲(chǔ)結(jié)構(gòu)。【參考答案】保存兩棵樹(shù)的存儲(chǔ)結(jié)構(gòu)是：下標(biāo)012345678910dataRABCDEFWXYZparent-7001124-4777合并后的存儲(chǔ)結(jié)構(gòu)是：下標(biāo)012345678910dataRABCDEFWXYZparent-110011240777四、算法閱讀題二叉鏈表中結(jié)點(diǎn)類的定義及二叉樹(shù)的定義如下所示。typedefintELEMType;typedefstructBNode //二叉樹(shù)結(jié)點(diǎn){ ELEMTypedata; //數(shù)據(jù)域 structBNode*left,*right; //指向左子結(jié)點(diǎn)、右子結(jié)點(diǎn)的指針}BinTNode;typedefBinTNode*BTree; //二叉樹(shù)以下程序?qū)崿F(xiàn)了二叉樹(shù)的若干基本操作，請(qǐng)?jiān)诳瞻滋幪钌线m當(dāng)內(nèi)容將算法補(bǔ)充完整。1．返回二叉樹(shù)的高度。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．返回二叉樹(shù)中度為1的結(jié)點(diǎn)個(gè)數(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é)點(diǎn)類的定義及二叉樹(shù)的定義如下所示。typedefintELEMType;typedefstructBNode //二叉樹(shù)結(jié)點(diǎn){ ELEMTypedata; //數(shù)據(jù)域 structBNode*left,*right; //指向左子結(jié)點(diǎn)、右子結(jié)點(diǎn)的指針}BinTNode;typedefBinTNode*BTree; //二叉樹(shù)說(shuō)明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ù)的功能是將二叉樹(shù)中所有結(jié)點(diǎn)的左、右子樹(shù)相互交換。4．函數(shù)CountLeave的功能是計(jì)算二叉樹(shù)中葉結(jié)點(diǎn)的數(shù)量。typedefstructBiTNode{ ElemTypedata; structBiTNode*lchild,*rchild;}*BiTree; //二叉樹(shù)結(jié)點(diǎn)定義intCountLeave(BiTreeT) //返回值為二叉樹(shù)T中葉結(jié)點(diǎn)的個(gè)數(shù){ if(!T)return（1）; if(T->lchild==NULL&&T->rchild==NULL) return（2）; else return（3）;}為使函數(shù)能夠完成指定的功能，請(qǐng)?jiān)诔绦蛑械臋M線處填入適當(dāng)?shù)膬?nèi)容?！緟⒖即鸢浮浚?）0（2）1（3）CountLeave(T->lchild)+CountLeave(T->rchild)五、算法設(shè)計(jì)題1．設(shè)二叉樹(shù)以二叉鏈表的形式存儲(chǔ)，試設(shè)計(jì)算法，返回二叉樹(shù)中度為2結(jié)點(diǎn)的個(gè)數(shù)?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。typedefintELEMType;typedefstructBNode //二叉樹(shù)結(jié)點(diǎn){ ELEMTypedata; //數(shù)據(jù)域 structBNode*left,*right; //指向左子結(jié)點(diǎn)、右子結(jié)點(diǎn)的指針}BinTNode;typedefBinTNode*BTree; //二叉樹(shù)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è)二叉樹(shù)以二叉鏈表的形式存儲(chǔ)，每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域中存放一個(gè)整數(shù)。試設(shè)計(jì)算法，求二叉樹(shù)中所有結(jié)點(diǎn)中所保存的整數(shù)之和?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。intsumofTree(BTreeroot){ if(root==NULL)return0; returnsumofTree(root->left)+sumofTree(root->right)+root->data;}3．將二叉樹(shù)中每層的結(jié)點(diǎn)個(gè)數(shù)定義為該層的寬度，各層最寬的寬度定義為二叉樹(shù)的寬度。設(shè)二叉樹(shù)以二叉鏈表的形式存儲(chǔ)，試設(shè)計(jì)算法，返回二叉樹(shù)的寬度?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。intWidthofTree(BTreeroot){ BinTNodetemp,interval; SeqBTreeQueuemyq; //使用第三章實(shí)現(xiàn)的隊(duì)列 inttreewidth=-1,count=0; printf("\nwidth\n"); initQueue(&myq); //初始化隊(duì)列myq interval.data=NA; if(root==NULL)return0; enqueue(&myq,root); //根入隊(duì)列 enqueue(&myq,&interval); //treewidth=1; printf("width1\n"); while(!isEmptyQ(&myq)){//隊(duì)列不空，意味著還有結(jié)點(diǎn)待遍歷 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)一、單項(xiàng)選擇題1．設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖所含的邊數(shù)最多是________。A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．n2答案：B。完全圖所含的邊數(shù)最多。對(duì)于無(wú)向圖，每個(gè)頂點(diǎn)都和其他頂點(diǎn)之間有邊相連，不含有頂點(diǎn)到自己的邊。每對(duì)頂點(diǎn)之間僅能有一條邊。2．含n個(gè)頂點(diǎn)的連通無(wú)向圖中，邊數(shù)至少是________。A．n-1 B．n C．n+1 D．nlogn；答案：A。含n個(gè)頂點(diǎn)的無(wú)向圖中，如果邊數(shù)少于n-1，則必定是不連通的。邊數(shù)等于n-1時(shí)，可以構(gòu)成一個(gè)連通圖。邊數(shù)多于n-1時(shí)，不僅能構(gòu)成連通圖，還一定會(huì)出現(xiàn)回路。所以n-1條邊是最少的。但并不是至少含有n-1條邊的圖一定是連通圖。比如，一個(gè)三角形加一個(gè)孤立點(diǎn)構(gòu)成的圖中，頂點(diǎn)個(gè)數(shù)為n=4，邊數(shù)為3=n-1，但圖是不連通的。含有至少n-1條邊的圖，要看邊與頂點(diǎn)的關(guān)聯(lián)情況，才能知道是不是構(gòu)成連通圖。當(dāng)邊數(shù)足夠多時(shí)，比如，含n個(gè)頂點(diǎn)的圖中至少有(n-1)(n-2)/2+1條邊時(shí)，圖一定是連通圖。(n-1)(n-2)/2條邊使得n-1個(gè)頂點(diǎn)的子圖成為完全圖，現(xiàn)在得到兩個(gè)連通分量，還剩余一條邊，在含n-1個(gè)頂點(diǎn)的連通分量中不能再增加邊了，所以這條邊只能是連接n-1個(gè)頂點(diǎn)中的任一個(gè)與唯一的孤立頂點(diǎn)，使得孤立頂點(diǎn)與這個(gè)完全子圖連通，圖成為連通圖。3．下列敘述中錯(cuò)誤的是________。A．圖的深度優(yōu)先搜索遍歷是一個(gè)遞歸過(guò)程B．圖的深度優(yōu)先搜索遍歷不適用于有向圖C．深度優(yōu)先遍歷和廣度優(yōu)先遍歷是圖遍歷的兩種基本算法D．圖的遍歷是從給定的頂點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問(wèn)一次答案：B。圖的深度優(yōu)先搜索和廣度優(yōu)先搜索是圖遍歷的兩種基本策略（選項(xiàng)C正確）。深度優(yōu)先搜索通常采用遞歸方式實(shí)現(xiàn)（選項(xiàng)A正確），既適用于對(duì)無(wú)向圖的遍歷，也適用于對(duì)有向圖的遍歷（選項(xiàng)B錯(cuò)誤）。選項(xiàng)D是圖遍歷的定義。4．無(wú)向圖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)}，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列是________。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。要完成這個(gè)題，可以先畫(huà)出題目中所給的圖，如圖6-1所示。bbeadcf圖圖6-1習(xí)題4的圖根據(jù)深度優(yōu)先搜索策略，遍歷了a,b,e三個(gè)頂點(diǎn)后，接下來(lái)應(yīng)該尋找頂點(diǎn)e的未遍歷鄰接點(diǎn)（d）進(jìn)行遍歷，而不會(huì)遍歷到頂點(diǎn)c（選項(xiàng)A是錯(cuò)誤的）。在遍歷了a,c,f三個(gè)頂點(diǎn)后，接下來(lái)應(yīng)該尋找頂點(diǎn)f的未遍歷鄰接點(diǎn)（d）進(jìn)行遍歷，而不會(huì)遍歷到頂點(diǎn)e（選項(xiàng)B是錯(cuò)誤的）。在遍歷了a,e,b三個(gè)頂點(diǎn)后，頂點(diǎn)b的所有鄰接點(diǎn)均已遍歷，應(yīng)該回退到頂點(diǎn)e，選擇e的下一個(gè)未遍歷的鄰接點(diǎn)（d）進(jìn)行遍歷，而不會(huì)遍歷到頂點(diǎn)c（選項(xiàng)C是錯(cuò)誤的）。對(duì)于選項(xiàng)D，從頂點(diǎn)a開(kāi)始遍歷，依次訪問(wèn)了頂點(diǎn)a,e,d,f,c后，c的鄰接點(diǎn)都被遍歷過(guò)了，開(kāi)始回退，到達(dá)頂點(diǎn)e后，它還有未遍歷的鄰接點(diǎn)b，訪問(wèn)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的拓?fù)湫蛄惺莀_______。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。要完成這個(gè)題，可以先畫(huà)出題目中所給的圖，如圖6-2所示。vv2v7v5v4v1v3v6圖圖6-2習(xí)題5的圖對(duì)于選項(xiàng)B，v6出現(xiàn)在v4之前，但圖中存在邊(v4,v6)，這是矛盾的，故選項(xiàng)B錯(cuò)誤。對(duì)于選項(xiàng)C，v5出現(xiàn)在v2之前，但圖中存在邊(v2,v5)，這是矛盾的，故選項(xiàng)C錯(cuò)誤。對(duì)于選項(xiàng)D，v5出現(xiàn)在v3之前，但圖中存在邊(v3,v5)，這是矛盾的，故選項(xiàng)D錯(cuò)誤。6．在有向圖G的拓?fù)渑判蛑校繇旤c(diǎn)vi在頂點(diǎn)vj之前，則下列情形不可能出現(xiàn)的是________。A．G中有弧(vi,vj) B．G中有一條從vi到vj的路徑C．G中沒(méi)有弧(vi,vj) D．G中有一條從vj到vi的路徑答案：D。在拓?fù)渑判蛑?，若有一條從vj到vi的路徑，則表明vj是vi的先決條件，必須先完成vj后才能開(kāi)始vi，那么在拓?fù)渑判蛑?，頂點(diǎn)vi不可能出現(xiàn)在頂點(diǎn)vj之前。二、解答題1．舉例說(shuō)明，帶權(quán)圖中的權(quán)值可以表示什么含義?！緟⒖即鸢浮繖?quán)值可以表示圖中很多的信息。比如，在一個(gè)反映城市間公路網(wǎng)的圖中，可以用頂點(diǎn)表示城市，邊表示道路，用邊上的權(quán)值表示兩城市間道路的里程數(shù)、走行時(shí)間、所需費(fèi)用等等，權(quán)還可以用來(lái)表示該條公路的車流量、公路等級(jí)、道路的限速等其他信息。對(duì)于一個(gè)電子線路圖，邊上的權(quán)值可以表示兩個(gè)端點(diǎn)之間的電阻、電流或電壓值。對(duì)于反映工程進(jìn)度的圖而言，邊上的權(quán)值可以表示從前一個(gè)工程到后一個(gè)工程所需要的時(shí)間等等。圖6-4一個(gè)無(wú)向圖和一個(gè)有向圖a)無(wú)向圖145321圖6-4一個(gè)無(wú)向圖和一個(gè)有向圖a)無(wú)向圖1453214532b)有向圖【參考答案】鄰接矩陣的定義如下：圖6-4a的鄰接矩陣A如下所示。A=頂點(diǎn)下標(biāo)指針頂點(diǎn)下標(biāo)指針圖6-4a的鄰接表如圖6-5a所示。圖6-4b的鄰接矩陣A如下所示。A=12001321200132403123450123443a)圖6-4a的鄰接表1012412∧345∧012344b)圖6-4b的鄰接表圖圖6-5圖6-4的鄰接表3．求圖6-4a各頂點(diǎn)的度及圖6-4b各頂點(diǎn)的入度和出席?！緟⒖即鸢浮繄D6-4a各頂點(diǎn)的度如表6-1所示。表6-1圖6-4a各頂點(diǎn)的度頂點(diǎn)12345度32232圖6-4b各頂點(diǎn)的入度和出度如表6-2所示。表6-2圖6-4b各頂點(diǎn)的入度和出度頂點(diǎn)12345入度12102出度201304．給出帶權(quán)圖6-6的鄰接矩陣和鄰接表。vv0v1v3v4v2v5v6v7627414105567326圖圖6-6帶權(quán)圖【參考答案】帶權(quán)圖鄰接矩陣的定義如下所示。圖6-6的鄰接矩陣A如下所示。A頂點(diǎn)下標(biāo)權(quán)值頂點(diǎn)下標(biāo)權(quán)值指針圖6-7圖6-6的鄰接表v圖6-7圖6-6的鄰接表v00163624v11065747v22046635v33v44v55v77v66066525414177331451017724102672354362525．給出圖6-4a的幾個(gè)不同的子圖。圖6-8圖6-4a的幾個(gè)不同的子圖14圖6-8圖6-4a的幾個(gè)不同的子圖1453214521453214532第一個(gè)是包含原圖中全部頂點(diǎn)，但沒(méi)有任何邊的子圖。第二個(gè)是包含了部分頂點(diǎn)和部分邊的子圖。第三個(gè)是包含了全部頂點(diǎn)及部分邊的子圖。第四個(gè)是原圖，圖也是自身的子圖。2314523145圖6-9無(wú)向圖【參考答案】從頂點(diǎn)1開(kāi)始的深度優(yōu)先搜索遍歷序列是12354、12453、14235、14532、13245、13542。給出其中的5種即可。7．對(duì)圖6-9，從頂點(diǎn)1開(kāi)始進(jìn)行廣度優(yōu)先搜索，試給出5種不同的遍歷序列?！緟⒖即鸢浮繌捻旤c(diǎn)1開(kāi)始的廣度優(yōu)先搜索遍歷序列是12345、12435、13245、13425、14235、14325。給出其中的5種即可。8．對(duì)圖6-9，給出它的幾棵不同的深度優(yōu)先生成樹(shù)。23145圖6-11對(duì)應(yīng)于12453的生成樹(shù)23145圖6-10對(duì)應(yīng)于23145圖6-11對(duì)應(yīng)于12453的生成樹(shù)23145圖6-10對(duì)應(yīng)于12354的生成樹(shù)231423145圖6-15對(duì)應(yīng)于13542的生成樹(shù)23145圖6-14對(duì)應(yīng)于13245的生成樹(shù)23145圖6-13對(duì)應(yīng)于14532的生成樹(shù)23145圖6-12對(duì)應(yīng)于14235的生成樹(shù)9．對(duì)圖6-9，給出它的幾棵不同的廣度優(yōu)先生成樹(shù)。23145圖6-17廣度優(yōu)先23145圖6-17廣度優(yōu)先生成樹(shù)23145圖6-16廣度優(yōu)先生成樹(shù)10．對(duì)圖6-18，使用普里姆算法求最小生成樹(shù)?！緟⒖即鸢浮?523352314527988圖6-18帶權(quán)無(wú)向圖表6-3使用普里姆算法求最小生成樹(shù)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最小生成樹(shù)352314528圖6-19最小生成樹(shù)在第二步選中了邊(2,3)而將頂點(diǎn)2加入最小生成樹(shù)T后，到頂點(diǎn)4的有最小權(quán)值的邊有兩條，分別是(1,4)和(2,4)，邊上的權(quán)都是8。所以，第三步選擇權(quán)值為8的邊時(shí)，既可以選中(1,4)也可以選中(2,4)。如果選中的是(2,4)，則得到的最小生成樹(shù)如圖6-20所示。11．對(duì)圖6-18，使用克魯斯卡爾算法求最小生成樹(shù)。【參考答案】先將邊按權(quán)值進(jì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得到的最小生成樹(shù)如圖6-21所示。35352314528圖6-22最小生成樹(shù)352314528圖6-21最小生成樹(shù)對(duì)邊進(jìn)行排序時(shí)，如果邊(2,4)排在邊(1,4)的前面，則選中的邊是(2,4)而不是(1,4)，得到的最小生成樹(shù)如圖6-22所示。①②④③⑤⑥⑦⑧⑨①②④③⑤⑥⑦⑧⑨⑩圖6-23一個(gè)有向無(wú)環(huán)圖【參考答案】拓?fù)渑判蛉缦滤尽?,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實(shí)際上，還可以寫(xiě)出更多的拓?fù)渑判?，比如?,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一個(gè)帶權(quán)圖3012453圖6-24一個(gè)帶權(quán)圖30124536782510153863107102016【參考答案】圖6-24的鄰接矩陣如下。A使用Dijkstra算法求解從頂點(diǎn)1到其余各頂點(diǎn)最短路徑的過(guò)程如圖6-25所示。終點(diǎn)從頂點(diǎn)1到各頂點(diǎn)的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求最短路徑過(guò)程14．求圖6-25所示的AOE網(wǎng)各事件的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間。3030124356251015386310710201678910814121833圖6-25圖6-25AOE網(wǎng)【參考答案】圖6-25所示AOE網(wǎng)各事件的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間如表6-5所示。表6-5各事件的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間事件最早開(kāi)始時(shí)間最遲開(kāi)始時(shí)間10021212388421215181862727三、算法設(shè)計(jì)題1．對(duì)于給定的無(wú)向圖G，采用鄰接矩陣存儲(chǔ)，試設(shè)計(jì)算法intgetD(MGraphg,VTypeu)，返回頂點(diǎn)u的度?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。intgetD(MGraphg,VTypeu){ //返回頂點(diǎn)u的度 intdegree=0,i,j; i=VerToNum(g,u); for(j=0;j<g.numVertices;j++)degree+=g.AdjMatrix[i][j]; returndegree;}無(wú)向圖中，鄰接矩陣的一行中非零元的個(gè)數(shù)即為該對(duì)應(yīng)頂點(diǎn)的度。也可以統(tǒng)計(jì)鄰接矩陣的一列中非零元的個(gè)數(shù)。2．對(duì)于給定的無(wú)向圖G，采用鄰接矩陣存儲(chǔ)，試設(shè)計(jì)算法isPath(MGraphg,VType*path)，判定給定的頂點(diǎn)序列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)部排序一、單項(xiàng)選擇題1．下列關(guān)于穩(wěn)定排序方法的敘述中，正確的是________。I．該排序算法可以處理相同的關(guān)鍵字II．該排序算法不可以處理相同的關(guān)鍵字III．該排序算法處理相同的關(guān)鍵字時(shí)能確定它們的排序結(jié)果IV．該排序算法處理相同的關(guān)鍵字時(shí)不能確定它們的排序結(jié)果A．僅I、III B．僅I、IV C．僅II、III D．僅II、IV答案：A。具有相等關(guān)鍵字的兩個(gè)記錄，經(jīng)過(guò)穩(wěn)定的排序后，它們的相對(duì)次序不改變。初始序列中是什么樣的相對(duì)次序，排序后的相對(duì)次序也是什么樣的。這是穩(wěn)定排序具有的特性。根據(jù)排序方法穩(wěn)定性的定義，可知I和III是正確的。2．下列排序方法中，排序趟數(shù)與序列的初始狀態(tài)有關(guān)的是________。A．插入排序 B．選擇排序 C．起泡排序 D．快速排序答案：D。對(duì)n個(gè)數(shù)據(jù)項(xiàng)，插入排序、選擇排序和起泡排序都需要進(jìn)行n-1趟排序。對(duì)于快速排序，序列的初始狀態(tài)不同，可能會(huì)影響劃分過(guò)程的結(jié)果，即經(jīng)過(guò)劃分后，兩個(gè)子段中所含數(shù)據(jù)的個(gè)數(shù)會(huì)不同。比如，如果每次都大致將數(shù)據(jù)一分為二，劃分的兩個(gè)子段中所含的數(shù)據(jù)個(gè)數(shù)相當(dāng)，則排序的趟數(shù)約為logn。而如果每次劃分都出現(xiàn)極端情況，一個(gè)子段為空，則排序趟數(shù)為n-1。3．若用起泡排序?qū)﹃P(guān)鍵字序列18,16,14,12,10,8進(jìn)行升序排序，所需進(jìn)行的關(guān)鍵字比較總次數(shù)是________。A．10 B．15 C．21 D．34答案：B。給定的關(guān)鍵字序列呈降序排列，要求進(jìn)行升序排序。按照起泡排序的算法，元素18要與后面的全部5個(gè)元素進(jìn)行比較，然后位于最終的排序位置。在這一趟中需要進(jìn)行5次比較。類似的，元素16要與后面的除18之外的4個(gè)元素進(jìn)行比較，最后排在18的前面。這一趟排序需要進(jìn)行4次比較。元素14排序到位的話，需要進(jìn)行3次比較。元素12排序到位的話，需要進(jìn)行2次比較。元素10排序到位的話，需要進(jìn)行1次比較。其他元素都到位了，意味著元素8也到位了。所以總的比較次數(shù)=5+4+3+2+1=15。實(shí)際上，題目中所給的關(guān)鍵字序列是降序的，對(duì)于升序序列來(lái)說(shuō)，這是最壞的初始排列。所以關(guān)鍵字比較次數(shù)最多，需要n(n-1)/2次比較。n=6時(shí)，需要15次比較。4．下列排序算法中，不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上的是________。A．快速排序 B．希爾排序 C．堆排序 D．起泡排序答案：B。采用快速排序，每趟排序都至少有一個(gè)樞軸放置到最終位置上。堆排序中，每趟都將堆頂元素放置到最終位置上。起泡排序中，每趟會(huì)選出本趟的極值（最大或最?。┓胖迷谧罱K位置上。但希爾排序不能保證。5．一組記錄的關(guān)鍵字值為46,79,56,38,40,84，利用partition劃分算法，以第一個(gè)記錄為樞軸，得到的一次劃分結(jié)果為_(kāi)_______。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選擇第一個(gè)元素做樞軸并將樞軸放到最后的位置：pivot:46847956384046此時(shí)，left對(duì)應(yīng)于84，right對(duì)應(yīng)于40。接下來(lái)，從left開(kāi)始向右尋找大于樞軸的元素，當(dāng)前元素即大于樞軸，停在84處。然后從right開(kāi)始向左尋找小于樞軸的元素，也是在當(dāng)前位置，停在40處。如下所示。847956384046↑↑leftright交換兩個(gè)元素，如下所示。407956388446↑↑leftright接下來(lái)，尋找第二對(duì)滿足條件的數(shù)據(jù)，如下所示。407956388446↑↑leftright交換兩個(gè)元素，如下所示。403856798446↑↑leftright繼續(xù)尋找下一對(duì)數(shù)據(jù)，如下所示。403856798446↑↑rightleft此時(shí)，right>left，需要將樞軸歸位，交換56與46，得到劃分結(jié)果403846798456。6．在下面的排序方法中，輔助空間為O(n)的是________。A．希爾排序 B．堆排序 C．選擇排序 D．歸并排序答案：D。希爾排序、堆排序及選擇排序都可以實(shí)現(xiàn)“原地排序”，即只需要若干個(gè)輔助變量，在保存數(shù)據(jù)的原數(shù)組空間上完成排序操作，空間復(fù)雜度是O(1)。歸并排序過(guò)程中，需要申請(qǐng)一個(gè)與原數(shù)組等大的輔助數(shù)組，空間復(fù)雜度是O(n)的。7．下列排序算法中，當(dāng)待排序數(shù)據(jù)已有序時(shí)，花費(fèi)時(shí)間反而最多的是________。A．起泡排序 B．希爾排序 C．快速排序 D．堆排序答案：C。當(dāng)待排序數(shù)據(jù)已有序時(shí)，采用最原始的樞軸選擇方法，可能導(dǎo)致所選的樞軸是數(shù)據(jù)中最小或最大的元素，這樣的樞軸將原始數(shù)據(jù)劃分為一個(gè)為空、另一個(gè)含其余全部數(shù)據(jù)的兩組，因此排序的趟數(shù)最多，花費(fèi)的時(shí)間最多。另外三個(gè)排序方法，當(dāng)待排序數(shù)據(jù)已有序時(shí)，數(shù)據(jù)交換次數(shù)達(dá)到最少，花費(fèi)的時(shí)間均能達(dá)到各排序方法的最優(yōu)情況。8．?dāng)?shù)組中有10000個(gè)元素，如果僅要求求出其中最大的4個(gè)元素，則最節(jié)省時(shí)間的算法是________。A．直接插入排序 B．希爾排序 C．快速排序 D．選擇排序答案：D。有的排序方法需要將所有數(shù)據(jù)全部排序完畢，才能知道最大的元素是哪個(gè)。有些排序方法，邊排序邊得到部分最終結(jié)果。題意要求選出10000個(gè)元素中最大的4個(gè)，顯然，使用后一類的排序方法更能節(jié)省時(shí)間，因?yàn)槌畲蟮?個(gè)數(shù)據(jù)外，其余的數(shù)據(jù)不需要完全排序。選項(xiàng)中給出的4個(gè)排序方法中，直接插入排序和希爾排序都需要將全部數(shù)據(jù)排序后才能知道最大的4個(gè)元素是什么。對(duì)于快速排序，使用樞軸將全部數(shù)據(jù)劃分為整體有序的兩部分。如果樞軸是所有數(shù)據(jù)中第k大的元素，且k<9996，則需要在較大的部分中繼續(xù)進(jìn)行劃分。劃分的趟數(shù)是不確定的。對(duì)于選擇排序，每趟排序都能選出本趟中的最大值，4趟排序后即可選出最大的4個(gè)元素。它屬于不完全排序方法（即邊排序邊得到部分最終結(jié)果）。4趟選擇排序中，需要進(jìn)行的比較操作是n-1+n-2+n-3+n-4=4n-10，交換次數(shù)不會(huì)超過(guò)比較次數(shù)。9．從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為_(kāi)_______。A．直接插入排序 B．選擇排序 C．希爾排序 D．二路歸并排序答案：A。題目中描述的正是直接插入排序的含義。10．使用數(shù)據(jù)序列10,15,20,25,30建立初始最大堆時(shí)，數(shù)據(jù)對(duì)交換的次數(shù)是________。A．1 B．2 C．3 D．4答案：C。建立初始最大堆的過(guò)程如圖7-1所示。101030251520a)初始完全二叉樹(shù)1015253020b)30與15交換3015251020c)30與10交換3015251020d)10與25交換圖7-1建初始最大堆的過(guò)程二、填空題1．對(duì)含n個(gè)數(shù)據(jù)的序列進(jìn)行排序，直接插入排序在最好情況下的時(shí)間復(fù)雜度為_(kāi)_________。答案：O(n)。初始數(shù)據(jù)已有序時(shí)，直接插入排序能達(dá)到最優(yōu)時(shí)間復(fù)雜度，從第二個(gè)元素到最后一個(gè)元素，每個(gè)元素僅需和其直接前驅(qū)進(jìn)行比較，不需要交換，即能完成排序。排序中關(guān)鍵字比較次數(shù)為n-1，交換次數(shù)為0。2．現(xiàn)有含9個(gè)關(guān)鍵字的最小堆，排在關(guān)鍵字升序第3位的元素（第3?。┧幍奈恢脗€(gè)數(shù)可能是__________。答案：6。含9個(gè)關(guān)鍵字的最小堆如圖7-2所示。堆中，a0是最小值，a1和a2都可能是第3小的值。如果a1<a2，則a3和a4也可能是第3小的值。如果a1>a2，則a5和a6也可能是第3小的值。所以，第3小的值可能位于從a1到a6的任一位置中，共6個(gè)。aa7a0a4a3a1a6a5a2a8圖7-2含9個(gè)關(guān)鍵字的最小堆3．一組記錄的關(guān)鍵字值為45,79,59,63,65,26,80,17，利用partition劃分算法，以第一個(gè)記錄為樞軸，劃分過(guò)程中，與元素79相交換的關(guān)鍵字是__________。答案：26。根據(jù)partition算法，劃分過(guò)程如下所示。初始：4579596365268017選擇第一個(gè)元素做樞軸并將樞軸放到最后的位置：pivot:451779596365268045此時(shí)，left對(duì)應(yīng)于17，right對(duì)應(yīng)于80。接下來(lái)，從left開(kāi)始向右尋找大于樞軸的元素，當(dāng)前元素即大于樞軸，停在79處。然后從right開(kāi)始向左尋找小于樞軸的元素，停在26處。如下所示。1779596365268045↑↑leftright交換兩個(gè)元素（79和26）。4．已知一組關(guān)鍵字為：45,78,57,30,40,89，利用堆排序?qū)ζ溥M(jìn)行升序排序，建立的初始堆是__________。答案：89,78,57,30,40,45。5．設(shè)關(guān)鍵字序列為16,15,32,11,6,30,22,46,7，采用基數(shù)排序進(jìn)行升序排序。若關(guān)鍵字序列保存在含9個(gè)元素的數(shù)組A中，則一趟基數(shù)排序后，元素16的下標(biāo)位置為_(kāi)_________。答案：5。一趟分配與收集后，得到的結(jié)果是30,11,32,22,15,16,6,46,7，元素16在下標(biāo)5處。三、解答題1．設(shè)一維整數(shù)數(shù)組內(nèi)保存整數(shù)序列，回答下列問(wèn)題：（1）試寫(xiě)出整數(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時(shí)，逆序?qū)ψ疃?。每個(gè)元素都和其后面的所有元素呈逆序，所以總的逆序?qū)€(gè)數(shù)=n-1+n-2+…+2+1=n(n-1)/2。2．有關(guān)鍵字序列：38,19,65,13,97,49,41,95,1,73，采用起泡排序方法進(jìn)行升序排序，請(qǐng)寫(xiě)出每趟排序的結(jié)果?！緟⒖即鸢浮棵刻似鹋菖判虻慕Y(jié)果如下所示。初始：3819651397494195173第1趟：1938136549419517397第2趟：1913384941651739597第3趟：1319384149165739597第4趟：1319384114965739597第5趟：1319381414965739597第6趟：1319138414965739597第7趟：1311938414965739597第8趟：1131938414965739597第9趟：11319384149657395973．對(duì)數(shù)據(jù)序列：66,61,200,30,80,150,4,8,100,12,20,31,1,5,44，寫(xiě)出采用希爾排序算法排序的每一趟結(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，采用直接插入排序方法進(jìn)行升序排序，請(qǐng)寫(xiě)出每趟排序的結(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ǎn)單選擇排序方法進(jìn)行升序排序，請(qǐng)寫(xiě)出每趟排序的結(jié)果?！緟⒖即鸢浮棵刻撕?jiǎn)單選擇排序的結(jié)果如下所示。初始：3819651397494195173第1趟：1196513974941953873第2趟：1136519974941953873第3趟：1131965974941953873第4趟：1131938974941956573第5趟：1131938414997956573第6趟：1131938414997956573第7趟：1131938414965959773第8趟：1131938414965959773第9趟：11319384149659597736．對(duì)數(shù)據(jù)序列：31,5,44,55,61,200,30,60,20,1,80,150,4,29，采用改進(jìn)的起泡排序方法進(jìn)行降序排序，請(qǐng)寫(xiě)出每趟排序的結(jié)果。【參考答案】每趟改進(jìn)的起泡排序的結(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．對(duì)數(shù)據(jù)序列：31,5,44,55,61,200,30,60,20,1,80,150,4,29，寫(xiě)出采用快速排序算法排序的過(guò)程?！緟⒖即鸢浮坎捎胮artition劃分算法，快速排序算法排序的過(guò)程如下所示。初始：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建成一個(gè)最大堆?！緟⒖即鸢浮拷ㄗ畲蠖训倪^(guò)程如圖7-3所示。56705670561112443130b)調(diào)整以1為根的子樹(shù)5670516112443130a)初始完全二叉樹(shù)56705670561112303144c)調(diào)整以30為根的子樹(shù)1270556161303144d)調(diào)整以12為根的子樹(shù)121270556161303144e)調(diào)整以70為根的子樹(shù)，即最大堆圖7圖7-3建最大堆的過(guò)程9．對(duì)數(shù)據(jù)序列：70,12,30,1,5,31,44,56,61，采用堆排序方法進(jìn)行升序排序，請(qǐng)寫(xiě)出每趟排序的結(jié)果。

【參考答案】習(xí)題8中已經(jīng)將數(shù)據(jù)序列建成最大堆，在此基礎(chǔ)上，進(jìn)行堆排序，如圖7-4所示。1611615127056303144b)輸出堆頂70并整堆后1270556161303144a)初始最大堆61446144517012563031d)輸出堆頂56并整堆后61566517012303144c)輸出堆頂61并整堆后61306130311701256445f)輸出堆頂31并整堆后6131517012564430e)輸出堆頂44并整堆后6156153130701564412h)輸出堆頂12并整堆后6112313070156445g)輸出堆頂30并整堆后616113130705564412i)輸出堆頂5后得到排序結(jié)果圖圖7-4堆排序過(guò)程10．對(duì)數(shù)據(jù)序列：31,5,44,55,61,30,60,20,1,4,29，采用基數(shù)排序方法進(jìn)行升序排序，請(qǐng)寫(xiě)出每趟排序的結(jié)果?！緟⒖即鸢浮康谝惶朔峙涞慕Y(jié)果如圖7-5所示。6060302061311444555290123456789圖7-5圖7-5基數(shù)排序第1趟（按個(gè)位數(shù)進(jìn)行排序）一趟收集的結(jié)果是：30,60,20,31,61,1,44,4,5,55,29。再進(jìn)行第二趟分配，結(jié)果如圖7-6所示。01012345678941529292031313044445555616160圖7-6圖7-6基數(shù)排序第2趟（按十位數(shù)進(jìn)行排序）得到排序結(jié)果：1,4,5,20,29,30,31,44,55,60,61。四、算法閱讀題1．設(shè)一系列正整數(shù)存放在一個(gè)數(shù)組中，算法evenOddSort將所有偶數(shù)存放在數(shù)組的前半部分，將所有的奇數(shù)存放在數(shù)組的后半部分。請(qǐng)?jiān)诳瞻滋幪钌线m當(dāng)內(nèi)容將算法補(bǔ)充完整。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è)計(jì)題1．將3個(gè)關(guān)鍵字進(jìn)行排序，關(guān)鍵字之間的比較次數(shù)最多為多少？試實(shí)現(xiàn)這樣一個(gè)排序方法?！緟⒖即鸢浮繉?duì)3個(gè)關(guān)鍵字進(jìn)行排序，關(guān)鍵字之間的比較次數(shù)最多為3次?？梢允褂枚鏄?shù)描述元素之間的比較過(guò)程及結(jié)果，這樣的二叉樹(shù)稱為比較樹(shù)。不妨設(shè)3個(gè)元素為a,b,c，其排序過(guò)程的比較樹(shù)如圖7-7所示。圖7-73個(gè)圖7-73個(gè)元素排序的比較樹(shù)a<b<ca<c<bc<a<bb<a<cb<c<ac<b<aa<bb<cb<ca<ca<c比較樹(shù)的葉結(jié)點(diǎn)表示的是排序結(jié)果，分支結(jié)點(diǎn)表示的是要進(jìn)行的比較操作，左分支表示條件成立，右分支表示條件不成立。從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑上，經(jīng)過(guò)的分支結(jié)點(diǎn)的個(gè)數(shù)，即是能得到該葉結(jié)點(diǎn)所表示的排序結(jié)果而需要進(jìn)行的比較操作次數(shù)。最大為3，即3個(gè)元素最多需要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è)計(jì)一個(gè)算法，計(jì)算含n個(gè)元素的數(shù)據(jù)序列中的逆序數(shù)。【參考答案】如果某元素u大于其后面的任一個(gè)元素v，則u與v構(gòu)成逆序?qū)ΑＴO(shè)數(shù)據(jù)序列保存在數(shù)組a中，元素個(gè)數(shù)為len。使用count統(tǒng)計(jì)逆序個(gè)數(shù)，初始時(shí)值為0。對(duì)a中的每個(gè)元素a[i]，查看排在其后面的每個(gè)元素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++)