一、選擇題
1．已知一算術表示式的中綴形式為 a+b*c-d/e，字尾形式為abc*+de/-，其字首形式為( )
a．-a+b*c/de b. -a+b*cd/e c．-+*abc/ded. -+a*bc/de
【北京航空航天大學 1999 一、3 （2分)】
2．算術表示式a+b*（c+d/e）轉為字尾表示式後為（ ）【中山大學 1999 一、5】
a．ab+cde/* b．abcdec．abcde/*++ d．abcde*/++
3. 設有一表示算術表示式的二叉樹（見下圖），
它所表示的算術表示式是（ ）
【南京理工大學1999 一、20（2分）】
a. a*b+c/(d*e)+(f-g) b. (a*b+c)/(d*e)+(f-g)
c. (a*b+c)/(d*e+（f-g）) d. a*b+c/d*e+f-g
4. 設樹t的度為4，其中度為1，2，3和4的結點個數分別為4，2，1，1 則t中的葉子數為（ ）
a．5b．6c．7d．8
【南京理工大學 2000 一、8 （1.5分）】
5. 在下述結論中，正確的是（ ）【南京理工大學 1999 一、4 （1分）】
①只有乙個結點的二叉樹的度為0; ②二叉樹的度為2； ③二叉樹的左右子樹可任意交換;
④深度為k的完全二叉樹的結點個數小於或等於深度相同的滿二叉樹。
abcd．①④
6. 設森林f對應的二叉樹為b，它有m個結點，b的根為p,p的右子樹結點個數為n,森林f中第一棵樹的結點個數是（ ）
a．m-n b．m-n-1 c．n+1 d．條件不足，無法確定 【南京理工大學2000 一、17（1.5分）】
7. 樹是結點的有限集合，它（ (1）)根結點，記為t。其餘結點分成為m（m>0）個(（2）)的集合t1，t2， …，ｔm，每個集合又都是樹，此時結點t稱為ti的父結點，ti稱為t的子結點（1≤i≤m）。
乙個結點的子結點個數稱為該結點的( （3） )。二叉樹與樹是兩個不同的概念，二叉樹也是結點的有限集合，它(（4）)根結點。可以把樹的根結點的層數定義為1，其他結點的層數等於其父結點所在層數加上1。
令t是一棵二叉樹，ki和kj是t中子結點數小於2的結點中的任意兩個，它們所在的層數分別為λki和λkj，當關係式│λki-λkj│≤1一定成立時，則稱t為一棵（(5)）。供選擇的答案：
（1）(4) a. 有0個或1個 b. 有0個或多個 c. 有且只有乙個 d. 有1個或1個以上
（2） a. 互不相交 b.允許相交 c.允許葉結點相交 d.允許樹枝結點相交
（3） a. 權 b.維數 c.次數d.序
（5） a. 豐滿樹 b.查詢樹 c.平衡樹 d.完全樹 【上海海運學院1999二、2(5分）】
8．若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數是（ ）
a．9b．11 c．15 d．不確定 【北京工商大學2001一.7(3分)】
9．在一棵三元樹中度為3的結點數為2個，度為2的結點數為1個，度為1的結點數為2個，則度為0的結點數為（ ）個
a．4b．5c．6 d．7 【哈爾濱工業大學 2001 二、2 （2分）】
10．設森林f中有三棵樹，第一，第二，第三棵樹的結點個數分別為m1，m2和m3。與森林f對應的二叉樹根結點的右子樹上的結點個數是（ ）。【北方交通大學 2001 一、16 （2分）】
a．m1b．m1+m2 c．m3d．m2+m3
11．具有10個葉結點的二叉樹中有（ ）個度為2的結點，【北京航空航天大學2000 一、5（2分)】
a．8b．9c．10d．ll
12．一棵完全二叉樹上有1001個結點，其中葉子結點的個數是（ ）【西安交通大學 1996 三、2 (3分)】
a． 250 b． 500 c．254 d．505 e．以上答案都不對
13. 設給定權值總數有n 個，其哈夫曼樹的結點總數為( ) 【福州大學 1998 一、5 (2分)】
a．不確定 b．2n c．2n+1 d．2n-1
14. 有n個葉子的哈夫曼樹的結點總數為（ ）。【青島大學 2002 二、1 （2分）】
a．不確定b．2nc．2n+1d．2n-1
15．若度為m的哈夫曼樹中，其葉結點個數為n，則非葉結點的個數為（ ）。【中科院計算所1999一、2（2分）】
a．n-1 b．n/m-1 c．(n-1)/(m-1) d． n/(m-1)-1 e．(n+1)/(m+1)-1
16. 有關二叉樹下列說法正確的是（ ）【南京理工大學 2000 一、11 （1.5分）】
a．二叉樹的度為2b．一棵二叉樹的度可以小於2
c．二叉樹中至少有乙個結點的度為2 d．二叉樹中任何乙個結點的度都為2
17．二叉樹的第i層上最多含有結點數為（ ）
【中山大學1998二、7 （2分）】【北京理工大學 2001 六、5（2分）】
a．2ib． 2i-1-1c． 2i-1d．2i -1
18. 乙個具有1025個結點的二叉樹的高h為（ ）【南京理工大學 1999 一、19 （2分）】
a．11b．10 c．11至1025之間 d．10至1024之間
19．一棵二叉樹高度為h,所有結點的度或為0，或為2，則這棵二叉樹最少有( )結點
a．2h b．2h-1 c．2h+1 d．h+1 【南京理工大學2001一、11(1.5分）】
20．對於有n 個結點的二叉樹, 其高度為（ ）【武漢交通科技大學 1996 一、5 (4分)】
a．nlog2n b．log2nc．log2n|+1 d．不確定
21. 一棵具有 n個結點的完全二叉樹的樹高度（深度）是（ ）【南京理工大學 1996一、8 （2分）】
a．logn+1 b．logn+1 c．logn d．logn-1
22．深度為h的滿m叉樹的第k層有（ ）個結點。(1=a．mk-1b．mk-1c．mh-1 d．mh-1
23．在一棵高度為k的滿二叉樹中，結點總數為（ ）【北京工商大學 2001 一、3 (3分)】
a．2k-1b．2kc．2k-1 d．log2k+1
24．高度為 k的二叉樹最大的結點數為（ ）。【山東大學 2001 二、3 (1分)】
a．2k b．2k-1c．2k -1d．2k-1-1
25. 一棵樹高為k的完全二叉樹至少有（ ）個結點【南京理工大學 1998 一、3 （2分）】
a．2k –1b. 2k-1 –1 c. 2k-1 d. 2k
26. 將有關二叉樹的概念推廣到三叉樹，則一棵有244個結點的完全三叉樹的高度（）
a．4b．5c．6d．7 【南京理工大學2000一、5 1.5分）】
27. 利用二叉鍊錶儲存樹，則根結點的右指標是（ ）。【青島大學 2001 五、5 （2分）】
a．指向最左孩子 b．指向最右孩子 c．空 d．非空
28．對二叉樹的結點從1開始進行連續編號，要求每個結點的編號大於其左、右孩子的編號，同一結點的左右孩子中，其左孩子的編號小於其右孩子的編號，可採用( )次序的遍歷實現編號。【北京理工大學 2000 一、4 （2分）】
a．先序b. 中序c. 後序d. 從根開始按層次遍歷
29．樹的後根遍歷序列等同於該樹對應的二叉樹的( ). 【北京理工大學 2001 六、6 （2分）】
a. 先序序列b. 中序序列c. 後序序列
30．若二叉樹採用二叉鍊錶儲存結構，要交換其所有分支結點左、右子樹的位置，利用( )遍歷方法最合適。
a．前序 b．中序 c．後序 d．按層次【北京航空航天大學 1999 一、4 （2分）】
31．在下列儲存形式中，哪乙個不是樹的儲存形式？（ ）【北方交通大學 2001 一、23 （2分）】
a．雙親表示法 b．孩子鍊錶表示法 c．孩子兄弟表示法 d．順序儲存表示法
32．一棵二叉樹的前序遍歷序列為abcdefg，它的中序遍歷序列可能是（ ）【北京工業大學 2001 一、2 (2分)】
第六章樹和二叉樹
樹是一類重要的非線性資料結構，是以分支關係定義的層次結構 6.1樹的定義 定義定義 樹 tree 是n n 0 個結點的有限集t，其中 有且僅有乙個特定的結點，稱為樹的根 root 當n 1時，其餘結點可分為m m 0 個互不相交的有限集t1,t2,tm，其中每乙個集合本身又是一棵樹，稱為根的子樹 ...
資料結構考研習題第六章樹和二叉樹
第六章樹和二叉樹 一 選擇題 1 已知一算術表示式的中綴形式為 a b c d e，字尾形式為abc de 其字首形式為 a a b c de b.a b cd e c abc ded.a bc de 北京航空航天大學 1999 一 3 2分 2 算術表示式a b c d e 轉為字尾表示式後為 中...
樹和二叉樹習題及答案
一 填空題 1.不相交的樹的聚集稱之為森林 2.從概念上講，樹與二叉樹是兩種不同的資料結構，將樹轉化為二叉樹的基本目的是 樹可採用孩子 兄弟鍊錶 二叉鍊錶 做儲存結構，目的是利用二叉樹的已有演算法解決樹的有關問題。3.深度為k的完全二叉樹至少有2 k 1個結點。至多有2 k 1個結點，若按自上而下，...