數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版第二版嚴(yán)蔚敏樹(shù)和二叉樹(shù)答案

1、（7）對(duì)二叉樹(shù)的結(jié)點(diǎn)從 號(hào)，同一結(jié)點(diǎn)的左右孩子中，A.先序 B.中序 C.后序 D.從根開(kāi)始按層次遍歷第5章樹(shù)和二叉樹(shù)i 選擇題（i）把一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài)是（A.唯一的E.有多種C.有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子D.有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子答案：A解釋：因?yàn)槎鏄?shù)有左孩子、右孩子之分，故一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài) 是唯一的。（2）由3個(gè)結(jié)點(diǎn)可以構(gòu)造岀多少種不同的二叉樹(shù)？（）A. 2B. 3C.4D . 5答案：D解釋：五種情況如下：A AA AABBB BBCCCC C（3） 棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（)A. 250B.500C.2

2、54D. 501答案：D解釋：設(shè)度為0結(jié)點(diǎn)（葉子結(jié)點(diǎn)）個(gè)數(shù)為 A，度為1的結(jié)點(diǎn)個(gè)數(shù)為 B,度為2的結(jié)點(diǎn)個(gè)數(shù)為C,有 A=C+1，A+B+C=1001,可得2C+B=1000,由完全二叉樹(shù)的性質(zhì)可得B=0或1,又因?yàn)?C為整數(shù)，所以 B=0, C=500, A=501,即有501個(gè)葉子結(jié)點(diǎn)。（4 ）一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高 h為（）oA. 11 B . 10C. 11 至 1025 之間 D . 10 至 1024 之間答案：C解釋：若每層僅有一個(gè)結(jié)點(diǎn)，則樹(shù)高h(yuǎn)為1025 ;且其最小樹(shù)高為log21025 +仁11，即h在11至1025之間。（5） 深度為h的滿m叉樹(shù)的第k層有（）個(gè)結(jié)

3、點(diǎn)。（仁<k=<h）A. m-1B . m-1 C.卅-1D . mh-1答案：A解釋：深度為h的滿m叉樹(shù)共有m-1個(gè)結(jié)點(diǎn)，第k層有m"個(gè)結(jié)點(diǎn)。（6） 利用二叉鏈表存儲(chǔ)樹(shù)，則根結(jié)點(diǎn)的右指針是（）A.指向最左孩子B.指向最右孩子C .空 D .非空答案：C解釋：利用二叉鏈表存儲(chǔ)樹(shù)時(shí)，右指針指向兄弟結(jié)點(diǎn)，因?yàn)楦?jié)點(diǎn)沒(méi)有兄弟結(jié)點(diǎn)，故根節(jié) 點(diǎn)的右指針指向空。1開(kāi)始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編 其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用（）遍歷實(shí)現(xiàn)編號(hào)答案：C解釋：根據(jù)題意可知按照先左孩子、再右孩子、最后雙親結(jié)點(diǎn)的順序遍歷二叉樹(shù)，即后序 遍歷二叉樹(shù)。（8）若二

4、叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)， 要交換其所有分支結(jié)點(diǎn)左、 右子樹(shù)的位置， 利用（ ） 遍歷方法最合適。A.前序 B 中序C后序 D按層次答案： C解釋：后續(xù)遍歷和層次遍歷均可實(shí)現(xiàn)左右子樹(shù)的交換， 不過(guò)層次遍歷的實(shí)現(xiàn)消耗比后續(xù)大， 后序遍歷方法最合適。（9）在下列存儲(chǔ)形式中， （ ）不是樹(shù)的存儲(chǔ)形式？A.雙親表示法B 孩子鏈表表示法C 孩子兄弟表示法D 順序存儲(chǔ)表示法答案： D 解釋：樹(shù)的存儲(chǔ)結(jié)構(gòu)有三種：雙親表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟 表示法是常用的表示法，任意一棵樹(shù)都能通過(guò)孩子兄弟表示法轉(zhuǎn)換為二叉樹(shù)進(jìn)行存儲(chǔ)。）。A 所有的結(jié)點(diǎn)均無(wú)左孩子BC只有一個(gè)葉子結(jié)點(diǎn)D答案： C 解釋：

