樹結(jié)構(gòu)習(xí)題及答案

樹結(jié)構(gòu)習(xí)題及答案樹結(jié)構(gòu)習(xí)題及答案樹結(jié)構(gòu)習(xí)題及答案樹結(jié)構(gòu)習(xí)題及答案編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:第5章樹【例5-1】寫出如圖5-1所示的樹的葉子結(jié)點(diǎn)、非終端結(jié)點(diǎn)、每個(gè)結(jié)點(diǎn)的度及樹深度。AABCDEFGHIJ圖5-1解：（1）葉子結(jié)點(diǎn)有：B、D、F、G、H、I、J。（2）非終端結(jié)點(diǎn)有：A、C、E。（3）每個(gè)結(jié)點(diǎn)的度分別是：A的度為4，C的度為2，E的度為3，其余結(jié)點(diǎn)的度為0。（4）樹的深度為3?！纠?-2】一棵度為2的樹與一棵二叉樹有什么區(qū)別解：度為2的樹有兩個(gè)分支，但分支沒有左右之分；一棵二叉樹也有兩個(gè)分支，但有左右之分，左右子樹的次序不能交換?！纠?-3】樹與二叉樹有什么區(qū)別解：區(qū)別有兩點(diǎn)：（1）二叉樹的一個(gè)結(jié)點(diǎn)至多有兩個(gè)子樹，樹則不然；（2）二叉樹的一個(gè)結(jié)點(diǎn)的子樹有左右之分，而樹的子樹沒有次序?！纠?-4】分別畫出具有3個(gè)結(jié)點(diǎn)的樹和三個(gè)結(jié)點(diǎn)的二叉樹的所有不同形態(tài)。解：如圖5-2(a)所示，具有3個(gè)結(jié)點(diǎn)的樹有兩種不同形態(tài)。圖圖5-2(a) 如圖5-2(b)所示，具有3個(gè)結(jié)點(diǎn)的二叉樹有以下五種不同形態(tài)。圖圖5-2(b)【例5-5】如圖5-3所示的二叉樹，試分別寫出它的順序表示和鏈接表示（二叉鏈表）。解：（1）順序表示。1234567891011abcde^^^^fg（2）該二叉樹的二叉鏈表表示如圖5-4所示。aabcd∧efg圖5-4∧∧∧∧∧∧∧【例5-6】試找出滿足下列條件的所有二叉樹：（1）先序序列和中序序列相同；（2）中序序列和后序序列相同；（3）先序序列和后序序列相同。解：（1）先序序列和中序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無左孩子的非空二叉樹；（2）中序序列和后序序列相同的二叉樹為：空樹或者任一結(jié)點(diǎn)均無右孩子的非空二叉樹；（3）先序序列和后序序列相同的二叉樹為：空樹或僅有一個(gè)結(jié)點(diǎn)的二叉樹。bbacdef圖5-5【例5-7】如圖5-5所示的二叉樹，要求：（1）寫出按先序、中序、后序遍歷得到的結(jié)點(diǎn)序列。（2）畫出該二叉樹的后序線索二叉樹。解：（1） 先序遍歷序列：ABDEFC 中序遍歷序列：DEFBAC后序遍歷序列：FEDBCA（2）其后序線索二叉樹如圖5-6所示。NULLNULLcabdef圖5-6A圖5-7BCDEFA圖5-7BCDEFGHIKLMJ解：第一步，加線。第二步，抹線。第三步，旋轉(zhuǎn)。過程如圖5-8所示。A圖5-8(a)A圖5-8(a)第一步加線BCDEFGHIKLMJA圖5-8(b)第二步抹線BCDEFGHIKLMJAB圖5-8(c)第三步旋轉(zhuǎn)CFDKGELHMIJABCDEFHIJABCDEFHIJ圖5-9解：第一步，加線。第二步，抹線。第三步，調(diào)整。過程如圖5-10所示。AABDHCFEJIBACDEFHIJ第一步第二步第三步BACDEFHIJ圖5-10【例5-10】將如圖5-11所示的森林轉(zhuǎn)換成二叉樹。圖圖5-11CDEFGABHILJK解：步驟略，結(jié)果如圖5-12所示。CCDEFGABHILJK圖5-12【例5-11】假定用于通信的電文由8個(gè)字符A、B、C、D、E、F、G、H組成，各字母在電文中出現(xiàn)的概率為5％、25％、4％、7％、9％、12％、30％、8％，試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。解：根據(jù)題意，設(shè)這8個(gè)字母對(duì)應(yīng)的權(quán)值分別為（5，25，4，7，9，12，30，8），并且n=8。第一步：255479第一步：25547912308第四步：257第四步：2579123081554918第五步：257912308155491827第六步：25309549187128152743第二步：第二步：257912305498第三步：第三步：25791230549815第七步：第七步：2530954918712815274357第八步：2595491843307128152757100圖5-13（2）設(shè)計(jì)哈夫曼編碼利用第八步得到的哈夫曼樹，規(guī)定左分支用0表示，右分支用1表示，字母A、B、C、D、E、F、G、H的哈夫曼編碼如下表示：A:0011 B:01 C:0010 E:000 F:100 G:11 H:1011習(xí)題5一、單項(xiàng)選擇題1.在一棵度為3的樹中，度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為（1.C）個(gè)。A.4 B.5 C.6 D.2.假設(shè)在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為（2.B）個(gè)。A.15 B.16 C.17 D.3.假定一棵三叉樹的結(jié)點(diǎn)數(shù)為50，則它的最小高度為（3.C）。A.3 B.4 C.5 D.4.在一棵二叉樹上第4層的結(jié)點(diǎn)數(shù)最多為（4.D）。A.2 B.4 C.6 D.5.用順序存儲(chǔ)的方法將完全二叉樹中的所有結(jié)點(diǎn)逐層存放在數(shù)組中R[1..n]，結(jié)點(diǎn)R[i]若有左孩子，其左孩子的編號(hào)為結(jié)點(diǎn)（5.B）。A.R[2i+1] B.R[2i] C.R[i/2] D.R[2i-1]6.由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（6.D）。A.24 B.48 C.72 D.7.線索二叉樹是一種（7.C）結(jié)構(gòu)。A.邏輯 B.邏輯和存儲(chǔ) C.物理 D.線性8.線索二叉樹中，結(jié)點(diǎn)p沒有左子樹的充要條件是（8.B）。A.p->lc=NULL B.p->ltag=1C.p->ltag=1且p->lc=NULL D.以上都不對(duì)9.設(shè)n,m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷序列中n在m前的條件是（9.B）。A.n在m右方 B.n在m左方C.n是m的祖先 D.n是m的子孫10.如果F是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的前序就是F中結(jié)點(diǎn)的（10.B）。A.中序 B.前序 C.后序 D.層次序11.欲實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二叉樹采用（11.A）存儲(chǔ)結(jié)構(gòu)。A.三叉鏈表 B.廣義表 C.二叉鏈表 D.順序12.下面敘述正確的是（12.D）。A.二叉樹是特殊的樹B.二叉樹等價(jià)于度為2的樹C.完全二叉樹必為滿二叉樹D.二叉樹的左右子樹有次序之分13.任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（13.A）。A.不發(fā)生改變B.發(fā)生改變C.不能確定 D.以上都不對(duì)14.已知一棵完全二叉樹的結(jié)點(diǎn)總數(shù)為9個(gè)，則最后一層的結(jié)點(diǎn)數(shù)為（14.B）。A.1 B.2 C.3 D.15.根據(jù)先序序列ABDC和中序序列DBAC確定對(duì)應(yīng)的二叉樹，該二叉樹（15.A）。A.是完全二叉樹 B.不是完全二叉樹C.是滿二叉樹 D.不是滿二叉樹二、判斷題1.二叉樹中每個(gè)結(jié)點(diǎn)的度不能超過2，所以二叉樹是一種特殊的樹。 （1.×）2.二叉樹的前序遍歷中，任意結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)之前。 （2.√）3.線索二叉樹是一種邏輯結(jié)構(gòu)。 （3.×）4.哈夫曼樹的總結(jié)點(diǎn)個(gè)數(shù)（多于1時(shí)）不能為偶數(shù)。 （4.√）5.由二叉樹的先序序列和后序序列可以唯一確定一顆二叉樹。 （5.×）6.樹的后序遍歷與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同。 （6.√）7.根據(jù)任意一種遍歷序列即可唯一確定對(duì)應(yīng)的二叉樹。 （7.√）8.滿二叉樹也是完全二叉樹。 （8.√）9.哈夫曼樹一定是完全二叉樹。 （9.×）10.樹的子樹是無序的。 （10.×）三、填空題1.假定一棵樹的廣義表表示為A（B（E），C（F（H，I，J），G），D），則該樹的度為_____，樹的深度為_____，終端結(jié)點(diǎn)的個(gè)數(shù)為______，單分支結(jié)點(diǎn)的個(gè)數(shù)為______，雙分支結(jié)點(diǎn)的個(gè)數(shù)為______，三分支結(jié)點(diǎn)的個(gè)數(shù)為_______，C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為_______，其孩子結(jié)點(diǎn)為_______和_______結(jié)點(diǎn)。1.3，4，6，1，1，2，A，F(xiàn)，G2.設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有_______個(gè)。2.n+13.對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵________二叉樹時(shí)具有最小高度，即為_______，當(dāng)它為一棵單支樹具有_______高度，即為_______。3.完全，，最大，n4.由帶權(quán)為3，9，6，2，5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為___。4.555.在一棵二叉排序樹上按_______遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。5.中序6.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指針域的總數(shù)為_______個(gè)，其中_______個(gè)用于鏈接孩子結(jié)點(diǎn)，_______個(gè)空閑著。6.2n，n-1，n+17.在一棵二叉樹中，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則n0=______。7.n2+18.一棵深度為k的滿二叉樹的結(jié)點(diǎn)總數(shù)為_______，一棵深度為k的完全二叉樹的結(jié)點(diǎn)總數(shù)的最小值為_____，最大值為______。8.2k-1，2k-1，2k-19.由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，共有____種不同的形態(tài)。9.510.設(shè)高度為h的二叉樹中只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為____。10.2h-111.一棵含有n個(gè)結(jié)點(diǎn)的k叉樹，______形態(tài)達(dá)到最大深度，____形態(tài)達(dá)到最小深度。11.單支樹，完全二叉樹12.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，若一個(gè)結(jié)點(diǎn)的編號(hào)為i(1≤i≤n)，則它的左孩子結(jié)點(diǎn)的編號(hào)為________，右孩子結(jié)點(diǎn)的編號(hào)為________，雙親結(jié)點(diǎn)的編號(hào)為________。12.2i，2i+1，i/2（或i/2）13.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲(chǔ)時(shí)，鏈表中指針域的總數(shù)為_________個(gè)，其中___________個(gè)用于鏈接孩子結(jié)點(diǎn)，_____________個(gè)空閑著。13.2n，n-1，n+114.哈夫曼樹是指________________________________________________的二叉樹。14.帶權(quán)路徑長度最小15.空樹是指________________________，最小的樹是指_______________________。15.結(jié)點(diǎn)數(shù)為0，只有一個(gè)根結(jié)點(diǎn)的樹16.二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有______________和_______________兩種。16.二叉鏈表，三叉鏈表17.三叉鏈表比二叉鏈表多一個(gè)指向______________的指針域。17.雙親結(jié)點(diǎn)18.線索是指___________________________________________。18.指向結(jié)點(diǎn)前驅(qū)和后繼信息的指針19.線索鏈表中的rtag域值為_____時(shí)，表示該結(jié)點(diǎn)無右孩子，此時(shí)______域?yàn)橹赶蛟摻Y(jié)點(diǎn)后繼線索的指針。19.1，RChild20.本節(jié)中我們學(xué)習(xí)的樹的存儲(chǔ)結(jié)構(gòu)有_____________、___________和___________。20.孩子表示法，雙親表示法，長子兄弟表示法四、應(yīng)用題1.已知一棵樹邊的集合為{<i，m>，<i，n>，<e，i>，<b，e>，<b，d>，<a，b>，<g，j>，<g，k>，<c，g>，<c，f>，<h，l>，<c，h>，<a，c>}，請(qǐng)畫出這棵樹，并回答下列問題：（1）哪個(gè)是根結(jié)點(diǎn)（2）哪些是葉子結(jié)點(diǎn)（3）哪個(gè)是結(jié)點(diǎn)g的雙親（4）哪些是結(jié)點(diǎn)g的祖先（5）哪些是結(jié)點(diǎn)g的孩子（6）哪些是結(jié)點(diǎn)e的孩子（7）哪些是結(jié)點(diǎn)e的兄弟哪些是結(jié)點(diǎn)f的兄弟（8）結(jié)點(diǎn)b和n的層次號(hào)分別是什么（9）樹的深度是多少（10）以結(jié)點(diǎn)c為根的子樹深度是多少1.解答：abcdabcdegfhimnjki圖5-15其中根結(jié)點(diǎn)為a；葉子結(jié)點(diǎn)有：d、m、n、j、k、f、l；c是結(jié)點(diǎn)g的雙親；a、c是結(jié)點(diǎn)g的祖先；j、k是結(jié)點(diǎn)g的孩子；m、n是結(jié)點(diǎn)e的子孫；e是結(jié)點(diǎn)d的兄弟；g、h是結(jié)點(diǎn)f的兄弟；結(jié)點(diǎn)b和n的層次號(hào)分別是2和5；樹的深度為5。4.已知用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL，寫出該二叉樹的先序、中序和后序遍歷序列。4.解答：先序序列：ABDHIEJKCFLG