數(shù)據(jù)結構第六章知識題課

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

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

3、A 、n=m+hB 、h+m=2nC、m=h-1D 、n=2 h -111 、設 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/DEB. -A+B*CD/EC -+*ABC/DED. -+A*BC/DE/13. 設有一表示算術表達式的二叉樹（見右圖） ，+*C *-它所表示的算術表達式是（）A BDE F GA. A*B+C/(D*E)+(F-G)B. (A*

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

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

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

7、.X 的左子樹中最右葉結點25.線索二叉樹是一種（）結構。A 邏輯B 邏輯和存儲C 物理D線性26 n 個結點的線索二叉樹上含有的線索數(shù)為（）A 2nB n lCn lD n27 下面幾個符號串編碼集合中，不是前綴編碼的是（）。A 0,10,110,1111B 11,10,001,101,0001C 00,010,0110,1000D b,c,aa,ac,aba,abb,abc28. 當一棵有 n 個結點的二叉樹按層次從上到下，同層次從左到右將數(shù)據(jù)存放在一維數(shù)組Al.n 中時，數(shù)組中第 i 個結點的左孩子為（）A A2i(2i=<n)B. A2i+1(2i+1=< n)CAi/2D

8、 無* *法確定29 、高度為 h 的完全二叉樹至少有多少個結點?至多有多少個結點 ?解：高度為 h 的完全二叉樹至少有2 h-1 個結點，至多有2 h-1 個結點 (也就是滿二叉樹 )。30 、在什么樣的情況下，等長編碼是最優(yōu)的前綴碼?答：在每個字符的使用概率相同的情況下，也即在哈夫曼樹中每片葉子的權重相等的時候，等長編碼是最優(yōu)的前綴碼。31 .假設在樹中，結點x 是結點 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)用圖表

9、示出此樹，并回答下列問題：(1) 哪個是根結點 ? (2) 哪些是葉結點 ? (3) 哪個是 g 的雙親 ? (4) 哪些是 g 的祖先 ?(5) 哪些是 g 的孩子 ? (6) 哪些是 e 的子孫 ? (7) 哪些是 e 的兄弟 ?哪些是 f 的兄弟 ?(8) 結點 b 和 n 的層次各是多少 ? (9) 樹的深度是多少 ? (10) 以結點 c 為根的子樹的深度是多少 ? (11) 樹的度數(shù)是多少 ?答：這是測試我們對樹的基本概念的掌握情況。a 是根結點； mndfjkl是葉結點； c 是 g 的雙親； c,a 是 g 的祖先；j,k 是 g 的孩子； imn 是 e 的子孫； d 是 e

10、 的兄弟， g,h 是 f 的兄弟；b 的層次是 2 ，n 的層次是 5；樹的深度是5；以 c 為根的子樹深度是3 ；* *樹的度數(shù)是 3 。32 、試找出分別滿足下面條件的所有二叉樹：(1) 前序序列和中序序列相同； (2) 中序序列和后序序列相同；(3) 前序序列和后序序列相同； (4) 前序、中序、后序序列均相同。答：(1) 前序序列和中序序列相同的二叉樹是：沒有左子樹的二叉樹(右單支樹 )。(2) 中序序列和后序序列相同的二叉樹是：沒有右子樹的二叉樹(左單支樹 )。(3) 前序序列和后序序列相同的二叉樹是：只有根結點的二叉樹。(4) 前序、中序、后序序列均相同的二叉樹：只有根結點的二叉

11、樹。33 、對二叉樹中的結點進行按層次順序( 每一層自左至右 ) 的訪問操作稱為二叉樹的層次遍歷，遍歷所得到的結點序列稱為二叉樹層次序列?，F(xiàn)已知一棵二叉樹的層次序列為 ABCDEFGHIJ, 中序序列為 DBGEHJACIF ，請畫出此二叉樹。解： A/ B C/ D EF/ /G H IJ34 、對下圖所示的森林：* *(1) 求各樹的前序序列和后序序列；(2) 求森林的前序序列和后序序列；(3) 將此森林轉換為相應的二叉樹；(4) 給出 (a) 所示樹的以雙親鏈表表示、孩子鏈表表示、雙親孩子鏈表表示及孩子兄弟鏈表表示等四種存儲結構， 并指出哪些存儲結構易于求指定結點的祖先， 哪些易于求指定

12、結點的后代 ?解：(1)(a) 的前序序列： ABCDEF后序序列： BDEFCA(b) 的前序序列： GHIJK后序序列： IJKHG(c) 的前序序列： LMPQRNO后序序列： QRPMNOL(2) 此森林的前序序列： ABCDEFGHIJKLMPQRNO此森林的后序序列：BDEFCAIJKHGQRPMNOL(3) 略(4) 略* *35 完全二叉樹中，結點個數(shù)為n ，則編號最大的分支結點的編號為。答： n/236 二叉樹結點的對稱序序列為A,B,C,D,E,F,G,后序序列為B,D,C,A,F,G,E,則該二叉樹結點的前序序列為(1),則該二叉樹對應的樹林包括(2)棵樹。答： (1)E