5、因?yàn)橄刃虮闅v結(jié)果是“中左右”（10）一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿足所有的結(jié)點(diǎn)均無(wú)右孩子是任意一棵二叉樹(shù)，后序遍歷結(jié)果是“左右中” ，當(dāng)沒(méi)有左子樹(shù)時(shí)，就是“中右”和“右中” ；當(dāng)沒(méi)有右子樹(shù)時(shí)，就是“中左”和“左中” 。則所有的結(jié)點(diǎn)均無(wú)左孩子或 所有的結(jié)點(diǎn)均無(wú)右孩子均可，所以A、B不能選，又所有的結(jié)點(diǎn)均無(wú)左孩子與所有的結(jié)點(diǎn)均無(wú)右孩子時(shí)，均只有一個(gè)葉子結(jié)點(diǎn)，故選C。11）設(shè)哈夫曼樹(shù)中有 199 個(gè)結(jié)點(diǎn)，則該哈夫曼樹(shù)中有（）個(gè)葉子結(jié)點(diǎn)A. 99B. 100C. 101D. 102答案： B解釋：在哈夫曼樹(shù)中沒(méi)有度為 1 的結(jié)點(diǎn)，只有度為0（葉子結(jié)點(diǎn)）和度為2

6、的結(jié)點(diǎn)。設(shè)葉子結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，由二叉樹(shù)的性質(zhì)n0=n2+1，則總結(jié)點(diǎn)數(shù) n=n0+n2=2*n0-1 ，得到 n0=100。（12 ）若X是二叉中序線索樹(shù)中一個(gè)有左孩子的結(jié)點(diǎn)，且A. X 的雙親BC. X的左子樹(shù)中最右結(jié)點(diǎn) 答案： C （13）引入二叉線索樹(shù)的目的是（）A.加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度C.為了能方便的找到雙親 答案： A （ 14 ）設(shè) F 是 針域?yàn)榭盏慕Y(jié)點(diǎn)有（個(gè)森林， B 是由）個(gè)。X不為根，則X的前驅(qū)為（）。.X的右子樹(shù)中最左的結(jié)點(diǎn).X的左子樹(shù)中最右葉結(jié)點(diǎn)B .為了能在二叉樹(shù)中方便的進(jìn)行插入與刪除 .使二叉樹(shù)的遍歷結(jié)果唯一F變換得的二叉樹(shù)。若

7、F中有n個(gè)非終端結(jié)點(diǎn)，則 B中右指An- 1答案： C（15） n （n2）該樹(shù)一定是一A.B.C.D.B. nC. n + 1D. n + 2個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹(shù)，棵完全二叉樹(shù)樹(shù)中一定沒(méi)有度為 1 的結(jié)點(diǎn) 樹(shù)中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn) 樹(shù)中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值關(guān)于該樹(shù)的敘述中， 錯(cuò)誤的是 （）。答案：A解釋：哈夫曼樹(shù)的構(gòu)造過(guò)程是每次都選取權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，所以樹(shù)中一定沒(méi)有度為 1的結(jié)點(diǎn)、兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)、任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值。2 應(yīng)用題(1 )試找岀滿足下列條件的二叉樹(shù) 先序

8、序列與后序序列相同中序序列與后序序列相同先序序列與中序序列相同中序序列與層次遍歷序列相同答案：先序遍歷二叉樹(shù)的順序是“根一左子樹(shù)一右子樹(shù)”，中序遍歷“左子樹(shù)一根一右子樹(shù)”,后序遍歷順序是：“左子樹(shù)一右子樹(shù)一根"，根據(jù)以上原則有 或?yàn)榭諛?shù)，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹(shù) 或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹(shù)的二叉樹(shù). 或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù). 或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù)(2)設(shè)一棵二叉樹(shù)的先序序列：A B D F C E G H，中序序列：B F D A G E H C 畫(huà)岀這棵二叉樹(shù)。 畫(huà)岀這棵二叉樹(shù)的后序線索樹(shù)。 將這棵二叉樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的樹(shù)(或森林)

9、。答案：A(3)假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中岀現(xiàn)的頻率分別為0.07, 0.19，0.02，0.06，0.32，0.03，0.21，0.10。 試為這8個(gè)字母設(shè)計(jì)赫夫曼編碼。 試設(shè)計(jì)另一種由二進(jìn)制表示的等長(zhǎng)編碼方案。 對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。 答案：方案1;哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹(shù)。w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)則:【(2,3)，6, (7,10)】,19, 21, 32(40)192132(60)(28)(17)/ 、7106(11)(5)/23方案比較:字母對(duì)應(yīng)出現(xiàn)編號(hào)編碼頻率111000.072000.19

