1、第6章樹和二叉樹1選擇題（1）把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（）。A唯一的Ｂ有多種C有多種，但根結(jié)點都沒有左孩子Ｄ有多種，但根結(jié)點都沒有右孩子（2）由3個結(jié)點可以構(gòu)造出多少種不同的二叉樹？（）A2B3C4D5（3）一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）。A250B500C254D501（4）一個具有1025個結(jié)點的二叉樹的高h(yuǎn)為（）。A11B10C11至1025之間D10至1024之間（5）深度為h的滿m

2、叉樹的第k層有（）個結(jié)點。(1=k=h)Amk1Bmk1Cmh1Dmh1（6）利用二叉鏈表存儲樹，則根結(jié)點的右指針是（）。A指向最左孩子B指向最右孩子C空D非空（7）對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用（）遍歷實現(xiàn)編號。A先序B.中序C.后序D.從根開始按層次遍歷（8）若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置

3、，利用（）遍歷方法最合適。A前序B中序C后序D按層次（9）在下列存儲形式中，（）不是樹的存儲形式？A雙親表示法B孩子鏈表表示法C孩子兄弟表示法D順序存儲表示法（10）一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（）。A所有的結(jié)點均無左孩子B所有的結(jié)點均無右孩子C只有一個葉子結(jié)點D是任意一棵二叉樹（11）某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A空或只有一個結(jié)點B任一結(jié)點無左子樹C高

4、度等于其結(jié)點數(shù)D任一結(jié)點無右子樹（12）若X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，則X的前驅(qū)為（）。AX的雙親BX的右子樹中最左的結(jié)點CX的左子樹中最右結(jié)點DX的左子樹中最右葉結(jié)點（13）引入二叉線索樹的目的是（）。A加快查找結(jié)點的前驅(qū)或后繼的速度B為了能在二叉樹中方便的進行插入與刪除C為了能方便的找到雙親D使二叉樹的遍歷結(jié)果唯一（100）（40）（60）192132（28）（17）（11）7106（5）23方案比較：方案1

5、的WPL＝2(0.190.320.21)4(0.070.060.10)5(0.020.03)=1.440.920.25=2.61方案2的WPL＝3(0.190.320.210.070.060.100.020.03)=3結(jié)論：哈夫曼編碼優(yōu)于等長二進制編碼（4）已知下列字符A、B、C、D、E、F、G的權(quán)值分別為3、12、7、4、2、8，11，試填寫出其對應(yīng)哈夫曼樹HT的存儲結(jié)構(gòu)的初態(tài)和終態(tài)。初態(tài):weightparentlchildrchi

6、ld13000212000370004400052000680007110008000900010000110001200013000字母編號對應(yīng)編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10字母編號對應(yīng)編碼出現(xiàn)頻率111000.072000.193111100.02411100.065100.326111110.037010.21811010