習(xí)題答案分析

1、BACEDFNPGHJMOLIK1已知一算術(shù)表達(dá)式的中綴形式為ABCDE，后綴形式為ABCDE，其前綴形式為（）。AABCDEBABCDECABCDEDABCDE參考答案：D3一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）。A250B500C254D505E以上答案都不對參考答案：E8在一棵三元樹中度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為（）個。A4B5C6D7參考答案：C10具有

2、10個葉結(jié)點的二叉樹中有（）個度為2的結(jié)點。A8B9C10D11參考答案：B53由3個結(jié)點可以構(gòu)造出（）種不同的二叉樹。A2B3C4D5參考答案：D47引入二叉線索樹的目的是（）。A加快查找結(jié)點的前驅(qū)或后繼的速度B為了能在二叉樹中方便的進(jìn)行插入與刪除C為了能方便的找到雙親D使二叉樹的遍歷結(jié)果唯一19將如下由三棵樹組成的森林轉(zhuǎn)換為二叉樹。參考答案：HGDACJIBFEMPONKOL各字母編碼如下：c1:0110c2:10c3:0010c4

3、:0111c5:000c6:010c7:11c8:0011注意雖然哈夫曼樹的帶權(quán)路徑長度是唯一的，但形態(tài)不唯一。33設(shè)T是一棵二叉樹，除葉子結(jié)點外，其它結(jié)點的度皆為2，若T中有6個葉結(jié)點，試問：(1)樹T的最大深度和最小可能深度分別是多少？(2)樹T中共有多少非葉結(jié)點？(3)若葉結(jié)點的權(quán)值分別為1、2、3、4、5、6，請構(gòu)造一棵哈曼夫樹，并計算該哈曼夫樹的帶權(quán)路徑長度wpl。參考答案：(1)最大深度6，最小深度4；(2)非葉結(jié)點數(shù)5；(

4、3)哈夫曼樹見下圖，其帶權(quán)路徑長度wpl=51。34一棵深度為Ｈ的滿ｋ叉樹有如下性質(zhì)：第Ｈ層上的結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有ｋ棵非空子樹。若按層次順序從１開始對全部結(jié)點編號，問：(1)第ｉ層上有多少個結(jié)點？(2)編號為ｐ的結(jié)點的第ｉ個孩子結(jié)點（若存在）的編號是多少？(3)編號為ｐ的結(jié)點的雙親結(jié)點（若存在）的編號是多少？參考答案：(1)個1?ik(2)（１＋（ｐ－１）＊ｋ）＋ｉ(3)（ｐ≠１）】????????kkp22給出算