（1）把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（ ）。
A．唯一的 Ｂ．有多種
C．有多種，但根結(jié)點(diǎn)都沒有左孩子 Ｄ．有多種，但根結(jié)點(diǎn)都沒有右孩子
答案：A
解釋：因?yàn)槎鏄溆凶蠛⒆印⒂液⒆又郑室豢脴滢D(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是唯一的。
（2）由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（ ）
A．2 B．3 C．4 D．5
答案：D
解釋：五種情況如下：
（3）一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ ）。
A．250 B． 500 C．254 D．501
答案：D
解釋：設(shè)度為0結(jié)點(diǎn)（葉子結(jié)點(diǎn)）個(gè)數(shù)為A，度為1的結(jié)點(diǎn)個(gè)數(shù)為B，度為2的結(jié)點(diǎn)個(gè)數(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個(gè)葉子結(jié)點(diǎn)。
（4）一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（ ）。
A．11 B．10 C．11至1025之間 D．10至1024之間
答案：C
解釋：若每層僅有一個(gè)結(jié)點(diǎn)，則樹高h(yuǎn)為1025；且其最小樹高為 ëlog21025û + 1=11，即h在11至1025之間。
（5）深度為h的滿m叉樹的第k層有（ ）個(gè)結(jié)點(diǎn)。(1=<k=<h)
A．mk-1 B．mk-1 C．mh-1 D．mh-1
答案：A
解釋：深度為h的滿m叉樹共有mh-1個(gè)結(jié)點(diǎn)，第k層有mk-1個(gè)結(jié)點(diǎn)。
（6）利用二叉鏈表存儲樹，則根結(jié)點(diǎn)的右指針是（ ）。
A．指向最左孩子 B．指向最右孩子 C．空 D．非空
答案：C
解釋：利用二叉鏈表存儲樹時(shí)，右指針指向兄弟結(jié)點(diǎn)，因?yàn)楦?jié)點(diǎn)沒有兄弟結(jié)點(diǎn)，故根節(jié)點(diǎn)的右指針指向空。
（7）對二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號，要求每個(gè)結(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．只有一個(gè)葉子結(jié)點(diǎn) D．是任意一棵二叉樹
答案：C
解釋：因?yàn)橄刃虮闅v結(jié)果是“中左右”，后序遍歷結(jié)果是“左右中”，當(dāng)沒有左子樹時(shí)，就是“中右”和“右中”；當(dāng)沒有右子樹時(shí)，就是“中左”和“左中”。則所有的結(jié)點(diǎn)均無左孩子或所有的結(jié)點(diǎn)均無右孩子均可，所以A、B不能選，又所有的結(jié)點(diǎn)均無左孩子與所有的結(jié)點(diǎn)均無右孩子時(shí)，均只有一個(gè)葉子結(jié)點(diǎn)，故選C。
（11）設(shè)哈夫曼樹中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有（ ）個(gè)葉子結(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)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，由二叉樹的性質(zhì)n0=n2+1，則總結(jié)點(diǎn)數(shù)n= n0+n2=2*n0-1，得到n0=100。
（12）若X是二叉中序線索樹中一個(gè)有左孩子的結(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是一個(gè)森林，B是由F變換得的二叉樹。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（ ）個(gè)。
A．n−1 B．n C．n + 1 D．n + 2
答案：C
（15）n（n≥2）個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯(cuò)誤的是（ ）。
A．該樹一定是一棵完全二叉樹
B．樹中一定沒有度為1的結(jié)點(diǎn)
C．樹中兩個(gè)權(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)、兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)、任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值。