習(xí)題答案(word版)

《習(xí)題答案(word版)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、1．已知一算術(shù)表達式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為（）。A．-A+B*C/DEB．-A+B*CD/EC．-+*ABC/DED．-+A*BC/DE參考答案：D3．一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）。A．250B．500C．254D．505E．以上答案都不對參考答案：E8．在一棵三元樹中度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為（）個。A．4B．5C．6D．7參考答案：C10．具有10個葉結(jié)點的二叉樹中有（）個度為2的結(jié)點。A．8B．9C．10D．11參考答案：B53．由3個結(jié)

2、點可以構(gòu)造出（）種不同的二叉樹。A．2B．3C．4D．5參考答案：D47．引入二叉線索樹的目的是（）。A．加快查找結(jié)點的前驅(qū)或后繼的速度B．為了能在二叉樹中方便的進行插入與刪除C．為了能方便的找到雙親D．使二叉樹的遍歷結(jié)果唯一19．將如下由三棵樹組成的森林轉(zhuǎn)換為二叉樹。NPGHJMOLIKEDFBAC參考答案：HGDACJIBFEMPONKOL反過來，將一個二叉樹轉(zhuǎn)化成森林或樹？（注意：轉(zhuǎn)化成森林的結(jié)果和轉(zhuǎn)化成樹的結(jié)果不一樣）21．設(shè)某二叉樹的前序遍歷序列為ABCDEFGGI，中序遍歷序列為BCAEDGHFI，試畫出該二叉樹。參考答案：AIDBECHFG27．設(shè)二叉樹T的存儲結(jié)構(gòu)如

3、下：12345678910Lchild00237580101DataJHFDBACEGIRchild0009400000其中Lchild、Rchild分別為結(jié)點的左、右孩子指針域，Data為結(jié)點的數(shù)據(jù)域，若根指針T的值為6，試：(1)畫出二叉樹的邏輯結(jié)構(gòu)；(2)寫出按前序、中序、后序遍歷該二叉樹所得到的結(jié)點序列；(3)畫出二叉樹的后序線索樹。參考答案：前序序列：ABCEDFHGIJ中序序列：ECBHFDJIGA后序序列：ECHFJIGDBA31．假定用于通訊的電文僅有8個字母C1，C2，…，C8組成，各個字母在電文中出現(xiàn)的頻率分別為5，25，3，6，10，11，36，4，試為這8個

4、字母設(shè)計哈夫曼編碼樹。參考答案：各字母編碼如下：c1:0110c2:10c3:0010c4: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；(3)哈夫曼樹見下圖，其帶權(quán)路徑長度wpl=51。34．一

5、棵深度為Ｈ的滿ｋ叉樹有如下性質(zhì)：第Ｈ層上的結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有ｋ棵非空子樹。若按層次順序從１開始對全部結(jié)點編號，問：(1)第ｉ層上有多少個結(jié)點？(2)編號為ｐ的結(jié)點的第ｉ個孩子結(jié)點（若存在）的編號是多少？(3)編號為ｐ的結(jié)點的雙親結(jié)點（若存在）的編號是多少？參考答案：(1)個(2)（１＋（ｐ－１）＊ｋ）＋ｉ(3)（ｐ≠１）】2．給出算法將二叉樹表示的表達式二叉樹按中綴表達式輸出，并加上相應(yīng)的括號。參考答案：本題是將符號算術(shù)表達式用二叉樹表示的逆問題，即將二叉樹表示的表達式還原成原表達式。二叉樹的中序遍歷序列與原算術(shù)表達式基本相同，差別僅在于二叉樹表示中消除了括號

6、。將中序序列加上括號就恢復(fù)原貌。當根結(jié)點運算符優(yōu)先級高于左子樹（或右子樹）根結(jié)點運算符時，就需要加括號。intPrecede(charoptr1,charoptr2)//比較運算符級別高低，optr1級別高于optr2時返回1，相等時返回0，低于時返回-1{switch(optr1){case‘+’:case‘-’:if(optr2==‘+’

7、

8、optr2==‘-’)return(0);elsereturn(-1);case‘*’:case‘/’:if(optr1==‘*’

9、

10、optr2==‘/’)return(0);elsereturn(1);}}voidInorderExp(B

11、iTreebt)//輸出二叉樹表示的算術(shù)表達式，設(shè)二叉樹的數(shù)據(jù)域是運算符或變量名{intbracket;if(bt){if(bt->lchild!=null){bracket=Precede(bt->data,bt->lchild->data)//比較雙親與左子女運算符優(yōu)先級if(bracket==1)printf(‘(’);InorderExp(bt->lchild);//輸出左子女表示的算術(shù)表達式if(bracket==1)printf(‘)’);//加上右括號}