數(shù)據(jù)結(jié)構(gòu)－樹練習(xí)題一、選擇題1、二叉樹的深度為k，則二叉樹最多有（ C ）個(gè)結(jié)點(diǎn)A. 2k B. 2k-1 C. 2k-1 D. 2k-12、用順序存儲的方法，將完全二叉樹中所有結(jié)點(diǎn)按層逐個(gè)從左到右的順序存放在一維數(shù)組R[1..N]中，若結(jié)點(diǎn)R[i]有右孩子，則其右孩子是（ B ）A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i]3、設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前面的條件是（ B ）A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孫4、設(shè)一棵二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹先序遍歷序列為（ ）A. adbce B. decab C. debac D. abcde5、在一棵具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（ A ） A. 31 B. 32 C. 33 D. 166、由二叉樹的前序和后序遍歷序列（ B ）惟一確定這棵二叉樹A. 能 B. 不能7、某二叉樹的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點(diǎn)數(shù)目為（ C ）。

A. 3　 B. 2 C. 4 D. 58、若以{4,5,6,7,8}作為權(quán)值構(gòu)造哈夫曼樹，則該樹的帶權(quán)路徑長度為（ C ）A. 67　 B. 68 C. 69 D. 709、將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)的編號為1，則編號為49的結(jié)點(diǎn)的左孩子編號為（A ）A. 98　 B. 99 C. 50 D. 4810、表達(dá)式a*(b+c)-d的后綴表達(dá)式是（ B ）A. abcd+-　 B. abc+*d- C. abc*+d- D. -+*abcd11、對某二叉樹進(jìn)行先序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，則后序遍歷的結(jié)果是（ B ） A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC12、樹最適合用來表示（ C ）A. 有序數(shù)據(jù)元素 B. 無序數(shù)據(jù)元素 C. 元素之間具有分支層次關(guān)系的數(shù)據(jù) D. 元素之間無聯(lián)系的數(shù)據(jù)13、表達(dá)式A*(B+C)/(D-E+F)的后綴表達(dá)式是（ C ） A. A*B+C/D-E+F B. AB*C+D/E-F+ C. ABC+*DE-F+/ D. ABCDED*+/-+14、任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序（ ）。

A. 不發(fā)生改變　 B. 發(fā)生改變 C. 不能確定 D. 以上都不對15、假定在一棵二叉樹中，度為2的結(jié)點(diǎn)數(shù)為15，度為1的結(jié)點(diǎn)數(shù)為30，則葉子結(jié)點(diǎn)數(shù)為（ ）個(gè) A. 15 B. 16 C. 17 D. 4716、由權(quán)值為3，6，7，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ）A. 51 B. 23 C. 53 D. 74二、判斷題（ ）1、存在這樣的二叉樹，對它采用任何次序的遍歷，結(jié)果相同 ）2、中序遍歷一棵二叉排序樹的結(jié)點(diǎn)，可得到排好序的結(jié)點(diǎn)序列 ）3、對于任意非空二叉樹，要設(shè)計(jì)其后序遍歷的非遞歸算法而不使用堆棧結(jié)構(gòu)，最適合的方法是對該二叉樹采用三叉鏈表 ）4、在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相同時(shí)，其編碼也相同，對于這種情況應(yīng)做特殊處理 T ）5、一個(gè)含有n個(gè)結(jié)點(diǎn)的完全二叉樹，它的高度是?log2n?＋1 T ）6、完全二叉樹的某結(jié)點(diǎn)若無左孩子，則它必是葉結(jié)點(diǎn)三、填空題1、具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度是 ?log2n?+1 2、哈夫曼樹是其樹的帶權(quán)路徑長度 最小 的二叉樹。

3、在一棵二叉樹中，度為0的結(jié)點(diǎn)的個(gè)數(shù)是n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有 n0= N2+1 4、樹內(nèi)各結(jié)點(diǎn)度的 最大值 稱為樹的度四、綜合題1、假設(shè)用于通訊的電文僅由8個(gè)字母A、B、C、D、E、F、G、H組成，字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10請為這8個(gè)字母設(shè)計(jì)哈夫曼編碼 2、已知權(quán)值集合為{5,7,2,3,6,9}，要求給出哈夫曼樹，并計(jì)算帶權(quán)路徑長度WPLWPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=693、已知一棵二叉樹的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF畫出二叉樹的形態(tài)。