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

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

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

3、1，則編號為49的結點的左孩子編號為（a ）。a. 98b. 99c. 50d. 4810、表達式a*(b+c)-d的后綴表達式是（ b ）。a. abcd+-b. abc+*d-c. abc*+d- d. -+*abcd11、對某二叉樹進行先序遍歷的結果為abdefc，中序遍歷的結果為dbfeac，則后序遍歷的結果是（ b ）。a. dbfeacb. dfebcac. bdfecad. bdefac12、樹最適合用來表示（ c ）。a. 有序數(shù)據元素 b. 無序數(shù)據元素 c. 元素之間具有分支層次關系的數(shù)據 d. 元素之間無聯(lián)系的數(shù)據13、表達式a*(b+c)/(d-e+f)的后綴表達式是（

4、 c ）a. a*b+c/d-e+fb. ab*c+d/e-f+c. abc+*de-f+/d. 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. 53 d. 74二、判斷題（ ）1、存在這樣的二叉樹，對它采用任何次序的遍歷，結果相同。（ ）2、中

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