數(shù)據(jù)結構第六章樹和二叉樹習題及答案

1、習題六樹和二叉樹、單項選擇題1. 以下說法錯誤的是（）A. 樹形結構的特點是一個結點可以有多個直接前趨B. 線性結構中的一個結點至多只有一個直接后繼C. 樹形結構可以表達（組織）更復雜的數(shù)據(jù)D. 樹（及一切樹形結構）是一種”分支層次”結構E. 任何只含一個結點的集合是一棵樹2. 下列說法中正確的是（）3.T5.A.B.C.D.（A.B.C.D.A.任何一棵二叉樹中至少有一個結點的度為2 任何一棵二叉樹中每個結點的度都為2任何一棵二叉樹屮的度肯定等于2任何一棵二叉樹中的度可以小于2討論樹、森林和二叉樹的關系，目的是為 ）借助二叉樹上的運算方法去實現(xiàn)對樹的一些運算將樹、森林按二叉樹的存儲方式進行存

2、儲將樹、森林轉換成二叉樹體現(xiàn)一種技巧，沒有什么實際意義4.樹最適合用來表示 有序數(shù)據(jù)元素DC.元素之間具有分支層次關系的數(shù)據(jù)若一-棵二叉樹具有10個度為2的結點，5個度為1的結點,A. 9 B . 11 C15 D .不確定（）B .無序數(shù)據(jù)元素.元素之間無聯(lián)系的數(shù)據(jù)則度為0的結點個數(shù)是（6.一，第二，第三棵樹的結點個數(shù)分別為對應的二叉樹根結點的右子樹上的結點個數(shù)是（設森林F中有三棵樹，第M1, M2和M3與森林FA. M1 B . M1+M2 C . M3 D.M2+M37. 一棵完全二叉樹上有1001個結點，其中葉子結點的個數(shù)是（）A. 250 B .500 C . 254 D . 505

3、 E .以上答案都不對8. 設給定權值總數(shù)有n個，其哈夫曼樹的結點總數(shù)為（）A. 不確定 B . 2n C . 2n+1 D . 2n-19. 二叉樹的第I層上最多含有結點數(shù)為（）in i-i i| |-1 |-1 |A. 2 B . 2-1C. 2 D. 2 -110. -棵二叉樹高度為h,所有結點的度或為0,或為2,則這棵二叉樹最少有（）結點A. 2h B . 2h-1C . 2h+1 D . h+111. 利用二叉鏈表存儲樹，則根結點的右指針是（）。A.指向最左孩了B指向最右孩了12.已知一棵二叉樹的前序遍歷結果為ABCDEF中序遍歷結果CBAEDF則后序遍歷的結為果A. CBEFDA

4、B . FEDCBA13.已知某二叉樹的后序遍歷序列是（）C . CBEDFAD不定A. acbed Bdecab C deabc D.cedbaA.都不相同B完全相同C.先序和屮序相同，而與后序不同D中序和后序相同，而與先序不同15.在完全二叉樹中，若一個結點是葉結點，則它沒（）。A.左子結點B.右子結點C.左子結點和右子結點D.左子結點，右子結點和兄弟結點16.在下列情況中，可稱為二叉樹的是（）14.在二叉樹結點的先序序列，屮序序列和后序序列屮，所有葉子結點的先后順序（)A. 每個結點至多有兩棵子樹的樹B. 哈夫曼樹C. 每個結點至多有兩棵子樹的有序樹D. 每個結點只有一棵右子樹E. 以上

5、答案都不對17. 一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：（）A. 0 B. 1 C. 2 D.不確定18. 引入二叉線索樹的目的是（）A.加快查找結點的前驅或后繼的速度C.為了能方便的找到雙親D19. n個結點的線索二叉樹上含有的線索數(shù)為B .為了能在二叉樹屮方便的進行插入與刪除 使二叉樹的遍歷結果唯一）D. n20. 由3個結點可以構造出多少種不同的二叉樹？（）21.前綴編碼的是（下面幾個符號串編碼集合屮，不是 ）。A. 0,10,110,1111 B11,10,001,101,0001C. 00,010,0110,1000 D . b,c,aa,ac,aba,ab

