第6章 樹和二叉樹(相關試題)數(shù)據(jù)結構

《數(shù)據(jù)結構》（C語言版）

第6章樹和二叉樹

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

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

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

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

C．deabcD．cedba

4二叉樹的遍歷3.

對二叉樹的結點從1開始進行連續(xù)編號，要求每個結點的編號大于其左、右孩子的編號，同一結點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用()次序的遍歷實現(xiàn)編號。A．先序B.中序C.后序D.從根開始按層次遍歷5二叉樹的遍歷4.

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

D．H6二叉樹的遍歷5.

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

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

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

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

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

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

個葉子結點，有

個度為2的結點，有

個結點只有非空左子樹，有

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

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

2622.對二叉樹的結點從1開始進行連續(xù)編號，要求每個結點的編號大于其左、右孩子的編號，同一結點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用()次序的遍歷實現(xiàn)編號。A．先序B.中序C.后序D.從根開始按層次遍歷2723.樹的后根遍歷序列等同于該樹對應的二叉樹的().A.先序序列B.中序序列C.后序序列2824.若二叉樹采用二叉鏈表存儲結構，要交換其所有分支結點左、右子樹的位置，利用()遍歷方法最合適。A．前序B．中序C．后序D．按層次2925.在二叉樹結點的先序序列，中序序列和后序序列中，所有葉子結點的先后順序（）A．都不相同B．完全相同C．先序和中序相同，而與后序不同D．中序和后序相同，而與先序不同3026.若X是二叉中序線索樹中一個有左孩子的結點，且X不為根，則x的前驅為()A.X的雙親B.X的右子樹中最左的結點C.X的左子樹中最右結點D.X的左子樹中最右葉結點3127.引入二叉線索樹的目的是（）A．加快查找結點的前驅或后繼的速度B．為了能在二叉樹中方便的進行插入與刪除C．為了能方便的找到雙親D．使二叉樹的遍歷結果唯一3228.n個結點的線索二叉樹上含有的線索數(shù)為（）A．2nB．n－lC．n＋lD．n3329.設F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結點，則B中右指針域為空的結點有（）個。A．n-1B．nC．n+1D．n+23430.一棵有n個結點的二叉樹，按層次從上到下，同一層從左到右順序存儲在一維數(shù)組A[1..n]中，則二叉樹中第i個結點（i從1開始用上述方法編號）的右孩子在數(shù)組A中的位置是（）A．A[2i](2i<=n)B．A[2i+1](2i+1<=n)