第五部分 樹(shù) 帶答案

第五部分樹(shù)帶答案第五部分樹(shù)帶答案第五部分樹(shù)帶答案xxx公司第五部分樹(shù)帶答案文件編號(hào)：文件日期：修訂次數(shù)：第1.0次更改批準(zhǔn)審核制定方案設(shè)計(jì)，管理制度第五部分樹(shù)一、選擇題1．高度為h(h>0)的二叉樹(shù)最少有(A)個(gè)結(jié)點(diǎn)-1C2．樹(shù)型結(jié)構(gòu)最適合用來(lái)描述(C)

A.有序的數(shù)據(jù)元素B.無(wú)序的數(shù)據(jù)元素

C.數(shù)據(jù)元素之間的具有層次關(guān)系的數(shù)據(jù)D.數(shù)據(jù)元素之間沒(méi)有關(guān)系的數(shù)據(jù)3．有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是(D)。A.log2(n)B.log2(n)+1C.log2(n+1)D.log24.(B)又是一棵滿二叉樹(shù)。A.二叉排序樹(shù) B.深度為5有31個(gè)結(jié)點(diǎn)的二叉樹(shù)C.有15個(gè)結(jié)點(diǎn)的二叉樹(shù) D.哈夫曼(Huffman)樹(shù)5.深度為k的滿二叉樹(shù)有(B)個(gè)分支結(jié)點(diǎn)。-16.若已知一棵二叉樹(shù)先序序列為ABCDEFG，中序序列為CBDAEGF，則其后序序列為(A)A

CDBGFEA

B

CDBFGEA

C

CDBAGFE

D

BCDAGFE7.二叉樹(shù)第i(i>=1)層上至多有(C

)結(jié)點(diǎn)。A、２ib、２ic、２i－１d、２i－１8.在一棵具有5層的滿二叉樹(shù)中結(jié)點(diǎn)總數(shù)為(

A)。A.31

B.32

C.33

D.169.一個(gè)二叉樹(shù)按順序方式存儲(chǔ)在一個(gè)維數(shù)組中，如圖01234567891011121314ABCDEFGHIJ則結(jié)點(diǎn)E在二叉樹(shù)的第(C)層。A、1 B、2 C、3 D、10．一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2，度為2的結(jié)點(diǎn)個(gè)數(shù)為1，則度為0的結(jié)點(diǎn)個(gè)數(shù)為(

C

)

A．4

B．5

C．6