10、3111100.02411100.065100.326111110.037010.2181010.10字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10方案 1 的 WPL = 2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 方案 2 的 WPL = 3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結(jié)論：哈夫曼編碼優(yōu)于等長(zhǎng)二進(jìn)制編碼(4)已知下列字符A、B、C、D、

11、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):weightpare ntIchildrchild13000212000370004400052000680007110008000900010000110001200013000終態(tài):weightpare ntlchildrchild138002121200371000449005280068100071111008595199114810151236112013971227132101347011123 算法設(shè)計(jì)題以二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，編寫(xiě)以下算法：(1統(tǒng)計(jì)二叉樹(shù)

12、的葉結(jié)點(diǎn)個(gè)數(shù)。題目分析如果二叉樹(shù)為空，返回0,如果二叉樹(shù)不為空且左右子樹(shù)為空，返回1，如果二叉樹(shù)不為空，且左右子樹(shù)不同時(shí)為空，返回左子樹(shù)中葉子節(jié)點(diǎn)個(gè)數(shù)加上右子樹(shù)中葉子節(jié)點(diǎn) 個(gè)數(shù)。算法描述int LeafNodeCou nt(BiTree T)i f(T=NULL)return 0; II 如果是空樹(shù)，則葉子結(jié)點(diǎn)個(gè)數(shù)為 0else if(T->lchild=NULL&& T->rchild=NULL)return 1; / 判斷結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)(左孩子右孩子都為空)，若是則返回1elsereturn LeafNodeCou nt(T->lchild)+Leaf

13、NodeCou nt( T->rchild);(2)判別兩棵樹(shù)是否相等。算法描述int compareTree(TreeNode* tree1, TreeNode* tree2)用分治的方法做，比較當(dāng)前根，然后比較左子樹(shù)和右子樹(shù)bool tree1IsNull = (tree1=NULL);bool tree2lsNull = (tree2=NULL);if(tree1lsNull != tree2lsNull)return 1;if(tree1IsNull && tree2IsNull)/如果兩個(gè)都是NULL，則相等return 0;/如果根節(jié)點(diǎn)不相等，直接返回不相等，

14、否則的話，看看他們孩子相等不相等if(tree1->c != tree2->c)return 1;return (compareTree(tree1->left,tree2->left)&compareTree(tree1->right,tree2->right) (compareTree(tree1->left,tree2->right)&compareTree(tree1->right,tree2->left);/算法結(jié)束(3) 交換二叉樹(shù)每個(gè)結(jié)點(diǎn)的左孩子和右孩子。題目分析如果某結(jié)點(diǎn)左右子樹(shù)為空，返回，否則交換該結(jié)

15、點(diǎn)左右孩子，然后遞歸交換左右子樹(shù)。算法描述void Cha ngeLR(BiTree &T)BiTree temp;if(T->lchild=NULL&&T->rchild=NULL)return;elsetemp = T->lchild;T->lchild = T->rchild;T->rchild = temp; /交換左右孩子ChangeLR(T->lchild); /遞歸交換左子樹(shù)ChangeLR(T->rchild);/遞歸交換右子樹(shù)(4) 設(shè)計(jì)二叉樹(shù)的雙序遍歷算法(雙序遍歷是指對(duì)于二叉樹(shù)的每一個(gè)結(jié)點(diǎn)來(lái)說(shuō)，先訪問(wèn)

16、這 個(gè)結(jié)點(diǎn)， 再按雙序遍歷它的左子樹(shù)， 然后再一次訪問(wèn)這個(gè)結(jié)點(diǎn)， 接下來(lái)按雙序遍歷它的右子樹(shù)) 題目分析 若樹(shù)為空，返回；若某結(jié)點(diǎn)為葉子結(jié)點(diǎn)，則僅輸出該結(jié)點(diǎn)；否則先輸出該結(jié)點(diǎn)， 遞歸遍歷其左子樹(shù)，再輸出該結(jié)點(diǎn)，遞歸遍歷其右子樹(shù)。 算法描述 void DoubleTraverse(BiTree T)i f(T = NULL)return;else if(T->lchild=NULL&&T->rchild=NULL)cout<<T->data; / 葉子結(jié)點(diǎn)輸出elsecout<<T->data;DoubleTraverse(T-&g

17、t;lchild); /遞歸遍歷左子樹(shù)cout<<T->data;DoubleTraverse(T->rchild); /遞歸遍歷右子樹(shù)(5) 計(jì)算二叉樹(shù)最大的寬度(二叉樹(shù)的最大寬度是指二叉樹(shù)所有層中結(jié)點(diǎn)個(gè)數(shù)的最大值) 題目分析 求二叉樹(shù)高度的算法見(jiàn)上題。求最大寬度可采用層次遍歷的方法，記下各層結(jié) 點(diǎn)數(shù)，每層遍歷完畢，若結(jié)點(diǎn)數(shù)大于原先最大寬度，則修改最大寬度。 算法描述 int Width(BiTree bt)/求二叉樹(shù) bt 的最大寬度if (bt=null) return (0); /空二叉樹(shù)寬度為 0elseBiTree Q;/Q 是隊(duì)列，元素為二叉樹(shù)結(jié)點(diǎn)指針，容

18、量足夠大 front=1;rear=1;last=1;/front 隊(duì)頭指針 ,rear 隊(duì)尾指針 ,last 同層最右結(jié)點(diǎn)在隊(duì)列中的位置 temp=0; maxw=0; /temp 記局部寬度 , maxw 記最大寬度 Qrear=bt; / 根結(jié)點(diǎn)入隊(duì)列 while(front<=last)p=Qfront+; temp+; / 同層元素?cái)?shù)加 1if (p->lchild!=null) Q+rear=p->lchild; /左子女入隊(duì)if (p->rchild!=null) Q+rear=p->rchild; /右子女入隊(duì)if (front>last)

