第6章 樹和二叉樹(相關(guān)試題)數(shù)據(jù)結(jié)構(gòu)

《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版）

第6章樹和二叉樹

計(jì)算機(jī)與信息工程學(xué)院于江德1樹形結(jié)構(gòu)樹樹的定義基本術(shù)語(yǔ)ADT定義樹的遍歷：先序遍歷后序遍歷層序遍歷二叉樹雙親表示法孩子表示法相互轉(zhuǎn)換存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)孩子兄弟表示法二叉樹的定義二叉樹的性質(zhì)特殊二叉樹二叉樹的性質(zhì)二叉樹的四種遍歷方法滿二叉樹完全二叉樹二叉鏈表順序存儲(chǔ)線索鏈表三叉鏈表遍歷算法實(shí)現(xiàn)基于遍歷的其他算法2二叉樹的遍歷1.

一棵二叉樹的先序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，則后序遍歷結(jié)果為（

）A.CBEFDA B.FEDCBAC.CBEDFA D.不確定3二叉樹的遍歷2.

某二叉樹的后序遍歷序列為dabec，中序遍歷序列為debac，則先序遍歷序列為（）。A．a(chǎn)cbedB．decab

C．deabcD．cedba

4二叉樹的遍歷3.

對(duì)二叉樹的結(jié)點(diǎn)從1開始進(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.從根開始按層次遍歷5二叉樹的遍歷4.

二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷:HFIEJKG。該二叉樹根的右子樹的根是()A．EB．FC．G

D．H6二叉樹的遍歷5.

某二叉樹的先序和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A.空或只有一個(gè)結(jié)點(diǎn)B．高度等于其結(jié)點(diǎn)數(shù)C．任一結(jié)點(diǎn)無(wú)左孩子D．任一結(jié)點(diǎn)無(wú)右孩子7二叉樹的遍歷5’.

某二叉樹的先序和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A．所有的結(jié)點(diǎn)均無(wú)左孩子B．所有的結(jié)點(diǎn)均無(wú)右孩子C．只有一個(gè)葉子結(jié)點(diǎn)D．是任意一棵二叉樹8二叉樹的遍歷6.

設(shè)n，m為一棵二叉樹的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是（）A.n在m的右方 B.n是m的祖先C.n在m的左方 D.n是m的子孫97.具有10個(gè)葉子結(jié)點(diǎn)的二叉樹中有（ ）個(gè)度為2的結(jié)點(diǎn)。A.8 B.9 C.10 D.11108.樹中所有結(jié)點(diǎn)的度的和等于所有結(jié)點(diǎn)數(shù)加（

）。A．0 B．1C．－1 D．2119.在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是（ ）A．t->left=NULLB.t->ltag=1C.t->ltag=1且t->left=NULLD.以上都不對(duì)1210.

由權(quán)值為9、2、5、7的四個(gè)葉子構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長(zhǎng)度為（）A．23B.37C.44D.461311．將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個(gè)結(jié)點(diǎn)的完全三叉樹的高度（）A．4B．5C．6D．71412．一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（）.A．11B．10C．11至1025之間D．10至1024之間1513.設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為N1，N2和N3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是（）。A．N1B．N1+N2C．N3D．N2+N31614.設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1則T中的葉子數(shù)為（）A．5B．6C．7D．81715.設(shè)森林F對(duì)應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p,p的右子樹結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是（）A．m-nB．m-n-1C．n+1D．條件不足，無(wú)法確定1816.

若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（）A．9B．11C．15D．不確定1917.一棵完全二叉樹上有1000個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）A．250B．500C．254D．505E．以上答案都不對(duì)20問(wèn):設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則它有

個(gè)葉子結(jié)點(diǎn)，有

個(gè)度為2的結(jié)點(diǎn)，有

個(gè)結(jié)點(diǎn)只有非空左子樹，有

個(gè)結(jié)點(diǎn)只有非空右子樹。48948810由于最后一層葉子數(shù)為489個(gè)，是奇數(shù)，說(shuō)明有1個(gè)結(jié)點(diǎn)只有非空左子樹；而完全二叉樹中不可能出現(xiàn)只有非空右子樹的結(jié)點(diǎn)(0個(gè))。答：易求出總層數(shù)和末層葉子數(shù)?？倢訑?shù)k=log2n＋1=10;且前9層總結(jié)點(diǎn)數(shù)為29-1=511

