數據結構第六章習題課

1、LT 1：二 12Lm：1： mim 1、下圖所示的4棵二叉樹中，不是完全二叉樹的是（） A D 2、二叉樹的前序遍歷序列中，任意一個結點均處在其子女結點的前面.這種說 法（）o A、正確 B、錯誤C、不一定 3、已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序 遍歷序列是（）。 A% acbed Bv decab C、deabc D% cedba 4、如果T2是由有序樹T轉換而來的二叉樹，那么T中結點的后序就是T2中 結點的（）o Av前序B、中序 C、后序 D、層次序 5、深度為5的二叉樹至多有（）個結點。 A、16B、32 C、31 D、10 6、在一個非空二叉

2、樹的中序遍歷序列中，根結點的右邊（）。 A.只有右子樹上的所有結點B、只有右子樹上的部分結點 C、只有左子樹上的部分結點D、只有左子樹上的所有結點 7、樹最適合用來表示（）。 Av有序數據元素B、無序數據元素 C、元素之間具有分支層次關系的數據 D、元素之間無聯(lián)系的數據。 8、任何一棵二叉樹的葉結點在先序、中序和后序遍歷序列中的相對次序（）。 A、不發(fā)生改變B、發(fā)生改變C、不能確定D、以上都不對 9、實現任意二叉樹的后序遍歷的非遞歸算法而不使用棧結構，最佳方案是二叉 樹采用0存儲結構。 A、二叉鏈表 B、廣義表存儲結構C、三叉鏈表D、順序存儲結構 10、對一個滿二叉樹，m個樹葉，n個結點，深度

3、為h,則（）。 A% n=m+h B% h+m=2n C% m=h-l D% n=2h-l IK設n, m為二叉樹上的兩個結點，在中序遍歷時，n在m前的條件是（）。 A. n在m右方 B、n是m祖先C、n在m左方 D、n是m子孫 12.已知一算術表達式的中綴形式為A+B*C-D/E,后綴形式為ABC*+DE/， 其前綴形式為() A.A+B*C/DE B. -A+B*CD/E C. -+*ABC/DE D. -+A*BC/DE 13. 設有一表示算術表達式的二叉樹(見右圖)， 它所表示的算術表達式是() A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C

4、. (A*B+C)/(D*E+ (F-G) ) D. A*B+C/D*E+F-G 14. 在下述結論中，正確的是() 只有一個結點的二叉樹的度為0;二叉樹的度為2；二叉樹的左右子 樹可任意交換；深度為K的完全二叉樹的結點個數小于或等于深度相同的滿 二叉樹。 A.B. C.D. 15設森林F對應的二叉樹為艮 它有m個結點，B的根為p,p的右子樹結點個 數為n,森林F中第一棵樹的結點個數是() A. m-n B. in-n-1 C. n+1 D.條件不足，無法確定 16. 若一棵二叉樹具有10個度為2的結點，5個度為1的結點，貝IJ度為0的結 點個數是0 A. 9B. 11C. 15D.不確定 1

5、7. 一棵完全二叉樹上有1001個結點，其中葉子結點的個數是0 A. 250 B. 500 C. 254 D. 505 E.以上答案都不對 一個具有1025個結點的二叉樹的高h為() A. 11 B. 10C. 11 至 1025 之間 D. 10 至 1024 之間 19.深度為h的滿m叉樹的第k層有()個結點。(l=k=h) A. mk4B. mk-lC. mh4 D. mh-l 20利用二叉鏈表存儲樹，則根結點的右指針是()。 A.指向最左孩子 B.指向最右孩子C.空 D.非空 21. 對二叉樹的結點從1開始進行連續(xù)編號，要求每個結點的編號大于其左、 右孩子的編號同一結點的左右孩子中，其

6、左孩子的編號小于其右孩子的編號. 可采用()次序的遍歷實現編號。 A.先序B.中序C.后序D.從根開始按層次遍歷 22. 若二叉樹采用二叉鏈表存儲結構.要交換其所有分支結點左、右子樹的位 置，利用()遍歷方法最合適。 A.前序 B.中序 C.后序 D.按層次 23一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹 一定滿足0 A.所有的結點均無左孩子 C-只有一個葉子結點 B. 所有的結點均無右孩子 D.是任意一棵二叉樹 24.若X是二叉中序線索樹中一個有左孩子的結點且X不為根，則x的前驅 為() A.X的雙親 C. X的左子樹中最右結點 B. X的右子樹中最左的結點 D. X的