19、/ 一層結(jié)束，last=rear;if(temp>maxw) maxw=temp;/last 指向下層最右元素 , 更新當(dāng)前最大寬度temp=0;/if/whilereturn (maxw);/ 結(jié)束 width(6) 用按層次順序遍歷二叉樹(shù)的方法，統(tǒng)計(jì)樹(shù)中具有度為1 的結(jié)點(diǎn)數(shù)目。題目分析 若某個(gè)結(jié)點(diǎn)左子樹(shù)空右子樹(shù)非空或者右子樹(shù)空左子樹(shù)非空，則該結(jié)點(diǎn)為度為 1 的結(jié)點(diǎn) 算法描述 int Level(BiTree bt) /層次遍歷二叉樹(shù)，并統(tǒng)計(jì)度為 1 的結(jié)點(diǎn)的個(gè)數(shù)int num=0; /num統(tǒng)計(jì)度為 1 的結(jié)點(diǎn)的個(gè)數(shù)if(bt)QueueInit(Q); QueueIn(Q,bt);

20、/Q 是以二叉樹(shù)結(jié)點(diǎn)指針為元素的隊(duì)列 while(!QueueEmpty(Q)p=QueueOut(Q); cout<<p->data; /出隊(duì) , 訪問(wèn)結(jié)點(diǎn)if(p->lchild && !p->rchild |!p->lchild && p->rchild)num+; / 度為 1 的結(jié)點(diǎn)if(p->lchild) QueueIn(Q,p->lchild); /非空左子女入隊(duì)if(p->rchild) QueueIn(Q,p->rchild); /非空右子女入隊(duì) / while(!QueueE

21、mpty(Q)/if(bt) return(num);/ 返回度為 1 的結(jié)點(diǎn)的個(gè)數(shù)(7) 求任意二叉樹(shù)中第一條最長(zhǎng)的路徑長(zhǎng)度，并輸出此路徑上各結(jié)點(diǎn)的值。 題目分析 因?yàn)楹笮虮闅v棧中保留當(dāng)前結(jié)點(diǎn)的祖先的信息，用一變量保存棧的最高棧頂指 針，每當(dāng)退棧時(shí)，棧頂指針高于保存最高棧頂指針的值時(shí)， 則將該棧倒入輔助棧中， 輔助棧始終 保存最長(zhǎng)路徑長(zhǎng)度上的結(jié)點(diǎn)，直至后序遍歷完畢，則輔助棧中內(nèi)容即為所求。 算法描述 void LongestPath(BiTree bt)/ 求二叉樹(shù)中的第一條最長(zhǎng)路徑長(zhǎng)度BiTree p=bt,l,s;/l, s 是棧，元素是二叉樹(shù)結(jié)點(diǎn)指針， l 中保留當(dāng)前最長(zhǎng)路徑中的結(jié)點(diǎn)int i ， top=0,tag,longest=0;while(p | top>0)while(p) s+top=p； tagtop=0; p=p->Lc; /沿左分枝向下if(tagtop=1) / 當(dāng)前結(jié)點(diǎn)的右分枝已遍歷if(!stop->Lc && !stop->Rc) /只有到葉子結(jié)點(diǎn)時(shí)，才查看路徑長(zhǎng)度if(top>longest)for(i=1