數據結構與算法 習題及解答 機械自考版 -第5-8章 樹與二叉樹-查找

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

第六章圖結構一、單項選擇題1．設無向圖的頂點個數為n，則該圖所含的邊數最多是________。A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．n2答案：B。完全圖所含的邊數最多。對于無向圖，每個頂點都和其他頂點之間有邊相連，不含有頂點到自己的邊。每對頂點之間僅能有一條邊。2．含n個頂點的連通無向圖中，邊數至少是________。A．n-1 B．n C．n+1 D．nlogn；答案：A。含n個頂點的無向圖中，如果邊數少于n-1，則必定是不連通的。邊數等于n-1時，可以構成一個連通圖。邊數多于n-1時，不僅能構成連通圖，還一定會出現回路。所以n-1條邊是最少的。但并不是至少含有n-1條邊的圖一定是連通圖。比如，一個三角形加一個孤立點構成的圖中，頂點個數為n=4，邊數為3=n-1，但圖是不連通的。含有至少n-1條邊的圖，要看邊與頂點的關聯情況，才能知道是不是構成連通圖。當邊數足夠多時，比如，含n個頂點的圖中至少有(n-1)(n-2)/2+1條邊時，圖一定是連通圖。(n-1)(n-2)/2條邊使得n-1個頂點的子圖成為完全圖，現在得到兩個連通分量，還剩余一條邊，在含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)先搜索通常采用遞歸方式實現（選項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,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b答案：D。要完成這個題，可以先畫出題目中所給的圖，如圖6-1所示。bbeadcf圖圖6-1習題4的圖根據深度優(yōu)先搜索策略，遍歷了a,b,e三個頂點后，接下來應該尋找頂點e的未遍歷鄰接點（d）進行遍歷，而不會遍歷到頂點c（選項A是錯誤的）。在遍歷了a,c,f三個頂點后，接下來應該尋找頂點f的未遍歷鄰接點（d）進行遍歷，而不會遍歷到頂點e（選項B是錯誤的）。在遍歷了a,e,b三個頂點后，頂點b的所有鄰接點均已遍歷，應該回退到頂點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出現在v4之前，但圖中存在邊(v4,v6)，這是矛盾的，故選項B錯誤。對于選項C，v5出現在v2之前，但圖中存在邊(v2,v5)，這是矛盾的，故選項C錯誤。對于選項D，v5出現在v3之前，但圖中存在邊(v3,v5)，這是矛盾的，故選項D錯誤。6．在有向圖G的拓撲排序中，若頂點vi在頂點vj之前，則下列情形不可能出現的是________。A．G中有弧(vi,vj) B．G中有一條從vi到vj的路徑C．G中沒有弧(vi,vj) D．G中有一條從vj到vi的路徑答案：D。在拓撲排序中，若有一條從vj到vi的路徑，則表明vj是vi的先決條件，必須先完成vj后才能開始vi，那么在拓撲排序中，頂點vi不可能出現在頂點vj之前。二、解答題1．舉例說明，帶權圖中的權值可以表示什么含義?！緟⒖即鸢浮繖嘀悼梢员硎緢D中很多的信息。比如，在一個反映城市間公路網的圖中，可以用頂點表示城市，邊表示道路，用邊上的權值表示兩城市間道路的里程數、走行時間、所需費用等等，權還可以用來表示該條公路的車流量、公路等級、道路的限速等其他信息。對于一個電子線路圖，邊上的權值可以表示兩個端點之間的電阻、電流或電壓值。對于反映工程進度的圖而言，邊上的權值可以表示從前一個工程到后一個工程所需要的時間等等。圖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各頂點的入度和出席?！緟⒖即鸢浮繄D6-4a各頂點的度如表6-1所示。表6-1圖6-4a各頂點的度頂點12345度32232圖6-4b各頂點的入度和出度如表6-2所示。表6-2圖6-4b各頂點的入度和出度頂點12345入度12102出度201304．給出帶權圖6-6的鄰接矩陣和鄰接表。vv0v1v3v4v2v5v6v7627414105567326圖圖6-6帶權圖【參考答案】帶權圖鄰接矩陣的定義如下所示。圖6-6的鄰接矩陣A如下所示。A頂點下標權值頂點下標權值指針圖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種不同的遍歷序列。【參考答案】從頂點1開始的廣度優(yōu)先搜索遍歷序列是12345、12435、13245、13425、14235、14325。給出其中的5種即可。8．對圖6-9，給出它的幾棵不同的深度優(yōu)先生成樹。23145圖6-11對應于12453的生成樹23145圖6-10對應于23145圖6-11對應于12453的生成樹23145圖6-10對應于12354的生成樹231423145圖6-15對應于13542的生成樹23145圖6-14對應于13245的生成樹23145圖6-13對應于14532的生成樹23145圖6-12對應于14235的生成樹9．對圖6-9，給出它的幾棵不同的廣度優(yōu)先生成樹。23145圖6-17廣度優(yōu)先23145圖6-17廣度優(yōu)先生成樹23145圖6-16廣度優(yōu)先生成樹10．對圖6-18，使用普里姆算法求最小生成樹。【參考答案】3523352314527988圖6-18帶權無向圖表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的有最小權值的邊有兩條，分別是(1,4)和(2,4)，邊上的權都是8。所以，第三步選擇權值為8的邊時，既可以選中(1,4)也可以選中(2,4)。如果選中的是(2,4)，則得到的最小生成樹如圖6-20所示。11．對圖6-18，使用克魯斯卡爾算法求最小生成樹?！緟⒖即鸢浮肯葘⑦叞礄嘀颠M行升序排序，如表6-4所示。表6-4按權值排序的各條邊是否選中邊權值(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一個帶權圖3012453圖6-24一個帶權圖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網各事件的最早開始時間和最遲開始時間。3030124356251015386310710201678910814121833圖6-25圖6-25AOE網【參考答案】圖6-25所示AOE網各事件的最早開始時間和最遲開始時間如表6-5所示。表6-5各事件的最早開始時間和最遲開始時間事件最早開始時間最遲開始時間10021212388421215181862727三、算法設計題1．對于給定的無向圖G，采用鄰接矩陣存儲，試設計算法intgetD(MGraphg,VTypeu)，返回頂點u的度?！緟⒖即鸢浮砍绦驅崿F如下所示。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;}無向圖中，鄰接矩陣的一行中非零元的個數即為該對應頂點的度。也可以統計鄰接矩陣的一列中非零元的個數。2．對于給定的無向圖G，采用鄰接矩陣存儲，試設計算法isPath(MGraphg,VType*path)，判定給定的頂點序列path是否是圖中的路徑。【參考答案】程序實現如下所示。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章內部排序一、單項選擇題1．下列關于穩(wěn)定排序方法的敘述中，正確的是________。I．該排序算法可以處理相同的關鍵字II．該排序算法不可以處理相同的關鍵字III．該排序算法處理相同的關鍵字時能確定它們的排序結果IV．該排序算法處理相同的關鍵字時不能確定它們的排序結果A．僅I、III B．僅I、IV C．僅II、III D．僅II、IV答案：A。具有相等關鍵字的兩個記錄，經過穩(wěn)定的排序后，它們的相對次序不改變。初始序列中是什么樣的相對次序，排序后的相對次序也是什么樣的。這是穩(wěn)定排序具有的特性。根據排序方法穩(wěn)定性的定義，可知I和III是正確的。2．下列排序方法中，排序趟數與序列的初始狀態(tài)有關的是________。A．插入排序 B．選擇排序 C．起泡排序 D．快速排序答案：D。對n個數據項，插入排序、選擇排序和起泡排序都需要進行n-1趟排序。對于快速排序，序列的初始狀態(tài)不同，可能會影響劃分過程的結果，即經過劃分后，兩個子段中所含數據的個數會不同。比如，如果每次都大致將數據一分為二，劃分的兩個子段中所含的數據個數相當，則排序的趟數約為logn。而如果每次劃分都出現極端情況，一個子段為空，則排序趟數為n-1。3．若用起泡排序對關鍵字序列18,16,14,12,10,8進行升序排序，所需進行的關鍵字比較總次數是________。A．10 B．15 C．21 D．34答案：B。給定的關鍵字序列呈降序排列，要求進行升序排序。按照起泡排序的算法，元素18要與后面的全部5個元素進行比較，然后位于最終的排序位置。在這一趟中需要進行5次比較。類似的，元素16要與后面的除18之外的4個元素進行比較，最后排在18的前面。這一趟排序需要進行4次比較。元素14排序到位的話，需要進行3次比較。元素12排序到位的話，需要進行2次比較。元素10排序到位的話，需要進行1次比較。其他元素都到位了，意味著元素8也到位了。所以總的比較次數=5+4+3+2+1=15。實際上，題目中所給的關鍵字序列是降序的，對于升序序列來說，這是最壞的初始排列。所以關鍵字比較次數最多，需要n(n-1)/2次比較。n=6時，需要15次比較。4．下列排序算法中，不能保證每趟排序至少能將一個元素放到其最終的位置上的是________。A．快速排序 B．希爾排序 C．堆排序 D．起泡排序答案：B。采用快速排序，每趟排序都至少有一個樞軸放置到最終位置上。堆排序中，每趟都將堆頂元素放置到最終位置上。起泡排序中，每趟會選出本趟的極值（最大或最小）放置在最終位置上。但希爾排序不能保證。5．一組記錄的關鍵字值為46,79,56,38,40,84，利用partition劃分算法，以第一個記錄為樞軸，得到的一次劃分結果為________。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對應于84，right對應于40。接下來，從left開始向右尋找大于樞軸的元素，當前元素即大于樞軸，停在84處。然后從right開始向左尋找小于樞軸的元素，也是在當前位置，停在40處。如下所示。847956384046↑↑leftright交換兩個元素，如下所示。407956388446↑↑leftright接下來，尋找第二對滿足條件的數據，如下所示。407956388446↑↑leftright交換兩個元素，如下所示。403856798446↑↑leftright繼續(xù)尋找下一對數據，如下所示。403856798446↑↑rightleft此時，right>left，需要將樞軸歸位，交換56與46，得到劃分結果403846798456。6．在下面的排序方法中，輔助空間為O(n)的是________。A．希爾排序 B．堆排序 C．選擇排序 D．歸并排序答案：D。希爾排序、堆排序及選擇排序都可以實現“原地排序”，即只需要若干個輔助變量，在保存數據的原數組空間上完成排序操作，空間復雜度是O(1)。歸并排序過程中，需要申請一個與原數組等大的輔助數組，空間復雜度是O(n)的。7．下列排序算法中，當待排序數據已有序時，花費時間反而最多的是________。A．起泡排序 B．希爾排序 C．快速排序 D．堆排序答案：C。當待排序數據已有序時，采用最原始的樞軸選擇方法，可能導致所選的樞軸是數據中最小或最大的元素，這樣的樞軸將原始數據劃分為一個為空、另一個含其余全部數據的兩組，因此排序的趟數最多，花費的時間最多。另外三個排序方法，當待排序數據已有序時，數據交換次數達到最少，花費的時間均能達到各排序方法的最優(yōu)情況。8．數組中有10000個元素，如果僅要求求出其中最大的4個元素，則最節(jié)省時間的算法是________。A．直接插入排序 B．希爾排序 C．快速排序 D．選擇排序答案：D。有的排序方法需要將所有數據全部排序完畢，才能知道最大的元素是哪個。有些排序方法，邊排序邊得到部分最終結果。題意要求選出10000個元素中最大的4個，顯然，使用后一類的排序方法更能節(jié)省時間，因為除最大的4個數據外，其余的數據不需要完全排序。選項中給出的4個排序方法中，直接插入排序和希爾排序都需要將全部數據排序后才能知道最大的4個元素是什么。對于快速排序，使用樞軸將全部數據劃分為整體有序的兩部分。如果樞軸是所有數據中第k大的元素，且k<9996，則需要在較大的部分中繼續(xù)進行劃分。劃分的趟數是不確定的。對于選擇排序，每趟排序都能選出本趟中的最大值，4趟排序后即可選出最大的4個元素。它屬于不完全排序方法（即邊排序邊得到部分最終結果）。4趟選擇排序中，需要進行的比較操作是n-1+n-2+n-3+n-4=4n-10，交換次數不會超過比較次數。9．從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在已排序序列的合適位置，該排序方法稱為________。A．直接插入排序 B．選擇排序 C．希爾排序 D．二路歸并排序答案：A。題目中描述的正是直接插入排序的含義。10．使用數據序列10,15,20,25,30建立初始最大堆時，數據對交換的次數是________。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個數據的序列進行排序，直接插入排序在最好情況下的時間復雜度為__________。答案：O(n)。初始數據已有序時，直接插入排序能達到最優(yōu)時間復雜度，從第二個元素到最后一個元素，每個元素僅需和其直接前驅進行比較，不需要交換，即能完成排序。排序中關鍵字比較次數為n-1，交換次數為0。2．現有含9個關鍵字的最小堆，排在關鍵字升序第3位的元素（第3?。┧幍奈恢脗€數可能是__________。答案：6。含9個關鍵字的最小堆如圖7-2所示。堆中，a0是最小值，a1和a2都可能是第3小的值。如果a1<a2，則a3和a4也可能是第3小的值。如果a1>a2，則a5和a6也可能是第3小的值。所以，第3小的值可能位于從a1到a6的任一位置中，共6個。aa7a0a4a3a1a6a5a2a8圖7-2含9個關鍵字的最小堆3．一組記錄的關鍵字值為45,79,59,63,65,26,80,17，利用partition劃分算法，以第一個記錄為樞軸，劃分過程中，與元素79相交換的關鍵字是__________。答案：26。根據partition算法，劃分過程如下所示。初始：4579596365268017選擇第一個元素做樞軸并將樞軸放到最后的位置：pivot:451779596365268045此時，left對應于17，right對應于80。接下來，從left開始向右尋找大于樞軸的元素，當前元素即大于樞軸，停在79處。然后從right開始向左尋找小于樞軸的元素，停在26處。如下所示。1779596365268045↑↑leftright交換兩個元素（79和26）。4．已知一組關鍵字為：45,78,57,30,40,89，利用堆排序對其進行升序排序，建立的初始堆是__________。答案：89,78,57,30,40,45。5．設關鍵字序列為16,15,32,11,6,30,22,46,7，采用基數排序進行升序排序。若關鍵字序列保存在含9個元素的數組A中，則一趟基數排序后，元素16的下標位置為__________。答案：5。一趟分配與收集后，得到的結果是30,11,32,22,15,16,6,46,7，元素16在下標5處。三、解答題1．設一維整數數組內保存整數序列，回答下列問題：（1）試寫出整數序列2,3,8,6,1中的所有逆序對。（2）什么情況下，由1,2,…,n組成的序列中逆序對最多？【參考答案】（1）逆序對：(2,1),(3,1),(8,1),(6,1),(8,6)。（2）數據序列為n,n-1,…,3,2,1時，逆序對最多。每個元素都和其后面的所有元素呈逆序，所以總的逆序對個數=n-1+n-2+…+2+1=n(n-1)/2。2．有關鍵字序列：38,19,65,13,97,49,41,95,1,73，采用起泡排序方法進行升序排序，請寫出每趟排序的結果?！緟⒖即鸢浮棵刻似鹋菖判虻慕Y果如下所示。初始：3819651397494195173第1趟：1938136549419517397第2趟：1913384941651739597第3趟：1319384149165739597第4趟：1319384114965739597第5趟：1319381414965739597第6趟：1319138414965739597第7趟：1311938414965739597第8趟：1131938414965739597第9趟：11319384149657395973．對數據序列：66,61,200,30,80,150,4,8,100,12,20,31,1,5,44，寫出采用希爾排序算法排序的每一趟結果。設增量序列d={5,3,1}?！緟⒖即鸢浮棵刻讼柵判虻慕Y果如下所示。初始：66612003080150481001220311544第1趟：d=520415126631830441506120010080第2趟：d=354120830311261441006620015080第3趟：d=1145812203031446166801001502004．有關鍵字序列：38,19,65,13,97,49,41,95,1,73，采用直接插入排序方法進行升序排序，請寫出每趟排序的結果?！緟⒖即鸢浮棵刻酥苯硬迦肱判虻慕Y果如下所示。初始：3819651397494195173第1趟：1938651397494195173第2趟：1938651397494195173第3趟：1319386597494195173第4趟：1319386597494195173第5趟：1319384965974195173第6趟：1319384149659795173第7趟：1319384149659597173第8趟：1131938414965959773第9趟：11319384149657395975．有關鍵字序列：38,19,65,13,97,49,41,95,1,73，采用簡單選擇排序方法進行升序排序，請寫出每趟排序的結果?！緟⒖即鸢浮棵刻撕唵芜x擇排序的結果如下所示。初始：3819651397494195173第1趟：1196513974941953873第2趟：1136519974941953873第3趟：1131965974941953873第4趟：1131938974941956573第5趟：1131938414997956573第6趟：1131938414997956573第7趟：1131938414965959773第8趟：1131938414965959773第9趟：11319384149659597736．對數據序列：31,5,44,55,61,200,30,60,20,1,80,150,4,29，采用改進的起泡排序方法進行降序排序，請寫出每趟排序的結果。【參考答案】每趟改進的起泡排序的結果如下所示。初始：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．對數據序列：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．將數據序列：70,12,30,1,5,31,44,56,61建成一個最大堆?！緟⒖即鸢浮拷ㄗ畲蠖训倪^程如圖7-3所示。56705670561112443130b)調整以1為根的子樹5670516112443130a)初始完全二叉樹56705670561112303144c)調整以30為根的子樹1270556161303144d)調整以12為根的子樹121270556161303144e)調整以70為根的子樹，即最大堆圖7圖7-3建最大堆的過程9．對數據序列：70,12,30,1,5,31,44,56,61，采用堆排序方法進行升序排序，請寫出每趟排序的結果。

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