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