數(shù)據(jù)結(jié)構(gòu)第六章習(xí)題課

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

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

3、為h,則（）。 A% n=m+h B% h+m=2n C% m=h-l D% n=2h-l IK設(shè)n, m為二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是（）。 A. n在m右方 B、n是m祖先C、n在m左方 D、n是m子孫 12.已知一算術(shù)表達(dá)式的中綴形式為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. 設(shè)有一表示算術(shù)表達(dá)式的二叉樹(見右圖)， 它所表示的算術(shù)表達(dá)式是() 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. 在下述結(jié)論中，正確的是() 只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0;二叉樹的度為2；二叉樹的左右子 樹可任意交換；深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿 二叉樹。 A.B. C.D. 15設(shè)森林F對應(yīng)的二叉樹為艮 它有m個(gè)結(jié)點(diǎn)，B的根為p,p的右子樹結(jié)點(diǎn)個(gè) 數(shù)為n,森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是() A. m-n B. in-n-1 C. n+1 D.條件不足，無法確定 16. 若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，貝IJ度為0的結(jié) 點(diǎn)個(gè)數(shù)是0 A. 9B. 11C. 15D.不確定 1

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

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

7、左子樹中最右葉結(jié)點(diǎn) 25線索二叉樹是一種()結(jié)構(gòu)。 A.邏輯 B.邏輯和存儲 C.物理 D.線性 26. n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為() A. 2n B. n1C. n+1D. n 27. 下面幾個(gè)符號串編碼集合中.不是前綴編碼的是()。 A. 0,10,110,1111B. 11,10,001,101,0001 C. 00,0100110,1000D. b,c,aa，ac,aba,abb,abc 28. 當(dāng)一棵有n個(gè)結(jié)點(diǎn)的二叉樹按層次從上到下，同層次從左到右將數(shù)據(jù)存放在 一維數(shù)組Aln中時(shí)，數(shù)組中第i個(gè)結(jié)點(diǎn)的左孩子為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. 已知一棵滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)為20到40之間的素?cái)?shù)，此二叉樹的葉子結(jié) 點(diǎn)有多少個(gè)？ 答：結(jié)點(diǎn)個(gè)數(shù)在20到40的滿二叉樹且結(jié)點(diǎn)數(shù)是素?cái)?shù)的數(shù)是31,其葉子數(shù)是16o 42.用一維數(shù)組存放的一

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

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

11、ild)+Leaves(t-nextsibling); 孩子子樹 和兄弟子樹中葉子數(shù)之和 結(jié)束 Leaves 46. 有n個(gè)結(jié)點(diǎn)的完全二叉樹存放在一維數(shù)組Al.n中，試據(jù)此建立一棵用二 叉鏈表表示的二叉樹，根由tree指向。 BITree Creat(ElemTpe A4nt i) /n個(gè)結(jié)點(diǎn)的完毫二叉樹存于一維數(shù)組A中，本算法據(jù)此建立以二叉鏈表表 示的完全二叉樹 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 算法討論初始調(diào)用時(shí),i=l。 47. 以孩子兄弟鏈表為存儲結(jié)構(gòu)，請?jiān)O(shè)計(jì)算法求樹/森林的深度。 題目分析由孩子兄弟鏈表表示的樹，求高度的遞歸模型是：若樹為空，高度為 零；若第一子女為空，高度為1和兄弟子樹的高度的大者；否則，高度為第一 子女樹高度加1和兄弟子樹高度的大者。其非遞歸算法使用隊(duì)列，逐層遍歷樹, 取得樹的高度。 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. 設(shè)計(jì)算法返回二叉樹T的先序序列的最后一個(gè)結(jié)點(diǎn)的指針，要求采用非遞歸 形式，且不許用棧。 題目分析二叉樹先序序列的最后一個(gè)結(jié)點(diǎn)，若二叉樹有右子樹，則是右子 樹中最右下的葉子結(jié)點(diǎn)；若無右子樹.僅有左子樹則是左子樹最右下的葉子 結(jié)點(diǎn)；若二叉樹無左右子樹，則返回根結(jié)點(diǎn)。 BITree LastNode(BiTree bt)返回二叉樹bt先序序列的最后一個(gè)結(jié)點(diǎn)的指針 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. 設(shè)一棵二叉樹的根結(jié)點(diǎn)指針為T, C為計(jì)數(shù)變，初值為0,試寫出對此二 叉樹中結(jié)點(diǎn)計(jì)數(shù)的算法：BTLC (T, C)。 Int BTLC(BiTree T,int *c)對二叉樹 T 的結(jié)點(diǎn)計(jì)數(shù) if(T) 枕卄;調(diào)用時(shí)*c=0 BTLC(T-lchild, 統(tǒng)計(jì)左子樹結(jié)點(diǎn) BTLC(T-rchild, 統(tǒng)計(jì)右子樹結(jié)點(diǎn) / 50. 設(shè)計(jì)算法：統(tǒng)計(jì)一棵二叉樹中

15、所有葉結(jié)點(diǎn)的數(shù)目及非葉結(jié)點(diǎn)的數(shù)目。 void Count(BiTree bt,int *n0,*n) /統(tǒng)計(jì)二叉樹bt上葉子結(jié)點(diǎn)數(shù)110和非葉子 結(jié)點(diǎn)數(shù)n if(bt) if (bt-lchild=null 非葉結(jié)點(diǎn) Count(bt-lchil(h Count(bt-rchild, /Count 51、編寫算法完成下列操作：無盍復(fù)地輸出以孩子兄弟鏈表存儲的樹T中的所 有的邊。輸出形式為(kl,k2)(ki,kj),其中kl和kJ為樹結(jié)點(diǎn)中的 結(jié)點(diǎn)標(biāo)識。 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個(gè)結(jié)點(diǎn)的左孩子 和右孩子結(jié)點(diǎn)，0表示空，試寫出判別結(jié)點(diǎn)u是否是結(jié)點(diǎn)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. 設(shè)一棵二叉樹以二叉鏈表為存貯結(jié)構(gòu)，結(jié)點(diǎn)結(jié)構(gòu)為(Ichild

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

18、hlld); 交換右子樹上所有結(jié)點(diǎn)的左右子樹 算法討論將上述算法中兩個(gè)遞歸調(diào)用語句放在前面，將交換語句放在最后, 則是以后序遍歷方式交換所有結(jié)點(diǎn)的左右子樹。中序遍歷不適合本題。 下面是本題(1)要求的非遞歸算法 void exchange(BiTree t)交換二叉樹中各結(jié)點(diǎn)的左右孩子的非遞歸算法 int top=0; BiTree s,p; /s是二叉樹的結(jié)點(diǎn)指針的棧，容足夠大 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)寫一個(gè)建立二叉樹的算法。(2)寫一個(gè)判別給定的二叉樹是否是完全二 叉樹的算法。 完全二叉樹定義為：深度為K,具有N個(gè)結(jié)點(diǎn)的二叉樹的每個(gè)結(jié)點(diǎn)都與深 度為K的滿二叉樹中編號從1至N的結(jié)點(diǎn)一一對應(yīng)。此題以此定義為準(zhǔn)。 題目分析二叉樹是遞歸定義的，以遞歸方式建立最簡單。判定是否是完全二 叉樹.可以使用隊(duì)列，在遍歷中利用完全二叉樹“若某結(jié)點(diǎn)無左子女就不應(yīng)有 右子女”的原則進(jìn)行判斷。 BiTree Creat()建立二叉樹的二叉鏈表形式的存儲結(jié)構(gòu) Elemlpe x ； B