6、b,abc22. 一棵有n個結點的二叉樹，按層次從上到下，同一層從左到右順序存儲在一維數(shù)組A1.n中，則二叉樹屮第i個結點（i從1開始用上述方法編號）的右孩子在數(shù)組A屮的位置是（）A. A2i(2i=n)B.A2i+1(2i+1lchild=NULL)&(t-rchild=NULL)coun tleaf(t-lchild, &coun t);請?zhí)羁帐怪晟?。二叉樹鏈表的結點類13. 以下程序是二叉鏈表樹屮序遍歷的非遞歸算法, 型的定義如下：typedef struct node /*C語言 /char data; struct node *lchild,*rchild;*bitree;void

7、 vst(bitree bt)/*bt bitree p; p=bt; in itstack(s); /*while(p | !empty(s)/*if(p)push (s,p);(1);廣Pelse p=pop(s); printf(“(” ,p -data);(2)為根結點的指針*/初始化棧s為空棧*/棧s不為空*/入棧*/棧頂元素出棧*/14. 二叉樹存儲結構同上題，以下程序為求二叉樹深度的遞歸算法，請?zhí)羁胀晟浦?。int depth(bitree bt) /*bt為根結點的指針 */int hl,hr;if (bt=NULL) return(1)_上hl=depth(bt-lchild)

8、; hr=depth(bt-rchild);if(2)；return(hr+1);15. 將二叉樹bt屮每一個結點的左右子樹互換的C語言算法如下，其中 ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進隊，出隊和判別隊列是否為空的函數(shù)，請?zhí)顚懰惴ㄥ每?白處，完成其功能。typedef struct nodeint data ; struct node *lchild, *rchild; bt no de;void EXCHANGE node *bt)bt node *p, *q;if (bt)ADDQ(Q,bt);while(!EMPTY(Q)p=DELQ(Q); q=(1)_；

9、 prchild=(2) _;(3) _=q if(p-lchild)Id) (5)_第六章樹和二叉樹、單項選擇題1. A2.D3. A4. C5. B6.D7.E 8. D9. CIO. B11. C12.A13.D14.B15.C16. B 17. B18. A19. C20. D21. B22. D23 . C二、判斷題(在各題后填寫“V或“X，)1. 完全二叉樹一定存在度為1的結點。X2. 對于有N個結點的二叉樹，其高度為 log2no X3. 二叉樹的遍歷只是為了在應用中找到一種線性次序。V4. 一棵一般樹的結點的前序遍歷和后序遍歷分別與它相應二叉樹的結點前序遍歷和后序遍歷是一致 的

10、。X5. 用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結點。X6. 中序遍歷一棵二叉排序樹的結點就可得到排好序的結點序列V7. 完全二叉樹中，若一個結點沒有左孩子，則它必是樹葉。V8. 二叉樹只能用二叉鏈表表示。X9. 給定一棵樹，可以找到唯一的一棵二叉樹與之對應。V10. 用鏈表(llink-rlink)存儲包含n個結點的二叉樹，結點的個指針區(qū)域中有個空 指針。X16.路徑長度最短的樹，路徑上權值較大的結點離根較近。11 .樹形結構屮元素之間存在一個對多個的關系。V12.13.14. 二叉樹中序線索化后，15.將一棵樹轉成二叉樹，根結點沒有左子樹。X 度為二的樹就是二叉樹。X不存在空指針域。X霍夫曼樹的結點個數(shù)不能是偶數(shù)。V哈夫曼樹是帶權三、填空題I p-lchild=null & p-rchlid=null2. (1)2k-1 (2)2k-13. 644. 2nn+15. 先序遍歷后序遍歷中序遍歷6. .(1)2k-2+1 (第k層1個結點，總結點個數(shù)是2H-1,其雙親是2H-1/2=2k-2)(2) |llog2i+17. 4&任何結點至多只有右子女的二叉樹。9. 二叉排序樹10. 前序II 6912. *cou nt+, co