第6章 樹(shù)和二叉樹(shù)

第6章樹(shù)和二叉樹(shù)一、判斷題

1、二叉樹(shù)是度為2的有序樹(shù)。1、（×

）

2、完全二叉樹(shù)一定存在度為1的結(jié)點(diǎn)。2、（×）3、二叉樹(shù)的遍歷結(jié)果不是唯一的。3、（√

）4、二叉樹(shù)的遍歷是為了在應(yīng)用中找到一種線性次序。4、（√

）5、一個(gè)樹(shù)的葉子結(jié)點(diǎn)，在前序遍歷和后序遍歷下，皆以相同的相對(duì)位置出現(xiàn)。5、（√）6、用二叉樹(shù)的前序遍歷和中序遍歷可以得出二叉樹(shù)的后序遍歷。6、（√

）7、完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必是葉子。7、（√）8、完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)通常采用順序存儲(chǔ)結(jié)構(gòu)。8、（√

）9、赫夫曼樹(shù)的結(jié)點(diǎn)個(gè)數(shù)不能是偶數(shù)。9、（√）10、赫夫曼樹(shù)無(wú)左右子樹(shù)之分。10、（×）二、選擇題1、一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為（

）

A11B10C11~1025D10~1024答案：C

2、一棵二叉樹(shù)高度為h，所有結(jié)點(diǎn)的度或?yàn)?、或?yàn)?，則這棵二叉樹(shù)最少有（）個(gè)結(jié)點(diǎn)。

A．2hB．2h-1C．2h+1D．h+1答案：B

3、有關(guān)二叉樹(shù)下列說(shuō)法正確的是（）

A．二叉樹(shù)的度為2B．一棵二叉樹(shù)的度可以小于2C．二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2D．二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為2答案：B4、對(duì)二叉樹(shù)的結(jié)點(diǎn)從1開(kāi)始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用（）次序的遍歷實(shí)現(xiàn)編號(hào)。A．先序B.中序C.后序D.從根開(kāi)始按層次遍歷答案：C

5、由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹(shù)？（）

A．2B．3C．4D．5答案：D

6、某二叉樹(shù)T有n個(gè)結(jié)點(diǎn)，設(shè)按某種順序?qū)中的每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)為1，2，…，n，且有如下性質(zhì)：T中任一結(jié)點(diǎn)V，其編號(hào)等于左子樹(shù)上的最小編號(hào)減1，而V的右子樹(shù)的結(jié)點(diǎn)中，其最小編號(hào)等于V左子樹(shù)上結(jié)點(diǎn)的最大編號(hào)加1。這時(shí)是按（）編號(hào)的。

A.中序遍歷序列B.前序遍歷序列

C.后序遍歷序列D.層次順序答案：B7、一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿足（）A．所有的結(jié)點(diǎn)均無(wú)左孩子B．所有的結(jié)點(diǎn)均無(wú)右孩子C．只有一個(gè)葉子結(jié)點(diǎn)D．是任意一棵二叉樹(shù)答案：C8、在二叉樹(shù)結(jié)點(diǎn)的先序序列，中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（）

A．都不相同

B．完全相同

C．先序和中序相同，而與后序不同

D．中序和后序相同，而與先序不同答案：B9、二叉樹(shù)的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷:HFIEJKG。該二叉樹(shù)根的右子樹(shù)的根是：

A

EB

FC

GD

H答案：C10、已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為()

A．-A+B*C/DE

B.-A+B*CD/E

C．-+*ABC/DED.-+A*BC/DE答案：D11、算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（）

A．a(chǎn)b+cde/*

B．a(chǎn)bcde/+*+

C．a(chǎn)bcde/*++D．a(chǎn)bcde*/++答案：B12、設(shè)樹(shù)T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4、2、1、1則T中的葉子數(shù)為（）

A．5B．6C．7D．8答案：D13、在一棵三元樹(shù)中度為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ù)為（）個(gè)

A．4

B．5C．6D．7

答案：C14、設(shè)給定權(quán)值總數(shù)有n個(gè)，其哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為（）

A．不確定

B．2n

C．2n+1

D．2n-1答案：D15、有n個(gè)葉子的哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為（）。

A．不確定

B．2n

C．2n+1

D．2n-1答案：D16、下述編碼中哪一個(gè)不是前綴碼（）。

A

（00，01，10，11）

B

（0，1，00，11）

C

（0，10，110，111）

D

（1，01，000，001）答案：B17、下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（）。

A．{0，10，110，1111}

B．{11，10，001，101，0001}

C．{00，010，0110，1000}

D．{b，c，aa，ac，aba，abb，abc}答案：B三、二叉樹(shù)遍歷、構(gòu)建、應(yīng)用1、二叉樹(shù)遍歷

先序中序后序遍歷的序列遍歷的算法2、二叉樹(shù)構(gòu)建已知二叉樹(shù)的前序（或后序）、中序，構(gòu)建二叉樹(shù)已知二叉鏈表的先序訪問(wèn)字符序列，構(gòu)建二叉樹(shù)，如先序訪問(wèn)串為：ABC??DE?G??F???3、二叉樹(shù)應(yīng)用構(gòu)建赫夫曼樹(shù)赫夫曼編碼

若一棵赫夫曼樹(shù)共有9個(gè)頂點(diǎn)，則其葉子節(jié)點(diǎn)的個(gè)數(shù)為多少？

因?yàn)椋汉辗蚵鼧?shù)的構(gòu)造過(guò)程是每權(quán)值小的結(jié)點(diǎn)產(chǎn)生一個(gè)新的根結(jié)點(diǎn)

所以：從赫夫曼樹(shù)的構(gòu)造特征可知一個(gè)根結(jié)點(diǎn)要么