13、ACBDGF（2）237 具有 n 個結點的滿二叉樹，其葉結點的個數(shù)是_。答： (n+1)/2設內部節(jié)點數(shù)為a，葉節(jié)點數(shù)為 b ，明顯有 a+b=n (1)，非空滿二叉樹中所有節(jié)點的出度正好等于入度，每個內部節(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ù)正好比內部節(jié)點數(shù)多1 。38 設一棵后序線索樹的高是50 ，結點 x 是樹中的一個結點， 其雙親是結點 y

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

15、左子樹和右子樹的高，hi 為以 p 為根的二叉樹的高，hi最后返回。height(p)if (1)if(p->lchild=null) lh=(2) if(p->rchild=null) rh=(4); else; elselh=(3);rh=(5);if (lh>rh) hi=(6)elsehi=(8);returnhi;/；elsehi=(7);答： (1)p (2)0 (3)height(p->lchild)(4)0(5)height(p->rchild)(6)lh+1(7)rh+1(8)0* *41 已知一棵滿二叉樹的結點個數(shù)為20 到 40 之間的素數(shù)，

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

17、 當森林（樹）以孩子兄弟表示法存儲時，若結點沒有孩子（ firstchild=null）,則它必是葉子， 總的葉子結點個數(shù)是孩子子樹 （firstchild）上的葉子數(shù)和兄弟（ nextsibling）子樹上葉結點個數(shù)之和。typedefstructnodeElemTypedata;/ 數(shù)據(jù)域* *structnode * firstchild, * nextsibling;/孩子與兄弟域*Tree;int Leaves (Tree t)/ 計算以孩子 - 兄弟表示法存儲的森林的葉子數(shù)if(t)if(t->firstchild=null)/ 若結點無孩子，則該結點必是葉子return(1

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

19、=(BiTree)malloc(sizeof(BiNode); tree->data=Ai;if(2*i>n)tree->lchild=null；elsetree->lchild=Creat(A,2*i)；if(2*i+1>n)tree->rchild=null；elsetree->rchild=Creat(A,2*i+1)；* *return (tree)；/Creat 算法討論 初始調用時 ,i=1 。47. 以孩子兄弟鏈表為存儲結構，請設計算法求樹 / 森林的深度。 題目分析 由孩子兄弟鏈表表示的樹，求高度的遞歸模型是：若樹為空，高度為零；若第一

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

21、最右下的葉子結點； 若無右子樹， 僅有左子樹， 則是左子樹最右下的葉子結* *點；若二叉樹無左右子樹，則返回根結點。BiTree LastNode(BiTree bt)/ 返回二叉樹 bt 先序序列的最后一個結點的指針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 即為所求/lastn

22、ode49. 設一棵二叉樹的根結點指針為 T，C 為計數(shù)變量，初值為 0，試寫出對此二叉樹中結點計數(shù) 的算法： BTLC（T，C）。int BTLC(BiTree T,int *c)/ 對二叉樹 T 的結點計數(shù)if(T)*c+;/ 調用時 *c=0BTLC(T->lchild,&c);/ 統(tǒng)計左子樹結點BTLC(T->rchild,&c);/ 統(tǒng)計右子樹結點/* *50 設計算法：統(tǒng)計一棵二叉樹中所有葉結點的數(shù)目及非葉結點的數(shù)目。void Count(BiTree bt,int *n0,*n) /統(tǒng)計二叉樹 bt 上葉子結點數(shù) n0 和非葉子結點數(shù) nif(bt)i

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

24、遍歷輸出樹中各條邊 printf(T->data,p->data); OutEdger(p); p=p->nextsibling;* */52 、已知 Li 和 Ri （i=1,2 ， ， n ）分別指示二叉樹中第i 個結點的左孩子和右孩子結點， 0 表示空，試寫出判別結點u 是否是結點 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 retur

25、n(descendent(L,R,u,Rv);else return FALSE;/53.設一棵二叉樹以二叉鏈表為存貯結構，結點結構為(lchild, data,rchild)，設計一個算法將二叉樹中所有結點的左，右子樹相互交換。類似本題的另外敘述有：（1 ）設 t 為一棵二叉樹的根結點地址指針，試設計一個非遞歸的算法完成把二叉樹中每個結點的左右孩子位置交換。（2 ）寫一個將二叉樹中每個結點的左右孩子交換的算法。void exchange(BiTree bt)/ 將二叉樹 bt 所有結點的左右子樹交換* *if(bt) BiTree s；s=bt->lchild; bt->lchi

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

27、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)* */exchange54 要求二叉樹按二叉鏈表形式存儲，（ 1）寫一個建立二叉樹的算法。（ 2 ）寫一個判別給定的二叉樹是否是完全二叉樹的算法。完全二叉樹定義為：深度為 K，具有 N 個結點的二叉樹的每個結點都與深度為 K 的滿二叉樹中編號從 1 至 N 的結點