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

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

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

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

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

4、字母設(shè)計(jì)哈夫曼編碼樹。參考答案：各字母編碼如下：c1:0110c2:10c3:0010c4:0111c5:000c6:010c7:11c8:0011注意雖然哈夫曼樹的帶權(quán)路徑長(zhǎng)度是唯一的，但形態(tài)不唯一。33．設(shè)T是一棵二叉樹，除葉子結(jié)點(diǎn)外，其它結(jié)點(diǎn)的度皆為2，若T中有6個(gè)葉結(jié)點(diǎn)，試問：(1)樹T的最大深度和最小可能深度分別是多少？(2)樹T中共有多少非葉結(jié)點(diǎn)？(3)若葉結(jié)點(diǎn)的權(quán)值分別為1、2、3、4、5、6，請(qǐng)構(gòu)造一棵哈曼夫樹，并計(jì)算該哈曼夫樹的帶權(quán)路徑長(zhǎng)度wpl。參考答案：(1)最大深度6，最小深度4；(2)非葉結(jié)點(diǎn)數(shù)5；(3)哈夫曼樹見下圖，其帶權(quán)路徑長(zhǎng)度wpl=51。34．一

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

6、。將中序序列加上括號(hào)就恢復(fù)原貌。當(dāng)根結(jié)點(diǎn)運(yùn)算符優(yōu)先級(jí)高于左子樹（或右子樹）根結(jié)點(diǎn)運(yùn)算符時(shí)，就需要加括號(hào)。intPrecede(charoptr1,charoptr2)//比較運(yùn)算符級(jí)別高低，optr1級(jí)別高于optr2時(shí)返回1，相等時(shí)返回0，低于時(shí)返回-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ù)表達(dá)式，設(shè)二叉樹的數(shù)據(jù)域是運(yùn)算符或變量名{intbracket;if(bt){if(bt->lchild!=null){bracket=Precede(bt->data,bt->lchild->data)//比較雙親與左子女運(yùn)算符優(yōu)先級(jí)if(bracket==1)printf(‘(’);InorderExp(bt->lchild);//輸出左子女表示的算術(shù)表達(dá)式if(bracket==1)printf(‘)’);//加上右括號(hào)}