數(shù)據(jù)結(jié)構(gòu)樹(shù)練習(xí)題

1、數(shù)據(jù)結(jié)構(gòu)樹(shù)練習(xí)題一、選擇題1 、二叉樹(shù)的深度為k ，則二叉樹(shù)最多有（C ）個(gè)結(jié)點(diǎn)。A. 2kB. 2k-1 C. 2k-1D. 2k-12 、用順序存儲(chǔ)的方法，將完全二叉樹(shù)中所有結(jié)點(diǎn)按層逐個(gè)從左到右的順序存放在一維數(shù)組R1.N 中，若結(jié)點(diǎn)Ri 有右孩子，則其右孩子是（B ） 。A. R2i-1B. R2i+1C. R2iD. R2/i3、設(shè)a,b為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前面的條件是（B ）。A. a 在b的右方 B. a 在b的左方 C. a 是b的祖先 D. a 是b的子孫4、設(shè)一棵二叉樹(shù)的中序遍歷序列：badce ，后序遍歷序列：bdeca ，則二叉樹(shù)先序遍歷序列為（

2、） 。A. adbceB. decab C. debacD. abcde5 、在一棵具有5 層的滿二叉樹(shù)中結(jié)點(diǎn)總數(shù)為（A ） 。A. 31B. 32 C. 33D. 166 、由二叉樹(shù)的前序和后序遍歷序列（B ）惟一確定這棵二叉樹(shù)。A. 能B. 不能7、某二叉樹(shù)的中序序列為ABCDEFG,后序序列為 BDCAFGE,則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為（ C ）。A. 3B. 2C. 4D. 58 、若以 4,5,6,7,8A. 67作為權(quán)值構(gòu)造哈夫曼樹(shù)，則該樹(shù)的帶權(quán)路徑長(zhǎng)度為（C ） 。B. 68C. 69D. 709 、將一棵有100 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)

3、，根結(jié)點(diǎn)的編號(hào)為1 ，則編號(hào)為49 的結(jié)點(diǎn)的左孩子編號(hào)為（A ） 。A. 98B. 99C. 50D. 4810 、表達(dá)式a*(b+c)-dA. abcd+-B )。B. abc+*d-C. abc*+d-D. -+*abcd11 、對(duì)某二叉樹(shù)進(jìn)行先序遍歷的結(jié)果為ABDEFC,中序遍歷的結(jié)果為DBFEAC,則后序遍歷A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC12 、樹(shù)最適合用來(lái)表示（C ） 。A. 有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C. 元素之間具有分支層次關(guān)系的數(shù)據(jù)D. 元素之間無(wú)聯(lián)系的數(shù)據(jù)13 、表達(dá)式A*(B+C)/(D-E+F) 的后綴表達(dá)式是(CC. A

4、BC+*DE-F+/D.A. A*B+C/D-E+FB. AB*C+D/E-F+ABCDED*+/-+14 、任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（） 。A. 不發(fā)生改變B. 發(fā)生改變C. 不能確定D. 以 上 都不對(duì)15 、 假定在一棵二叉樹(shù)中，度為2 的結(jié)點(diǎn)數(shù)為15 ， 度為 1 的結(jié)點(diǎn)數(shù)為30 ， 則葉子結(jié)點(diǎn)數(shù)為（）個(gè)。A. 15B. 16C. 17D. 4716 、由權(quán)值為3， 6， 7， 2， 5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（A. 51B. 23C. 53D. 74二、判斷題()1、存在這樣的二叉樹(shù)，對(duì)它采用任何次序的遍歷，結(jié)果相同。()2、

5、中序遍歷一棵二叉排序樹(shù)的結(jié)點(diǎn)，可得到排好序的結(jié)點(diǎn)序列。()3、對(duì)于任意非空二叉樹(shù)，要設(shè)計(jì)其后序遍歷的非遞歸算法而不使用堆棧結(jié)構(gòu)，最適 合的方法是對(duì)該二叉樹(shù)采用三叉鏈表。()4、在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相同時(shí)，其編碼也相同，對(duì)于這種情況 應(yīng)做特殊處理。(T )5、一個(gè)含有n結(jié)點(diǎn)的完全二叉樹(shù)，它的高度是 log2n +1。(T )6、完全二叉樹(shù)的某結(jié)點(diǎn)若無(wú)左孩子，則它必是葉結(jié)點(diǎn)。三、填空題1、具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是log 2n +1。2、哈夫曼樹(shù)是其樹(shù)的帶權(quán)路徑長(zhǎng)度最小 的二叉樹(shù)。3、在一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)的個(gè)數(shù)是n0 ,度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2 ,則有 n0=N2+1。4、樹(shù)內(nèi)各結(jié)點(diǎn)度的 最大值 稱為樹(shù)的度。四、綜合題1、假設(shè)用于通訊白電文僅由 8個(gè)字母A、的頻率分別為：0.07 , 0.19 , 0.02 , 0.06 ,CF日C、D、E、F、G H組成，字母在電文中出現(xiàn)0.32 , 0.03 , 0.21 , 0.10。請(qǐng)為這8個(gè)字母設(shè)計(jì)A000B101C10000D1001E11F10001G01H0012、已知權(quán)值集合為5,7,2,3,6,9,要求給出哈夫曼樹(shù)，并計(jì)算帶權(quán)路徑長(zhǎng)度WPL。WPL=1