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

1、1、下圖所示的4棵二叉樹中，不是完全二叉樹的是（ ）ABCD2、二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子女結(jié)點的前面，這種說法（ ）。 A、正確B、錯誤C、不一定3、已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是（ ）。 A、acbedB、decabC、deabcD、cedba 4、如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的后序就是T2中結(jié)點的（ ）。 A、前序B、中序C、后序D、層次序5、深度為5的二叉樹至多有（ ）個結(jié)點。 A、16B、32C、31D、106、在一個非空二叉樹的中序遍歷序列中，根結(jié)點的右邊（ ）。 A、只有右子樹上的所有

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

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

4、D. A*B+C/D*E+F-G14. 在下述結(jié)論中，正確的是（ ）只有一個結(jié)點的二叉樹的度為0; 二叉樹的度為2； 二叉樹的左右子樹可任意交換; 深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。 A B C D15. 設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點個數(shù)是（ ）Am-n Bm-n-1 Cn+1 D條件不足，無法確定 16若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（ ）A9 B11 C15 D不確定 17一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（ ）A 250 B 500

5、 C254 D505 E以上答案都不對 18. 一個具有1025個結(jié)點的二叉樹的高h為（ ）A11 B10 C11至1025之間 D10至1024之間19深度為h的滿m叉樹的第k層有（ ）個結(jié)點。(1=<k=<h)Amk-1 Bmk-1 Cmh-1 Dmh-120. 利用二叉鏈表存儲樹，則根結(jié)點的右指針是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空21對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用( )次序的遍歷實現(xiàn)編號。A先序 B. 中序 C. 后序 D. 從根開始按層次遍歷22

6、若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利用( )遍歷方法最合適。A前序 B中序 C后序 D按層次23一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（ ）A所有的結(jié)點均無左孩子 B所有的結(jié)點均無右孩子C只有一個葉子結(jié)點 D是任意一棵二叉樹24. 若X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，則x的前驅(qū)為( ) A.X的雙親 B.X的右子樹中最左的結(jié)點 C.X的左子樹中最右結(jié)點 D.X的左子樹中最右葉結(jié)點25. 線索二叉樹是一種（ ）結(jié)構(gòu)。A 邏輯 B 邏輯和存儲 C 物理 D線性26n個結(jié)點的線索二叉樹上含有的線索數(shù)為（ ）A2n

7、Bnl Cnl Dn 27下面幾個符號串編碼集合中，不是前綴編碼的是（ ）。A0,10,110,1111 B11,10,001,101,0001C00,010,0110,1000 Db,c,aa,ac,aba,abb,abc 28. 當(dāng)一棵有n個結(jié)點的二叉樹按層次從上到下，同層次從左到右將數(shù)據(jù)存放在一維數(shù)組 Al.n中時，數(shù)組中第i個結(jié)點的左孩子為（ ）AA2i(2i=<n) B. A2i+1(2i+1=< n) CAi/2 D無法確定29、高度為h的完全二叉樹至少有多少個結(jié)點?至多有多少個結(jié)點?解：高度為h的完全二叉樹至少有2h-1個結(jié)點，至多有2h-1個結(jié)點(也就是滿二叉樹)。