D．711.在一棵二叉樹(shù)上第5層的結(jié)點(diǎn)數(shù)最多是(B) A8 B16 C32 D1512.設(shè)一棵完全二叉樹(shù)共有699個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為(B)。 A.349 B.350 C.255 D.35113.有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是(

D)。 A. B. C. D.14．下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是(

B)。 A.{0,10,110,1111} B.{11,10,001,101,0001} C.{00,010,0110,1000} D.{B,C,AA,AC,ABA,ABB,ABC}15．在一棵三叉樹(shù)中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)個(gè)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)個(gè)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)個(gè)數(shù)為(

C)個(gè)。 A.4 B.5 C.6 D.716．一棵二叉樹(shù)高度為h，所有結(jié)點(diǎn)的度為0或2，則這棵二叉樹(shù)最少有(B)個(gè)結(jié)點(diǎn)。 A.2h B.2h-1 C.2h+1 D.h+117．將有關(guān)二叉樹(shù)的概念推廣到三叉樹(shù)，則一棵有244個(gè)結(jié)點(diǎn)的完全三叉樹(shù)的高度是(C)。 A.4 B.5 C.6 D.718．樹(shù)有先根遍歷和后根遍歷，樹(shù)可以轉(zhuǎn)化為對(duì)應(yīng)的二叉樹(shù)。下面的說(shuō)法正確的是(B)。樹(shù)的后根遍歷與其對(duì)應(yīng)的二叉樹(shù)的后根遍歷相同樹(shù)的后根遍歷與其對(duì)應(yīng)的二叉樹(shù)的中根遍歷相同樹(shù)的先根遍歷與其對(duì)應(yīng)的二叉樹(shù)的中根遍歷相同以上都不對(duì)19．按照二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有(C)種。 A. 3 B. 4 C. 5 D.620．前序遍歷序列與中序遍歷序列相同的二叉樹(shù)為(D)。根結(jié)點(diǎn)無(wú)左子樹(shù)的二叉樹(shù)根結(jié)點(diǎn)無(wú)右子樹(shù)的二叉樹(shù)只有根結(jié)點(diǎn)的二叉樹(shù)或非葉子結(jié)點(diǎn)只有左子樹(shù)的二叉樹(shù)只有根結(jié)點(diǎn)的二叉樹(shù)或非葉子結(jié)點(diǎn)只有右子樹(shù)的二叉樹(shù)21．前序遍歷序列與后序遍歷序列相同的二叉樹(shù)為(C)。非葉子結(jié)點(diǎn)只有左子樹(shù)的二叉樹(shù)根結(jié)點(diǎn)無(wú)右子樹(shù)的二叉樹(shù)只有根結(jié)點(diǎn)的二叉樹(shù)非葉子結(jié)點(diǎn)只有右子樹(shù)的二叉樹(shù)22．設(shè)某二叉樹(shù)有如下特點(diǎn)：結(jié)點(diǎn)的子樹(shù)數(shù)目不是2就是0。這樣的一棵二叉樹(shù)中有m(m>0)個(gè)子樹(shù)為0的結(jié)點(diǎn)時(shí)，該二叉樹(shù)上的結(jié)點(diǎn)總數(shù)為(B)。 A.2m+1 B.2m-1 23．樹(shù)是結(jié)點(diǎn)的集合，它有(A)個(gè)根結(jié)點(diǎn)。二叉樹(shù)有(C)個(gè)根結(jié)點(diǎn)，按一定的規(guī)則，任一樹(shù)都可以轉(zhuǎn)換成唯一對(duì)應(yīng)的二叉樹(shù)。 A.1且只有1 B.1或多于1 C.0或1 D.至少224．當(dāng)一棵二叉樹(shù)的前序序列和中序序列分別是HGEDBFCA和EGBDHFAC時(shí)，其后序序列必是(B)，層次序列是(C)。 A.BDEAGFHC B.EBDGACFH C.HGFEDCBA D.HFGDEABC25．二叉樹(shù)中結(jié)點(diǎn)的兒子的順序是(A)A.確定的 B.可變的 C.任意的 D.未知26．在二叉樹(shù)的二叉鏈表存儲(chǔ)方式中，具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中有（C）個(gè)非空的指針域。 B.n+1D.n二、填空題1．深度為n(n>0)的二叉樹(shù)最多有_2n-1_____個(gè)結(jié)點(diǎn)。2．對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，對(duì)應(yīng)二叉鏈表中指針總數(shù)有2n個(gè)，其中n-1個(gè)用于指向孩子結(jié)點(diǎn)，n+1個(gè)指針空閑。3．一棵深度為6的滿二叉樹(shù)有__31____個(gè)非終端結(jié)點(diǎn)。4．若一棵二叉樹(shù)中有8個(gè)度為2的結(jié)點(diǎn),則它有__9___個(gè)葉子。5．樹(shù)中結(jié)點(diǎn)A的____子樹(shù)的數(shù)目_______稱為結(jié)點(diǎn)A的度。6．一棵深度為4的二叉樹(shù)最多有___15____個(gè)結(jié)點(diǎn)。7．將

樹(shù)

轉(zhuǎn)化為二叉樹(shù)時(shí)，其根結(jié)點(diǎn)的右子樹(shù)總是空的。8．哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度

最小

的樹(shù)，通常權(quán)值較大的結(jié)點(diǎn)離根結(jié)點(diǎn)

越近