(完全二叉樹的前k-1層肯定是滿的)所以末層葉子數(shù)為1000-511=489個(gè)。21請(qǐng)注意葉子結(jié)點(diǎn)總數(shù)≠末層葉子數(shù)！還應(yīng)當(dāng)加上第k-1層（靠右邊）的0度結(jié)點(diǎn)個(gè)數(shù)。分析：k層的489個(gè)葉子的父結(jié)點(diǎn)占上層的245個(gè)結(jié)點(diǎn)（489/2)上層（k=9)右邊的0度結(jié)點(diǎn)數(shù)還有29-1-245=11個(gè)！另一法：可先求2度結(jié)點(diǎn)數(shù),再由此得到葉子總數(shù)。首先，k-2層的28-1（255）個(gè)結(jié)點(diǎn)肯定都是2度的（完全二叉）另外，末層葉子（剛才已求出為489）所對(duì)應(yīng)的雙親也是度＝2，（共有489/2＝244個(gè)）。所以，全部2度結(jié)點(diǎn)數(shù)為255(k-2層)＋244(k-1層)=499個(gè)；總?cè)~子數(shù)＝2度結(jié)點(diǎn)數(shù)＋1=500個(gè)。第i層上的滿結(jié)點(diǎn)數(shù)為2i-1所以，全部葉子數(shù)＝489(末層)＋11(k-1層)=500個(gè)。度為2的結(jié)點(diǎn)＝葉子總數(shù)－1=499個(gè)。2218．設(shè)給定權(quán)值總數(shù)有n個(gè)，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為()A．不確定B．2nC．2n+1D．2n-118‘．有n個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為()A．不確定B．2nC．2n+1D．2n-12319.有關(guān)二叉樹下列說(shuō)法正確的是（）A．二叉樹的度為2B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D．二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為22420.一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹最少有()結(jié)點(diǎn)A．2hB．2h-1C．2h+1D．h+12521.一棵樹高為K的完全二叉樹至少有（）個(gè)結(jié)點(diǎn)A．2k–1B.2k-1–1C.2k-1D.2k

2622.對(duì)二叉樹的結(jié)點(diǎn)從1開始進(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.從根開始按層次遍歷2723.樹的后根遍歷序列等同于該樹對(duì)應(yīng)的二叉樹的().A.先序序列B.中序序列C.后序序列2824.若二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左、右子樹的位置，利用()遍歷方法最合適。A．前序B．中序C．后序D．按層次2925.在二叉樹結(jié)點(diǎn)的先序序列，中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（）A．都不相同B．完全相同C．先序和中序相同，而與后序不同D．中序和后序相同，而與先序不同3026.若X是二叉中序線索樹中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則x的前驅(qū)為()A.X的雙親B.X的右子樹中最左的結(jié)點(diǎn)C.X的左子樹中最右結(jié)點(diǎn)D.X的左子樹中最右葉結(jié)點(diǎn)3127.引入二叉線索樹的目的是（）A．加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B．為了能在二叉樹中方便的進(jìn)行插入與刪除C．為了能方便的找到雙親D．使二叉樹的遍歷結(jié)果唯一3228.n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為（）A．2nB．n－lC．n＋lD．n3329.設(shè)F是一個(gè)森林，B是由F變換得的二叉樹。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（）個(gè)。A．n-1B．nC．n+1D．n+23430.一棵有n個(gè)結(jié)點(diǎn)的二叉樹，按層次從上到下，同一層從左到右順序存儲(chǔ)在一維數(shù)組A[1..n]中，則二叉樹中第i個(gè)結(jié)點(diǎn)（i從1開始用上述方法編號(hào)）的右孩子在數(shù)組A中的位置是（）A．A[2i](2i<=n)B．A[2i+1](2i+1<=n)