（1）把一棵樹轉(zhuǎn)換為二叉樹后,，這棵二叉樹的形態(tài)是（ ）,。
A．唯一的 Ｂ．有多種
C．有多種,，但根結(jié)點都沒有左孩子 Ｄ．有多種,，但根結(jié)點都沒有右孩子
答案：A
解釋：因為二叉樹有左孩子,、右孩子之分,，故一棵樹轉(zhuǎn)換為二叉樹后,，這棵二叉樹的形態(tài)是唯一的。
（2）由3個結(jié)點可以構(gòu)造出多少種不同的二叉樹,？（ ）
A．2 B．3 C．4 D．5
答案：D
解釋：五種情況如下：
（3）一棵完全二叉樹上有1001個結(jié)點,，其中葉子結(jié)點的個數(shù)是（ ）。
A．250 B． 500 C．254 D．501
答案：D
解釋：設(shè)度為0結(jié)點（葉子結(jié)點）個數(shù)為A,，度為1的結(jié)點個數(shù)為B,，度為2的結(jié)點個數(shù)為C，有A=C+1,，A+B+C=1001,，可得2C+B=1000，由完全二叉樹的性質(zhì)可得B=0或1,，又因為C為整數(shù),，所以B=0，C=500,，A=501,，即有501個葉子結(jié)點。
（4）一個具有1025個結(jié)點的二叉樹的高h(yuǎn)為（ ）,。
A．11 B．10 C．11至1025之間 D．10至1024之間
答案：C
解釋：若每層僅有一個結(jié)點,，則樹高h(yuǎn)為1025；且其最小樹高為 ëlog21025û + 1=11,，即h在11至1025之間,。
（5）深度為h的滿m叉樹的第k層有（ ）個結(jié)點。(1=<k=<h)
A．mk-1 B．mk-1 C．mh-1 D．mh-1
答案：A
解釋：深度為h的滿m叉樹共有mh-1個結(jié)點,，第k層有mk-1個結(jié)點,。
（6）利用二叉鏈表存儲樹，則根結(jié)點的右指針是（ ）。
A．指向最左孩子 B．指向最右孩子 C．空 D．非空
答案：C
解釋：利用二叉鏈表存儲樹時,，右指針指向兄弟結(jié)點,，因為根節(jié)點沒有兄弟結(jié)點，故根節(jié)點的右指針指向空,。
（7）對二叉樹的結(jié)點從1開始進行連續(xù)編號,，要求每個結(jié)點的編號大于其左、右孩子的編號,，同一結(jié)點的左右孩子中,，其左孩子的編號小于其右孩子的編號，可采用（ ）遍歷實現(xiàn)編號,。
A．先序 B. 中序 C. 后序 D. 從根開始按層次遍歷
答案：C
解釋：根據(jù)題意可知按照先左孩子,、再右孩子、最后雙親結(jié)點的順序遍歷二叉樹,，即后序遍歷二叉樹,。
（8）若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左,、右子樹的位置,，利用（ ）遍歷方法最合適。
A．前序 B．中序 C．后序 D．按層次
答案：C
解釋：后續(xù)遍歷和層次遍歷均可實現(xiàn)左右子樹的交換,，不過層次遍歷的實現(xiàn)消耗比后續(xù)大,，后序遍歷方法最合適。
（9）在下列存儲形式中,，（ ）不是樹的存儲形式,？
A．雙親表示法 B．孩子鏈表表示法 C．孩子兄弟表示法 D．順序存儲表示法
答案：D
解釋：樹的存儲結(jié)構(gòu)有三種：雙親表示法、孩子表示法,、孩子兄弟表示法,，其中孩子兄弟表示法是常用的表示法，任意一棵樹都能通過孩子兄弟表示法轉(zhuǎn)換為二叉樹進行存儲,。
（10）一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反,，則該二叉樹一定滿足（ ）。
A．所有的結(jié)點均無左孩子 B．所有的結(jié)點均無右孩子
C．只有一個葉子結(jié)點 D．是任意一棵二叉樹
答案：C
解釋：因為先序遍歷結(jié)果是“中左右”,，后序遍歷結(jié)果是“左右中”,，當(dāng)沒有左子樹時，就是“中右”和“右中”,；當(dāng)沒有右子樹時,，就是“中左”和“左中”。則所有的結(jié)點均無左孩子或所有的結(jié)點均無右孩子均可,，所以A,、B不能選,，又所有的結(jié)點均無左孩子與所有的結(jié)點均無右孩子時，均只有一個葉子結(jié)點,，故選C,。
（11）設(shè)哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有（ ）個葉子結(jié)點,。
A．99 B．100
C．101 D．102
答案：B
解釋：在哈夫曼樹中沒有度為1的結(jié)點，只有度為0（葉子結(jié)點）和度為2的結(jié)點,。設(shè)葉子結(jié)點的個數(shù)為n0,，度為2的結(jié)點的個數(shù)為n2，由二叉樹的性質(zhì)n0=n2+1,，則總結(jié)點數(shù)n= n0+n2=2*n0-1,，得到n0=100。
（12）若X是二叉中序線索樹中一個有左孩子的結(jié)點,，且X不為根,，則X的前驅(qū)為（ ）。
A．X的雙親 B．X的右子樹中最左的結(jié)點
C．X的左子樹中最右結(jié)點 D．X的左子樹中最右葉結(jié)點
答案：C
（13）引入二叉線索樹的目的是（ ）,。
A．加快查找結(jié)點的前驅(qū)或后繼的速度 B．為了能在二叉樹中方便的進行插入與刪除
C．為了能方便的找到雙親 D．使二叉樹的遍歷結(jié)果唯一
答案：A
（14）設(shè)F是一個森林,，B是由F變換得的二叉樹。若F中有n個非終端結(jié)點,，則B中右指針域為空的結(jié)點有（ ）個,。
A．n−1 B．n C．n + 1 D．n + 2
答案：C
（15）n（n≥2）個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中,，錯誤的是（ ）,。
A．該樹一定是一棵完全二叉樹
B．樹中一定沒有度為1的結(jié)點
C．樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點
D．樹中任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值
答案：A
解釋：哈夫曼樹的構(gòu)造過程是每次都選取權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，所以樹中一定沒有度為1的結(jié)點,、兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點,、任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值。