數(shù)據(jù)結構樹練習題

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

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

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

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

5、中序遍歷一棵二叉排序樹的結點，可得到排好序的結點序列。()3、對于任意非空二叉樹，要設計其后序遍歷的非遞歸算法而不使用堆棧結構，最適 合的方法是對該二叉樹采用三叉鏈表。()4、在哈夫曼編碼中，當兩個字符出現(xiàn)的頻率相同時，其編碼也相同，對于這種情況 應做特殊處理。(T )5、一個含有n結點的完全二叉樹，它的高度是 log2n +1。(T )6、完全二叉樹的某結點若無左孩子，則它必是葉結點。三、填空題1、具有n個結點的完全二叉樹的深度是log 2n +1。2、哈夫曼樹是其樹的帶權路徑長度最小 的二叉樹。3、在一棵二叉樹中，度為0的結點的個數(shù)是n0 ,度為2的結點的個數(shù)為n2 ,則有 n0=N2+1。4、樹內各結點度的 最大值 稱為樹的度。四、綜合題1、假設用于通訊白電文僅由 8個字母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。請為這8個字母設計A000B101C10000D1001E11F10001G01H0012、已知權值集合為5,7,2,3,6,9,要求給出哈夫曼樹，并計算帶權路徑長度WPL。WPL=1