數(shù)據(jù)結(jié)構(gòu)第六章樹和二叉樹習(xí)題及答案

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

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

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

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

5、答案都不對(duì)17. 一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個(gè)數(shù)是：（）A. 0 B. 1 C. 2 D.不確定18. 引入二叉線索樹的目的是（）A.加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度C.為了能方便的找到雙親D19. n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為B .為了能在二叉樹屮方便的進(jìn)行插入與刪除 使二叉樹的遍歷結(jié)果唯一）D. n20. 由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（）21.前綴編碼的是（下面幾個(gè)符號(hào)串編碼集合屮，不是 ）。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個(gè)結(jié)點(diǎn)的二叉樹，按層次從上到下，同一層從左到右順序存儲(chǔ)在一維數(shù)組A1.n中，則二叉樹屮第i個(gè)結(jié)點(diǎn)（i從1開始用上述方法編號(hào)）的右孩子在數(shù)組A屮的位置是（）A. A2i(2i=n)B.A2i+1(2i+1lchild=NULL)&(t-rchild=NULL)coun tleaf(t-lchild, &coun t);請(qǐng)?zhí)羁帐怪晟啤６鏄滏湵淼慕Y(jié)點(diǎn)類13. 以下程序是二叉鏈表樹屮序遍歷的非遞歸算法, 型的定義如下：typedef struct node /*C語(yǔ)言 /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)為根結(jié)點(diǎn)的指針*/初始化棧s為空棧*/棧s不為空*/入棧*/棧頂元素出棧*/14. 二叉樹存儲(chǔ)結(jié)構(gòu)同上題，以下程序?yàn)榍蠖鏄渖疃鹊倪f歸算法，請(qǐng)?zhí)羁胀晟浦?。int depth(bitree bt) /*bt為根結(jié)點(diǎn)的指針 */int hl,hr;if (bt=NULL) return(1)_上hl=depth(bt-lchild)

8、; hr=depth(bt-rchild);if(2)；return(hr+1);15. 將二叉樹bt屮每一個(gè)結(jié)點(diǎn)的左右子樹互換的C語(yǔ)言算法如下，其中 ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進(jìn)隊(duì)，出隊(duì)和判別隊(duì)列是否為空的函數(shù)，請(qǐng)?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)_第六章樹和二叉樹、單項(xiàng)選擇題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的結(jié)點(diǎn)。X2. 對(duì)于有N個(gè)結(jié)點(diǎn)的二叉樹，其高度為 log2no X3. 二叉樹的遍歷只是為了在應(yīng)用中找到一種線性次序。V4. 一棵一般樹的結(jié)點(diǎn)的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點(diǎn)前序遍歷和后序遍歷是一致 的

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