數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)習(xí)題含答案

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

2、叉樹(shù)的第k層有（）個(gè)結(jié)點(diǎn)。(1=k=h)Amk1Bmk1Cmh1Dmh1（6）利用二叉鏈表存儲(chǔ)樹(shù)，則根結(jié)點(diǎn)的右指針是（）。A指向最左孩子B指向最右孩子C空D非空（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)始按層次遍歷（8）若二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左、右子樹(shù)的位置

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

4、度等于其結(jié)點(diǎn)數(shù)D任一結(jié)點(diǎn)無(wú)右子樹(shù)（12）若X是二叉中序線索樹(shù)中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則X的前驅(qū)為（）。AX的雙親BX的右子樹(shù)中最左的結(jié)點(diǎn)CX的左子樹(shù)中最右結(jié)點(diǎn)DX的左子樹(shù)中最右葉結(jié)點(diǎn)（13）引入二叉線索樹(shù)的目的是（）。A加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B為了能在二叉樹(shù)中方便的進(jìn)行插入與刪除C為了能方便的找到雙親D使二叉樹(shù)的遍歷結(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)于等長(zhǎng)二進(jìn)制編碼（4）已知下列字符A、B、C、D、E、F、G的權(quán)值分別為3、12、7、4、2、8，11，試填寫(xiě)出其對(duì)應(yīng)哈夫曼樹(shù)HT的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)。初態(tài):weightparentlchildrchi

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