一．選擇題
1.設高度為h的二叉樹只有為0和2的結點，則此類二叉樹的結點數至少有（）個，至多有幾個（）
a.2h b.2h-1 c.2h+1 d.2h-1 e.2h-1 f.2h+1
2.高度為h的完全二叉樹有（）個結點，至多有（）個結點。
a.2h b. 2h-1 c. 2h+1 d. 2h-1
3.具有n個結點的滿二叉樹有（）個葉結點。
a.n/2 b.(n-1)/2 c.(n+1)/2 d.n/2+1
4.一棵具有n個葉節點的哈夫曼樹，共有（）個結點。
a.2n b. 2n-1 c.2n+1 d.2n-1
5.一棵具有25個結點的完全二叉樹最多有（）個結點。
a.48 b.49 c.50 d.51
6.已知二叉樹的前序遍歷序列為abcdef，中序遍歷序列為cbaedf，則後序遍歷序列是（）。
a.cbefda b.fedcba c.cbedfa d.不定
7.已知二叉樹的中序遍歷序列是debac,後序遍歷序列是dabec,則前序遍歷序列是（）。
a.acbed d.cedba
8.下面4棵二叉樹中，（）不是完全二叉樹。
abcd
9.**索化二叉樹中，t所指結點沒有左子樹的充分必要條件是（）。
a.t->left=null b. t->ltag=1 c. t->left=null且t->ltag=1 d.以上都不對
10.下列線索二叉樹中（用虛線表示線索），符合後續線索樹的定義的是（）。
11.算術表示式a+b*(c+d/c)轉換為字尾表示式是（ ）。
a．ab+cdeb．abcde/+*+
c．abcded. abcde*/++
12.具有10個葉結點的二叉樹中有（ ）個度為2的結點。
a．8b.9c.10d.11
13.乙個具有1025個結點的二叉樹的高h為（ ）。
a.11b.10 c.11~1025 d.10~1024
14.前序遍歷與中序遍歷結果相同的二叉樹為（ ）；前序遍歷和後序遍歷結果相同
的二叉樹為（ ）的二叉樹。
a.空二叉樹
b.只有根結點
c.根結點無左孩子
d.根結點無右孩子
15.一棵非空二叉樹的先序遍歷序列與後序遍歷序列正好相反，則該二叉樹一定滿足
（ ）。
a.所有非葉結點均無左孩子 b.所有非葉結點均無右孩子
c.只有乙個葉子結點d.a和b同時成立
16.某二叉樹的中序序列和後序序列正好相反，則該二叉樹一定是（ ）的二叉樹。
a.空或只有乙個根結點b.任一非葉結點無左子樹
c.高度等於其結點數d.任一非葉結點無右子樹
17.線索二叉樹是一種（ ）結構。
a. 邏輯b邏輯和儲存 c物理 d線性
18.n個結點的線索二叉樹上含有的線索數為（ ）。
a.2nb.n-1c.n+1 d.n
19.由3個結點可以構造出（ ）種不同的二叉樹。
a.2b.3c.4d.5
20.若度為m的哈夫曼樹中，其葉結點個數為n，則非葉結點的個數為（ ）。
a.n-1b.「n/m」-1 c. 「（n-1）/（m-1）」 d. 「n/（m-1）」-1
21.對n（n>=2）個權值均不同的字元構成的哈夫曼樹，關於該樹的敘述中，錯誤的是
（ ）。
a. 該樹一定是一棵完全二叉樹
b. 樹中一定沒有度為1的結點
c. 樹中兩個權值最小的結點一定是兄弟結點
d. 樹中任一非葉結點的權值一定不小於下一層結點的權值
11.算術表示式a+b*(c+d/c)轉換為字尾表示式是（ ）。
a．ab+cdeb．abcde/+*+
c．abcded. abcde*/++
12.具有10個葉結點的二叉樹中有（ ）個度為2的結點。
a．8b.9c.10d.11
13.乙個具有1025個結點的二叉樹的高h為（ ）。
a.11b.10 c.11~1025 d.10~1024
14.前序遍歷與中序遍歷結果相同的二叉樹為（ ）；前序遍歷和後序遍歷結果相同
的二叉樹為（ ）的二叉樹。
a.空二叉樹
b.只有根結點
c.根結點無左孩子
d.根結點無右孩子
15.一棵非空二叉樹的先序遍歷序列與後序遍歷序列正好相反，則該二叉樹一定滿足
（ ）。
a.所有非葉結點均無左孩子 b.所有非葉結點均無右孩子
c.只有乙個葉子結點d.a和b同時成立
16.某二叉樹的中序序列和後序序列正好相反，則該二叉樹一定是（ ）的二叉樹。
a.空或只有乙個根結點b.任一非葉結點無左子樹
c.高度等於其結點數d.任一非葉結點無右子樹
17.線索二叉樹是一種（ ）結構。
a. 邏輯b邏輯和儲存 c物理 d線性
18.n個結點的線索二叉樹上含有的線索數為（ ）。
a.2nb.n-1c.n+1 d.n
19.由3個結點可以構造出（ ）種不同的二叉樹。
a.2b.3c.4d.5
20.若度為m的哈夫曼樹中，其葉結點個數為n，則非葉結點的個數為（ ）。
a.n-1b.「n/m」-1 c. 「（n-1）/（m-1）」 d. 「n/（m-1）」-1
21.對n（n>=2）個權值均不同的字元構成的哈夫曼樹，關於該樹的敘述中，錯誤的是
（ ）。
e. 該樹一定是一棵完全二叉樹
f. 樹中一定沒有度為1的結點
g. 樹中兩個權值最小的結點一定是兄弟結點
h. 樹中任一非葉結點的權值一定不小於下一層結點的權值
11.算術表示式a+b*(c+d/c)轉換為字尾表示式是（ ）。
a．ab+cdeb．abcde/+*+
c．abcded. abcde*/++
12.具有10個葉結點的二叉樹中有（ ）個度為2的結點。
a．8b.9c.10d.11
13.乙個具有1025個結點的二叉樹的高h為（ ）。
a.11b.10 c.11~1025 d.10~1024
14.前序遍歷與中序遍歷結果相同的二叉樹為（ ）；前序遍歷和後序遍歷結果相同
的二叉樹為（ ）的二叉樹。
a.空二叉樹
b.只有根結點
c.根結點無左孩子
d.根結點無右孩子
15.一棵非空二叉樹的先序遍歷序列與後序遍歷序列正好相反，則該二叉樹一定滿足
（ ）。
a.所有非葉結點均無左孩子 b.所有非葉結點均無右孩子
c.只有乙個葉子結點d.a和b同時成立
16.某二叉樹的中序序列和後序序列正好相反，則該二叉樹一定是（ ）的二叉樹。
a.空或只有乙個根結點b.任一非葉結點無左子樹
c.高度等於其結點數d.任一非葉結點無右子樹
17.線索二叉樹是一種（ ）結構。
a. 邏輯b邏輯和儲存 c物理 d線性
18.n個結點的線索二叉樹上含有的線索數為（ ）。
a.2nb.n-1c.n+1 d.n
19.由3個結點可以構造出（ ）種不同的二叉樹。
a.2b.3c.4d.5
20.若度為m的哈夫曼樹中，其葉結點個數為n，則非葉結點的個數為（ ）。
a.n-1b.「n/m」-1 c. 「（n-1）/（m-1）」 d. 「n/（m-1）」-1
21.對n（n>=2）個權值均不同的字元構成的哈夫曼樹，關於該樹的敘述中，錯誤的是
（ ）。
i. 該樹一定是一棵完全二叉樹
j. 樹中一定沒有度為1的結點
k. 樹中兩個權值最小的結點一定是兄弟結點
l. 樹中任一非葉結點的權值一定不小於下一層結點的權值
二、填空
1.一顆二叉樹有67個結點，結點的度要麼是0，要麼是2，則這個二叉樹中度為2的結點有（ ）個
2.含a、b、c三個結點的不同形態的二叉樹有（ ）棵
3.一棵含有n個結點的二叉樹，可能達到的最大深度是（ ）最小深度是（ ）
4.一棵哈夫曼樹有19個結點，則其葉子結點的個數是（ ）
5.設二叉樹的中序遍歷序列序列是abcdefg，後序遍歷序列是bdcafge，則二叉樹的前序遍歷序列是（ ）該二叉樹對應的森林應該包含（）棵樹
6.一棵樹含n個結點的滿二叉樹有（）個度為1的結點，有（）個分支（非終端）結點和（）個葉子，該滿二叉樹的深度為（）
7.含4個度為2的結點和5個葉子結點的完全二叉樹，有（）個度為1的結點
8.已知二叉樹前序序列為abcdegcf，中序遍歷序列為dbgeacf，則後序序列一定是（）
資料結構課後習題及解析第六章
第六章習題 1 試分別畫出具有3個結點的樹和3個結點的二叉樹的所有不同形態。2 對題1所得各種形態的二叉樹，分別寫出前序 中序和後序遍歷的序列。3 已知一棵度為k的樹中有n1個度為1的結點，n2個度為2的結點，nk個度為k的結點，則該樹中有多少個葉子結點並證明之。4.假設一棵二叉樹的先序序列為eba...
資料結構習題答案耿國華主編第六章
6.27 問題 假設一棵二叉樹的先序序列為ebadcfhgikj和中序序列為abcdefghijk。請畫出該樹。解答 6.29 問題 假設一棵二叉樹的層序序列為abcdefghij和中序序列為dbgehjacif。請畫出該樹。6.37 問題 試利用棧的基本操作寫出先序遍歷二叉樹的非遞迴演算法。解答提...
資料結構試題和答案第六章
a a 2n b n l c n l d n 11.由3 個結點可以構造出多少種不同的二叉樹？a a 2 b 3 c 4 d 5 12.深度為k的完全二叉樹至少有 個結點，至多有 個結點。13.具有n個結點的二叉樹，採用二叉鍊錶儲存，共有 個空鏈域。14.n個結點的線索二叉樹上含有的線索數為 15....