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