1、一、單選題1、把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（）。A.有多種B.有多種，但根結(jié)點都沒有右孩子C.唯一的D.有多種，但根結(jié)點都沒有左孩子正確答案：C2、由3個結(jié)點可以構(gòu)造出多少種不同的二叉樹？（）A.5B.2C.3D.4正確答案：A3、一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）。A.250B.254C.500D.501正確答案：D4、一個具有1025個結(jié)點的二叉樹的高h(yuǎn)為（）oA.11B.11至1025之間C. 10至1024之間D.10正確答案：B5、深度為h的滿m叉樹的第k層有（）個結(jié)點。（l=k=h）mk 1mk-1mh 1正確答案：C6、利用二叉鏈表存儲樹，則

2、根結(jié)點的右指針是（）oA.非空B.指向最右孩子C.指向最左孩子D.空正確答案：D7、對二叉樹的結(jié)點從1開始進(jìn)行連續(xù)編號，要求每個結(jié)點的編號大于其左、右 孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可 采用（）遍歷實現(xiàn)編號。A.從根開始按層次遍歷B冼序C后序D.中序正確答案：c8、若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置， 利用（）遍歷方法最合適。A.中序B.先序C.后序D.按層次正確答案：C9、在下列存儲形式中，（）不是樹的存儲形式？A.孩子鏈表表示法B.順序存儲表示法C.雙親表示法D.孩子兄弟表示法正確答案：B10、一棵非空的二叉樹的先序遍歷

3、序列與后序遍歷序列正好相反，則該二叉樹一 定滿足（）oA.所有的結(jié)點均無右孩子B.只有一個葉子結(jié)點C.是任意一棵二叉樹D.所有的結(jié)點均無左孩子正確答案：B11、設(shè)哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有（）個葉子結(jié)點。A.99B.101C.1O2D.1OO正確答案：D12、若X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，則X的前驅(qū)為（）oA.X的左子樹中最右結(jié)點B.X的右子樹中最左的結(jié)點C.X的左子樹中最右葉結(jié)點D.X的雙親正確答案：A13、引入二叉線索樹的目的是（）。A.為了能在二叉樹中方便的進(jìn)行插入與刪除B.使二叉樹的遍歷結(jié)果唯一C.為了能方便的找到雙親D.加快查找結(jié)點的前驅(qū)或后繼

4、的速度正確答案：D14、設(shè)F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有（）個。A.nB.n+1C.n+2D.n-1正確答案：B15、n (nN2)個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯誤的是()oA.樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點B.該樹一定是一棵完全二叉樹C.樹中一定沒有度為1的結(jié)點D.樹中任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值正確答案：B二、判斷題1、樹中任意兩個結(jié)點一定存在最近共同祖先。正確答案：V2、在完全二叉樹中，若一個結(jié)點沒有左子女，則它一定是葉結(jié)點。正確答案：V3、二叉樹是一般樹的特殊情形。正確答案：X4、二叉樹的后序遍歷序列和先序遍歷序列保存的信息相同，只不過順序相反。正確答案：