8、30、在什么樣的情況下，等長編碼是最優(yōu)的前綴碼?答：在每個字符的使用概率相同的情況下，也即在哈夫曼樹中每片葉子的權(quán)重相等的時候，等長編碼是最優(yōu)的前綴碼。31.假設(shè)在樹中，結(jié)點x是結(jié)點y的雙親時,用(x,y)來表示樹邊。已知一棵樹邊的集合為(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用圖表示出此樹，并回答下列問題：(1)哪個是根結(jié)點? (2)哪些是葉結(jié)點? (3)哪個是g的雙親? (4)哪些是g的祖先? (5)哪些是g的孩子? (6)哪些是e的子孫? (7)哪些是e的兄弟?哪些是f的兄弟

9、? (8)結(jié)點b和n的層次各是多少? (9)樹的深度是多少? (10)以結(jié)點c為根的子樹的深度是多少? (11) 樹的度數(shù)是多少?答：這是測試我們對樹的基本概念的掌握情況。a是根結(jié)點；mndfjkl是葉結(jié)點；c是g的雙親；c,a是g的祖先；j,k是g的孩子；imn是e的子孫；d是e的兄弟，g,h是f的兄弟；b的層次是2，n的層次是5；樹的深度是5；以c為根的子樹深度是3；樹的度數(shù)是3。32、試找出分別滿足下面條件的所有二叉樹：(1)前序序列和中序序列相同； (2)中序序列和后序序列相同；(3)前序序列和后序序列相同； (4)前序、中序、后序序列均相同。答：(1) 前序序列和中序序列相同的二叉樹

10、是：沒有左子樹的二叉樹(右單支樹)。(2) 中序序列和后序序列相同的二叉樹是：沒有右子樹的二叉樹(左單支樹)。(3) 前序序列和后序序列相同的二叉樹是：只有根結(jié)點的二叉樹。(4) 前序、中序、后序序列均相同的二叉樹：只有根結(jié)點的二叉樹。33、對二叉樹中的結(jié)點進行按層次順序(每一層自左至右)的訪問操作稱為二叉樹的層次遍歷，遍歷所得到的結(jié)點序列稱為二叉樹層次序列?，F(xiàn)已知一棵二叉樹的層次序列為ABCDEFGHIJ,中序序列為DBGEHJACIF，請畫出此二叉樹。解： A        / B C /  D E F/ &#

11、160;   /G H I       J34、對下圖所示的森林：(1)求各樹的前序序列和后序序列；(2)求森林的前序序列和后序序列；(3)將此森林轉(zhuǎn)換為相應(yīng)的二叉樹；(4)給出(a)所示樹的以雙親鏈表表示、孩子鏈表表示、雙親孩子鏈表表示及孩子兄弟鏈表表示等四種存儲結(jié)構(gòu)，并指出哪些存儲結(jié)構(gòu)易于求指定結(jié)點的祖先，哪些易于求指定結(jié)點的后代?解：(1)   (a)的前序序列：ABCDEF    后序序列：BDEFCA     (b)的前序序列：GHIJ

12、K     后序序列：IJKHG      (c)的前序序列：LMPQRNO     后序序列：QRPMNOL(2)  此森林的前序序列： ABCDEFGHIJKLMPQRNO    此森林的后序序列： BDEFCAIJKHGQRPMNOL(3) 略(4) 略35完全二叉樹中，結(jié)點個數(shù)為n，則編號最大的分支結(jié)點的編號為 。答：ën/2û36二叉樹結(jié)點的對稱序序列為A,B,C,D,E,F,G,后序序列為B,D,C,A,F,G,E

13、,則該二叉樹結(jié)點的前序序列為(1) ,則該二叉樹對應(yīng)的樹林包括 (2) 棵樹。答：(1)EACBDGF （2）237具有n個結(jié)點的滿二叉樹，其葉結(jié)點的個數(shù)是_。答：(n+1)/2設(shè)內(nèi)部節(jié)點數(shù)為a，葉節(jié)點數(shù)為b，明顯有a+b=n (1)，非空滿二叉樹中所有節(jié)點的出度正好等于入度，每個內(nèi)部節(jié)點出度為2，葉節(jié)點出度為0，所有節(jié)點的出度和為2a；根節(jié)點入度為0，其他節(jié)點的入度為1，所有節(jié)點的入度和為a+b-1;因此有2a=a+b-1 (2)。由(1)(2)得b=(n+1)/2，a=(n-1)/2。另外可得b=a+1，也就是說，非空滿二叉樹的葉節(jié)點數(shù)正好比內(nèi)部節(jié)點數(shù)多1。38設(shè)一棵后序線索樹的高是50，

14、結(jié)點x是樹中的一個結(jié)點，其雙親是結(jié)點y,y的右子樹高度是31，x是y的左孩子。則確定x的后繼最多需經(jīng)過_中間結(jié)點（不含后繼及x本身）答：31（x的后繼是經(jīng)x的雙親y的右子樹中最左下的葉結(jié)點）39有一份電文中共使用 6個字符:a,b,c,d,e,f,它們的出現(xiàn)頻率依次為2,3,4,7,8,9，試構(gòu)造一棵哈夫曼樹，則其加權(quán)路徑長度WPL為(1)，字符c的編碼是(2)。答：(1)80 (2)001（不唯一）40下面是求二叉樹高度的類C寫的遞歸算法，試補充完整。說明二叉樹的兩指針域為lchild與rchild, 算法中p為二叉樹的根，lh和rh分別為以p為根的二叉樹的左子樹和右子樹的高，hi為以p為根

15、的二叉樹的高，hi最后返回。height(p)if (1) if(p->lchild=null) lh=(2) ; else lh=(3);if(p->rchild=null) rh=(4); else rh=(5);if (lh>rh) hi=(6)；else hi=(7); else hi=(8);return hi;/ 答：(1)p (2)0 (3)height(p->lchild) (4)0 (5)height(p->rchild) (6)lh+1 (7)rh+1 (8)041已知一棵滿二叉樹的結(jié)點個數(shù)為20到40之間的素數(shù)，此二叉樹的葉子結(jié)點有多少個？答

16、：結(jié)點個數(shù)在20到40的滿二叉樹且結(jié)點數(shù)是素數(shù)的數(shù)是31，其葉子數(shù)是16。42用一維數(shù)組存放的一棵完全二叉樹；ABCDEFGHIJKL。請寫出后序遍歷該二叉樹的訪問結(jié)點序列。答：HIDJKEBLFGCA43一棵左右子樹均不空的二叉樹在先序線索化后，其空指針域數(shù)為多少？答：左右子樹均不空的二叉樹先序線索化后，空指針域為1個（最后訪問結(jié)點的右鏈為空）。44設(shè)有正文AADBAACACCDACACAAD,字符集為A,B,C,D,設(shè)計一套二進制編碼，使得上述正文的編碼最短。45編程求以孩子兄弟表示法存儲的森林的葉子結(jié)點數(shù)。要求描述結(jié)構(gòu)。題目分析當(dāng)森林（樹）以孩子兄弟表示法存儲時，若結(jié)點沒有孩子（firs

17、tchild=null）,則它必是葉子，總的葉子結(jié)點個數(shù)是孩子子樹（firstchild）上的葉子數(shù)和兄弟（nextsibling）子樹上葉結(jié)點個數(shù)之和。typedef struct nodeElemType data; /數(shù)據(jù)域 struct node * firstchild, * nextsibling;/孩子與兄弟域 *Tree;int Leaves (Tree t) /計算以孩子-兄弟表示法存儲的森林的葉子數(shù) if(t) if(t->firstchild =null) /若結(jié)點無孩子，則該結(jié)點必是葉子 return(1+Leaves(t->nextsibling); /返

18、回葉子結(jié)點和其兄弟子樹中的葉子結(jié)點數(shù)else return (Leaves(t->firstchild)+Leaves(t->nextsibling); /孩子子樹和兄弟子樹中葉子數(shù)之和/結(jié)束Leaves46有n個結(jié)點的完全二叉樹存放在一維數(shù)組A1.n中，試據(jù)此建立一棵用二叉鏈表表示的二叉樹，根由tree指向。 BiTree Creat(ElemType A,int i)/n個結(jié)點的完全二叉樹存于一維數(shù)組A中，本算法據(jù)此建立以二叉鏈表表示的完全二叉樹 BiTree tree;if (i<=n) tree=(BiTree)malloc(sizeof(BiNode); tree-

19、>data=Ai;if(2*i>n) tree->lchild=null；else tree->lchild=Creat(A,2*i)；if(2*i+1>n) tree->rchild=null；else tree->rchild=Creat(A,2*i+1)；return (tree)； /Creat算法討論初始調(diào)用時,i=1。47. 以孩子兄弟鏈表為存儲結(jié)構(gòu)，請設(shè)計算法求樹/森林的深度。題目分析由孩子兄弟鏈表表示的樹，求高度的遞歸模型是：若樹為空，高度為零；若第一子女為空，高度為1和兄弟子樹的高度的大者；否則，高度為第一子女樹高度加1和兄弟子樹高度

20、的大者。其非遞歸算法使用隊列，逐層遍歷樹，取得樹的高度。int TreeDepth(CSTree T)if (!T) return 0; else h1= TreeDepth(T->firstchild); h2= TreeDepth(T->nextsibling); return (max(h1+1,h2); / TreeDepth48. 設(shè)計算法返回二叉樹T的先序序列的最后一個結(jié)點的指針，要求采用非遞歸形式，且不許用棧。題目分析二叉樹先序序列的最后一個結(jié)點，若二叉樹有右子樹，則是右子樹中最右下的葉子結(jié)點；若無右子樹，僅有左子樹，則是左子樹最右下的葉子結(jié)點；若二叉樹無左右子樹，則

21、返回根結(jié)點。BiTree LastNode(BiTree bt) /返回二叉樹bt先序序列的最后一個結(jié)點的指針BiTree p=bt;if(bt=null) return(null);else while(p) if (p->rchild) p=p->rchild; /若右子樹不空，沿右子樹向下else if (p->lchild) p=p->lchild; /右子樹空，左子樹不空，沿左子樹向下else return(p); /左右子樹均為空，p即為所求/lastnode49. 設(shè)一棵二叉樹的根結(jié)點指針為T，C為計數(shù)變量，初值為0，試寫出對此二叉樹中結(jié)點計數(shù)的算法：BT

22、LC（T，C）。int BTLC(BiTree T,int *c) /對二叉樹T的結(jié)點計數(shù)if(T) *c+; /調(diào)用時*c=0BTLC(T->lchild,&c); /統(tǒng)計左子樹結(jié)點BTLC(T->rchild,&c); /統(tǒng)計右子樹結(jié)點 /50設(shè)計算法：統(tǒng)計一棵二叉樹中所有葉結(jié)點的數(shù)目及非葉結(jié)點的數(shù)目。void Count(BiTree bt,int *n0,*n) /統(tǒng)計二叉樹bt上葉子結(jié)點數(shù)n0和非葉子結(jié)點數(shù)nif(bt)if (bt->lchild=null && bt->rchild=null) *n0+；/葉子結(jié)點 else

23、 *n+; /非葉結(jié)點 Count(bt->lchild,&n0,&n); Count(bt->rchild,&n0,&n); /Count51、編寫算法完成下列操作：無重復(fù)地輸出以孩子兄弟鏈表存儲的樹T中的所有的邊。輸出形式為（k1,k2）（ki,kj），其中ki和kj為樹結(jié)點中的結(jié)點標(biāo)識。Void OutEdger(CSTree T) /先根遍歷輸出樹中各條邊 if (T) p=T->firstchild; while(p) printf(T->data,p->data); OutEdger(p); p=p->nextsi

24、bling; /52、已知Li和Ri（i=1,2，n）分別指示二叉樹中第i個結(jié)點的左孩子和右孩子結(jié)點，0表示空，試寫出判別結(jié)點u是否是結(jié)點v的子孫的算法。status descendent(int L,int R,int u,int v) if (u&&v) if(Lv=u|Rv=u) return TRUE; else if(descendent(L,R,u,Lv) return TRUE; else return(descendent(L,R,u,Rv); else return FALSE;/53. 設(shè)一棵二叉樹以二叉鏈表為存貯結(jié)構(gòu)，結(jié)點結(jié)構(gòu)為(lchild, data,

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

26、ge(bt->rchild); /交換右子樹上所有結(jié)點的左右子樹 算法討論將上述算法中兩個遞歸調(diào)用語句放在前面，將交換語句放在最后，則是以后序遍歷方式交換所有結(jié)點的左右子樹。中序遍歷不適合本題。下面是本題（1）要求的非遞歸算法void exchange(BiTree t) /交換二叉樹中各結(jié)點的左右孩子的非遞歸算法int top=0; BiTree s,p; /s是二叉樹的結(jié)點指針的棧，容量足夠大 if(bt)s+top=t; while(top>0)t=stop-;if(t->lchild|t->rchild)p=t->lchild;t->lchild=t->rchild;t->rchild=p;/交換左右if(t->lchild) s+top=t->lchild; /左子女入棧if(t->rchild) s+top=t->rchild; /右子女入棧/while(top>0)/if(bt) /exchange 54要求二叉樹按二叉鏈表形式存儲，（1）寫一個建立二叉樹的算法。（2）寫一個判別給定的二叉樹是否是完全二叉樹的算法。完全二叉樹定義為：深度為K，具有N個結(jié)點的二叉樹的每個結(jié)點都與深度為K的滿二叉樹中編號從1至N的結(jié)點一一對應(yīng)。此題