。9．具有n個(gè)葉子的二叉樹(shù)，每個(gè)葉子的權(quán)值為wi(1≤i≤n)其中帶權(quán)路徑最小的二叉樹(shù)被稱為_(kāi)__哈夫曼樹(shù)或最有二叉樹(shù)______。10．若已知一棵二叉樹(shù)的先序序列為–+a*b–cd/ef，中序序列為a+b*c–d–e/f，則其后序序列為_(kāi)_abcd-*+ef/-________。11．已知一棵完全二叉樹(shù)中共有768結(jié)點(diǎn)，則該樹(shù)中共有__384___個(gè)葉子結(jié)點(diǎn)。12．已知二叉樹(shù)有50個(gè)葉子結(jié)點(diǎn)，且僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為30，則總結(jié)點(diǎn)數(shù)為129。13．對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，對(duì)應(yīng)二叉鏈表中指針總數(shù)__2n_個(gè)，其中__n-1個(gè)用于指向孩子結(jié)點(diǎn)。14．哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度__最小___的樹(shù)，通常權(quán)值較大的結(jié)點(diǎn)離根_越近____。15．一個(gè)深度為k、具有最少結(jié)點(diǎn)數(shù)的完全二叉樹(shù)，按層次用自然數(shù)依次對(duì)結(jié)點(diǎn)編號(hào)，則編號(hào)最小的葉子序號(hào)為_(kāi)__2k-2+1__，編號(hào)為i的結(jié)點(diǎn)所在的層次號(hào)是。16．一棵完全二叉樹(shù)有999個(gè)結(jié)點(diǎn)，它的深度為10，葉子結(jié)點(diǎn)數(shù)為500個(gè)。17．如果一棵樹(shù)有n1個(gè)深度為1的結(jié)點(diǎn)，n2個(gè)深度為2的結(jié)點(diǎn)，……，nm個(gè)度為m的結(jié)點(diǎn)，則該樹(shù)中葉子結(jié)點(diǎn)數(shù)為：2n2+3n3+……+m*nm+1-(n2+n3+……+nm)18．對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，該樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和為n-1。19．在一棵二叉樹(shù)中，假定雙分支結(jié)點(diǎn)數(shù)為5個(gè)，單分支結(jié)點(diǎn)個(gè)數(shù)為6個(gè)，則葉子結(jié)點(diǎn)數(shù)為6個(gè)。20．對(duì)于一棵二叉樹(shù)，若一個(gè)結(jié)點(diǎn)的編號(hào)為i，則它的左孩子結(jié)點(diǎn)的編號(hào)為2i，右孩子結(jié)點(diǎn)的編號(hào)為2i+1，雙親結(jié)點(diǎn)的編號(hào)為(i/2)下取整。21．假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為18，則它的最少深度為5，最大深度為18。三、判斷題1．完全二叉樹(shù)就是滿二叉樹(shù)。(W)2．已知一棵二叉樹(shù)的前序序列和中序序列可以唯一地構(gòu)造出該二叉樹(shù)。(R)四、算法題1．設(shè)二叉樹(shù)T的存儲(chǔ)結(jié)構(gòu)為二叉鏈表,結(jié)點(diǎn)結(jié)構(gòu)定義如下：structnode{chardata；//data為字符型structnode*lchild,*rchild；//指向左右孩子的指針}；設(shè)root為二叉樹(shù)T的根指針，對(duì)二叉樹(shù)T執(zhí)行算法traversal(root),試指出其輸出結(jié)果；算法(C函數(shù))如下：voidtraversal(structnode*root){if(root){printf("%c",root->data)；traversal(root->lchild)；printf("%c",root->data)；traversal(root->rchild)；}}ACEEFFCABGGBDD2．編寫(xiě)遞歸算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。intleaf_count(BiNode*T,int*count)/*初始化時(shí)*count=0，用其記錄T中葉子結(jié)點(diǎn)的個(gè)數(shù)*/{ if(T){ if(T->lchild==NULL&&T->rchild==NULL) *count++; else{ leaf_count(T->lchild,*count); leaf_count(T->rchild,*count); } }}五、操作題1．二叉樹(shù)有哪幾種基本形態(tài)畫(huà)圖說(shuō)明之。（5種）2．二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，并寫(xiě)出其先序、后序、中序的遍歷序列。012345678910ACBDEGFH先序：ACDEFHBG后序：DFHECGBA中序：DCFEHABG3．給定30個(gè)字符組成的電文:DDDDDAAABEEAAFCDAACABBCCCBAADD試為字符A、B、C、D、E、F設(shè)計(jì)哈夫曼(Huffman)編碼。(1)畫(huà)出相應(yīng)的哈夫曼樹(shù)；(2)分別列出A、B、C、D、E、F的哈夫曼碼；(3)計(jì)算該樹(shù)的帶權(quán)路徑長(zhǎng)度WPL。(WPL=70)4．試將森林F={T1,T2,T3,T4}轉(zhuǎn)換為一棵二叉樹(shù)。T1T2T3T45．試畫(huà)出下列二叉樹(shù)的中序線索二叉樹(shù)存儲(chǔ)結(jié)構(gòu)圖。二叉樹(shù)6．試用孩子兄弟(左孩子右兄弟)表示法畫(huà)出下列樹(shù)的存儲(chǔ)結(jié)構(gòu)圖。樹(shù)7．已知二叉樹(shù)的前序遍歷序列和中序遍歷序列分別是：B,A,C,D,F,E,G和D,C,A,F,G,E,B,試畫(huà)出該二叉樹(shù)。8．試用雙親表示法畫(huà)出下列樹(shù)T的存儲(chǔ)結(jié)構(gòu)圖。9．假定后序遍歷二叉樹(shù)的結(jié)果是A,C,B(1)試畫(huà)出所有可得到這一結(jié)果的不同形態(tài)的二叉樹(shù)；(5種)(2)分別寫(xiě)出這些二叉樹(shù)的中序遍歷序列。ABC,ACB,CAB,BAC,BCA10．有9個(gè)帶權(quán)結(jié)點(diǎn)a、b、c、d、e、f、g、h、I，分別帶權(quán)4，2，7，12，6，10，5，9，3，試以他們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù)（請(qǐng)按照左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)的次序構(gòu)造）。11．某二叉樹(shù)的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)表示如