（1）把一棵樹轉換為二叉樹后，這棵二叉樹的形態是（   ）。              

A．唯一的                          Ｂ．有多種

C．有多種，但根結點都沒有左孩子    Ｄ．有多種，但根結點都沒有右孩子

答案：A

解釋：因為二叉樹有左孩子、右孩子之分，故一棵樹轉換為二叉樹后，這棵二叉樹的形態是唯一的。

（2）由3個結點可以構造出多少種不同的二叉樹？（    ）

A．2          B．3             C．4          D．5   

答案：D

解釋：五種情況如下：

（3）一棵完全二叉樹上有1001個結點，其中葉子結點的個數是（  ）。

A．250         B． 500          C．254        D．501   

答案：D

解釋：設度為0結點（葉子結點）個數為A，度為1的結點個數為B，度為2的結點個數為C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉樹的性質可得B=0或1，又因為C為整數，所以B=0，C=500，A=501，即有501個葉子結點。

（4）一個具有1025個結點的二叉樹的高h為（  ）。

A．11          B．10             C．11至1025之間       D．10至1024之間

答案：C

解釋：若每層僅有一個結點，則樹高h為1025；且其最小樹高為 ëlog21025û + 1=11，即h在11至1025之間。

（5）深度為h的滿m叉樹的第k層有（  ）個結點。(1=<k=<h)

A．mk-1          B．mk-1            C．mh-1        D．mh-1

答案：A

解釋：深度為h的滿m叉樹共有mh-1個結點，第k層有mk-1個結點。

（6）利用二叉鏈表存儲樹，則根結點的右指針是（  ）。

A．指向最左孩子        B．指向最右孩子         C．空        D．非空

答案：C

解釋：利用二叉鏈表存儲樹時，右指針指向兄弟結點，因為根節點沒有兄弟結點，故根節點的右指針指向空。

（7）對二叉樹的結點從1開始進行連續編號，要求每個結點的編號大于其左、右孩子的編號，同一結點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用（  ）遍歷實現編號。

A．先序         B. 中序           C. 后序       D. 從根開始按層次遍歷

答案：C

解釋：根據題意可知按照先左孩子、再右孩子、最后雙親結點的順序遍歷二叉樹，即后序遍歷二叉樹。

（8）若二叉樹采用二叉鏈表存儲結構，要交換其所有分支結點左、右子樹的位置，利用（  ）遍歷方法最合適。

A．前序         B．中序            C．后序      D．按層次

答案：C

解釋：后續遍歷和層次遍歷均可實現左右子樹的交換，不過層次遍歷的實現消耗比后續大，后序遍歷方法最合適。

（9）在下列存儲形式中，（  ）不是樹的存儲形式？

A．雙親表示法   B．孩子鏈表表示法   C．孩子兄弟表示法   D．順序存儲表示法

答案：D

解釋：樹的存儲結構有三種：雙親表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵樹都能通過孩子兄弟表示法轉換為二叉樹進行存儲。

（10）一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（  ）。

A．所有的結點均無左孩子        B．所有的結點均無右孩子

C．只有一個葉子結點            D．是任意一棵二叉樹

答案：C

解釋：因為先序遍歷結果是“中左右”，后序遍歷結果是“左右中”，當沒有左子樹時，就是“中右”和“右中”；當沒有右子樹時，就是“中左”和“左中”。則所有的結點均無左孩子或所有的結點均無右孩子均可，所以A、B不能選，又所有的結點均無左孩子與所有的結點均無右孩子時，均只有一個葉子結點，故選C。

（11）設哈夫曼樹中有199個結點，則該哈夫曼樹中有（    ）個葉子結點。

A．99 B．100

C．101 D．102

答案：B

解釋：在哈夫曼樹中沒有度為1的結點，只有度為0（葉子結點）和度為2的結點。設葉子結點的個數為n0，度為2的結點的個數為n2，由二叉樹的性質n0=n2+1，則總結點數n= n0+n2=2*n0-1，得到n0=100。

（12）若X是二叉中序線索樹中一個有左孩子的結點，且X不為根，則X的前驅為（  ）。

A．X的雙親                      B．X的右子樹中最左的結點 

C．X的左子樹中最右結點          D．X的左子樹中最右葉結點

答案：C

（13）引入二叉線索樹的目的是（  ）。

A．加快查找結點的前驅或后繼的速度    B．為了能在二叉樹中方便的進行插入與刪除

C．為了能方便的找到雙親              D．使二叉樹的遍歷結果唯一

答案：A

（14）設F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結點，則B中右指針域為空的結點有（   ）個。

A．n−1 B．n C．n + 1 D．n + 2

答案：C

（15）n（n≥2）個權值均不相同的字符構成哈夫曼樹，關于該樹的敘述中，錯誤的是（ ）。

A．該樹一定是一棵完全二叉樹

B．樹中一定沒有度為1的結點

C．樹中兩個權值最小的結點一定是兄弟結點

D．樹中任一非葉結點的權值一定不小于下一層任一結點的權值

答案：A

解釋：哈夫曼樹的構造過程是每次都選取權值最小的樹作為左右子樹構造一棵新的二叉樹，所以樹中一定沒有度為1的結點、兩個權值最小的結點一定是兄弟結點、任一非葉結點的權值一定不小于下一層任一結點的權值。