7、左子樹中最右葉結點 25線索二叉樹是一種()結構。 A.邏輯 B.邏輯和存儲 C.物理 D.線性 26. n個結點的線索二叉樹上含有的線索數為() A. 2n B. n1C. n+1D. n 27. 下面幾個符號串編碼集合中.不是前綴編碼的是()。 A. 0,10,110,1111B. 11,10,001,101,0001 C. 00,0100110,1000D. b,c,aa，ac,aba,abb,abc 28. 當一棵有n個結點的二叉樹按層次從上到下，同層次從左到右將數據存放在 一維數組Aln中時，數組中第i個結點的左孩子為0 A. A2l(2i=n) B. A2i+l(2i+l=lchi

8、ld=niill) lh=(2); else lh=(3); lf(p-rchild=null) rh=(4); else rh=(5); if (lhrh) hi=(6)； else hi=(7); else hi=(8); return hi; / 答:(l)p (2)0 (3)height(p-lchild) (4)0 (5) height(p-rchlld) (6)lh+l(7)rh+l(8)0 41. 已知一棵滿二叉樹的結點個數為20到40之間的素數，此二叉樹的葉子結 點有多少個？ 答：結點個數在20到40的滿二叉樹且結點數是素數的數是31,其葉子數是16o 42.用一維數組存放的一

9、棵完全二叉樹；ABCDEFGHIJKLo謂寫出后序遍歷該 二叉樹的訪問結點序列。 答:HIDJKEBLFGCA 43. 棵左右子樹均不空的二叉樹在先序線索化后，其空指針域數為多少？ 答：左右子樹均不空的二叉樹先序線索化后，空指針域為1個(最后訪問結點 的右鏈為空)。 44. 設有正文AADBAACACCDACACAAD,字符集為A,B,C,D，設計一套二進制 編碼，使得上述正文的編碼最短。 45. 編程求以孩”兄弟表示法存儲的森林的葉子結點數。要求描述結構。 題目分析當森林(樹)以孩子兄弟表示法存儲時，若結點沒有孩子 (firstchild=null)，則它必是葉子，總的葉子結點個數是孩子子樹

10、(flrstchild) 上的葉子數和兄弟(nextsibllng)子樹上葉結點個數之和。 typedef struct node EleniTpe data;數據域 struct node *flrstchlld, *nextsibling;孩子與兄弟域 嚴Tree; int Leaves (Tree t)計算以孩子兄弟表示法存儲的森林的葉子數 if(t) if(t-flrstchild=null)若結點無孩子，則該結點必是葉子 return(l+Leaves(t-nextsibllng); 返回葉子結點和其兄弟子樹中的葉子 結點數 else return (Leaves(t-firstch

11、ild)+Leaves(t-nextsibling); 孩子子樹 和兄弟子樹中葉子數之和 結束 Leaves 46. 有n個結點的完全二叉樹存放在一維數組Al.n中，試據此建立一棵用二 叉鏈表表示的二叉樹，根由tree指向。 BITree Creat(ElemTpe A4nt i) /n個結點的完毫二叉樹存于一維數組A中，本算法據此建立以二叉鏈表表 示的完全二叉樹 BiTree tree; If (idata=Ai; if(2*in) tree-lchild=null ； else tree-lchild=Creat(A,2*i)； lf(2*i+ln)tree-rchlld=null ； e

12、lse tree-rchild=Creat(A,2*1+1)； return (tree)； /Creat 算法討論初始調用時,i=l。 47. 以孩子兄弟鏈表為存儲結構，請設計算法求樹/森林的深度。 題目分析由孩子兄弟鏈表表示的樹，求高度的遞歸模型是：若樹為空，高度為 零；若第一子女為空，高度為1和兄弟子樹的高度的大者；否則，高度為第一 子女樹高度加1和兄弟子樹高度的大者。其非遞歸算法使用隊列，逐層遍歷樹, 取得樹的高度。 int TreeDepth(CSTree T) if (!T) return 0; else hl=TreeDepth(T-firstchild); h2=TreeDep

13、th(T-nextslbling); return (max(hl+l,h2); /TreeDepth 48. 設計算法返回二叉樹T的先序序列的最后一個結點的指針，要求采用非遞歸 形式，且不許用棧。 題目分析二叉樹先序序列的最后一個結點，若二叉樹有右子樹，則是右子 樹中最右下的葉子結點；若無右子樹.僅有左子樹則是左子樹最右下的葉子 結點；若二叉樹無左右子樹，則返回根結點。 BITree LastNode(BiTree bt)返回二叉樹bt先序序列的最后一個結點的指針 BITree p=bt; if(bt=null) return(null); else while(p) if (p-rchil

14、d) p=p-rchlld;若右子樹不空，沿右子樹向下 else if (p-lchikl) p=p-lchil(l; /子樹空，左子樹不空，沿左子樹向下 else retijrn(p);左右子樹均為空，p即為所求 /Iastnode 49. 設一棵二叉樹的根結點指針為T, C為計數變，初值為0,試寫出對此二 叉樹中結點計數的算法：BTLC (T, C)。 Int BTLC(BiTree T,int *c)對二叉樹 T 的結點計數 if(T) 枕卄;調用時*c=0 BTLC(T-lchild, 統(tǒng)計左子樹結點 BTLC(T-rchild, 統(tǒng)計右子樹結點 / 50. 設計算法：統(tǒng)計一棵二叉樹中

15、所有葉結點的數目及非葉結點的數目。 void Count(BiTree bt,int *n0,*n) /統(tǒng)計二叉樹bt上葉子結點數110和非葉子 結點數n if(bt) if (bt-lchild=null 非葉結點 Count(bt-lchil(h Count(bt-rchild, /Count 51、編寫算法完成下列操作：無盍復地輸出以孩子兄弟鏈表存儲的樹T中的所 有的邊。輸出形式為(kl,k2)(ki,kj),其中kl和kJ為樹結點中的 結點標識。 Void OutEdger(CSTree T)先根遍歷輸出樹中各條邊 if p=T.firstchlld; while(p) printf(

16、T-data,p-data); OutEdger(p); p=p-nextsibling; / 52、已知Li和Ri (i=l,2, ,n)分別指示二叉樹中第i個結點的左孩子 和右孩子結點，0表示空，試寫出判別結點u是否是結點v的子孫的算法。 status descendent(int L,int RJnt u,int v) if (U else if(descendent(L,R,u,Lv) return TRUE; else return(descendent(L9R9u,Rv); else return FALSE; / 53. 設一棵二叉樹以二叉鏈表為存貯結構，結點結構為(Ichild

17、, data,rchild),設計 一個算法將二叉樹中所有結點的左右子樹相互交換。 類似本題的另外敘述有： (1) 設t為一棵二叉樹的根結點地址指針，試設計一個非遞歸的算法完成把 二叉樹中每個結點的左右孩子位置交換。 (2) 寫一個將二叉樹中每個結點的左右孩子交換的算法。 void exchange(BiTree bt)將二叉樹bt所有結點的左右子樹交換 if(bt)BiTrees； s=bt-lchild; bt-lchild=bt-rchild; bt-rchild=s; 左右子女交換 exchange(bt-lcliikl); 交換左子樹上所有結點的左右子樹 exdiange(bt-rc

18、hlld); 交換右子樹上所有結點的左右子樹 算法討論將上述算法中兩個遞歸調用語句放在前面，將交換語句放在最后, 則是以后序遍歷方式交換所有結點的左右子樹。中序遍歷不適合本題。 下面是本題(1)要求的非遞歸算法 void exchange(BiTree t)交換二叉樹中各結點的左右孩子的非遞歸算法 int top=0; BiTree s,p; /s是二叉樹的結點指針的棧，容足夠大 if(bt) s+top=t; while(top0) t=stop-； if(t-lchildllt-rchild)p=t-lchild;t-lchilcl=t-rchild;t-rchild=p;/ 交 換左右

19、if(t-lchild) s+top=t-lchild; 左子女入棧 if(t-rchlld) s+top=t-rchlld; 右子女入棧 /while(top0) /if(bt) /exchange 54要求二叉樹按二叉鏈表形式存儲， (1)寫一個建立二叉樹的算法。(2)寫一個判別給定的二叉樹是否是完全二 叉樹的算法。 完全二叉樹定義為：深度為K,具有N個結點的二叉樹的每個結點都與深 度為K的滿二叉樹中編號從1至N的結點一一對應。此題以此定義為準。 題目分析二叉樹是遞歸定義的，以遞歸方式建立最簡單。判定是否是完全二 叉樹.可以使用隊列，在遍歷中利用完全二叉樹“若某結點無左子女就不應有 右子女”的原則進行判斷。 BiTree Creat()建立二叉樹的二叉鏈表形式的存儲結構 Elemlpe x ； B