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

習(xí)題六 樹(shù)和二叉樹(shù)一、單項(xiàng)選擇題1 以下說(shuō)法錯(cuò)誤的是 ( )A樹(shù)形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)可以有多個(gè)直接前趨B線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有一個(gè)直接后繼C樹(shù)形結(jié)構(gòu)可以表達(dá)(組織)更復(fù)雜的數(shù)據(jù)D樹(shù)(及一切樹(shù)形結(jié)構(gòu))是一種分支層次結(jié)構(gòu)E任何只含一個(gè)結(jié)點(diǎn)的集合是一棵樹(shù)2下列說(shuō)法中正確的是 ( )A任何一棵二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2B任何一棵二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度都為2C任何一棵二叉樹(shù)中的度肯定等于2D任何一棵二叉樹(shù)中的度可以小于23討論樹(shù)、森林和二叉樹(shù)的關(guān)系，目的是為了（ ）A借助二叉樹(shù)上的運(yùn)算方法去實(shí)現(xiàn)對(duì)樹(shù)的一些運(yùn)算B將樹(shù)、森林按二叉樹(shù)的存儲(chǔ)方式進(jìn)行存儲(chǔ)C將樹(shù)、森林轉(zhuǎn)換成二叉樹(shù)D體現(xiàn)一種技巧，沒(méi)有什么實(shí)際意義4樹(shù)最適合用來(lái)表示 ( )A有序數(shù)據(jù)元素 B無(wú)序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù) D元素之間無(wú)聯(lián)系的數(shù)據(jù)5若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（ ）A9 B11 C15 D不確定 6設(shè)森林F中有三棵樹(shù)，第一，第二，第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2和M3。與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是（ ）。AM1 BM1+M2 CM3 DM2+M37一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ ）A 250 B 500 C254 D505 E以上答案都不對(duì) 8. 設(shè)給定權(quán)值總數(shù)有n 個(gè)，其哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為( ) A不確定 B2n C2n+1 D2n-19二叉樹(shù)的第I層上最多含有結(jié)點(diǎn)數(shù)為（ ）A2I B 2I-1-1 C 2I-1 D2I -110一棵二叉樹(shù)高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹(shù)最少有( )結(jié)點(diǎn)A2h B2h-1 C2h+1 Dh+1 11. 利用二叉鏈表存儲(chǔ)樹(shù)，則根結(jié)點(diǎn)的右指針是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空12已知一棵二叉樹(shù)的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為（ ）。ACBEFDA B FEDCBA C CBEDFA D不定 13已知某二叉樹(shù)的后序遍歷序列是dabec, 中序遍歷序列是debac , 它的前序遍歷是（ ）。Aacbed Bdecab Cdeabc Dcedba 14在二叉樹(shù)結(jié)點(diǎn)的先序序列，中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（ ）A都不相同 B完全相同 C先序和中序相同，而與后序不同 D中序和后序相同，而與先序不同 15在完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒(méi)（ ）。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在下列情況中，可稱為二叉樹(shù)的是（ ）A每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)的樹(shù) B. 哈夫曼樹(shù) C每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)的有序樹(shù) D. 每個(gè)結(jié)點(diǎn)只有一棵右子樹(shù) E以上答案都不對(duì) 17. 一棵左右子樹(shù)均不空的二叉樹(shù)在先序線索化后，其中空的鏈域的個(gè)數(shù)是：( )。A. 0 B. 1 C. 2 D. 不確定 18. 引入二叉線索樹(shù)的目的是（ ）A加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度 B為了能在二叉樹(shù)中方便的進(jìn)行插入與刪除C為了能方便的找到雙親 D使二叉樹(shù)的遍歷結(jié)果唯一19n個(gè)結(jié)點(diǎn)的線索二叉樹(shù)上含有的線索數(shù)為（ ）A2n Bnl Cnl Dn 20由3 個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹(shù)？（ ）A2 B3 C4 D5 21下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（ ）。A0,10,110,1111 B11,10,001,101,0001 C00,010,0110,1000 Db,c,aa,ac,aba,abb,abc 22. 一棵有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，按層次從上到下，同一層從左到右順序存儲(chǔ)在一維數(shù)組A1.n中，則二叉樹(shù)中第i個(gè)結(jié)點(diǎn)（i從1開(kāi)始用上述方法編號(hào)）的右孩子在數(shù)組A中的位置是（ ）AA2i(2i=n) BA2i+1(2i+1lchild=NULL)&(t-rchild=NULL)_; countleaf(t-lchild,&count); _ 13以下程序是二叉鏈表樹(shù)中序遍歷的非遞歸算法，請(qǐng)?zhí)羁帐怪晟?。二叉?shù)鏈表的結(jié)點(diǎn)類型的定義如下： typedef struct node /*C語(yǔ)言/ char data; struct node *lchild,*rchild;*bitree;void vst(bitree bt) /*bt為根結(jié)點(diǎn)的指針*/ bitree p; p=bt; initstack(s); /*初始化棧s為空棧*/while(p | !empty(s) /*棧s不為空*/ if(p) push (s,p); (1)_ ; /*P入棧*/else p=pop(s); printf(“%c”,p-data);(2)_ _; /*棧頂元素出棧*/ 14二叉樹(shù)存儲(chǔ)結(jié)構(gòu)同上題，以下程序?yàn)榍蠖鏄?shù)深度的遞歸算法，請(qǐng)?zhí)羁胀晟浦?int depth(bitree bt) /*bt為根結(jié)點(diǎn)的指針*/int hl,hr; if (bt=NULL) return(1)_ _); hl=depth(bt-lchild); hr=depth(bt-rchild); if(2)_ _) (3)_ _； return(hr+1); 15將二叉樹(shù)bt中每一個(gè)結(jié)點(diǎn)的左右子樹(shù)互換的C語(yǔ)言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進(jìn)隊(duì)，出隊(duì)和判別隊(duì)列是否為空的函數(shù)，請(qǐng)?zhí)顚?xiě)算法中得空白處，完成其功能。typedef struct node int data ; struct node *lchild, *rchild; btnode; void EXCHANGE(btnode *bt)btnode *p, *q; if (bt)ADDQ(Q,bt); while(!EMPTY(Q) p=DELQ(Q); q=(1)_ _; p-rchild=(2)_ _; (3)_ _=q;if(p-lchild) (4)_ _; if(p-rchild) (5)_ _; /第六章 樹(shù)和二叉樹(shù)一、單項(xiàng)選擇題1.A2.D3A4C5B6D7E 8. D9C10B11. C12A13D14B15C16B 17. B18. A19C20D21B22. D23C二、判斷題（在各題后填寫(xiě)“”或“”）1. 完全二叉樹(shù)一定存在度為1的結(jié)點(diǎn)。2. 對(duì)于有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，其高度為log2n。3. 二叉樹(shù)的遍歷只是為了在應(yīng)用中找到一種線性次序。4. 一棵一般樹(shù)的結(jié)點(diǎn)的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹(shù)的結(jié)點(diǎn)前序遍歷和后序遍歷是一致的。5. 用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)。6中序遍歷一棵二叉排序樹(shù)的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列 7完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必是樹(shù)葉。8. 二叉樹(shù)只能用二叉鏈表表示。9. 給定一棵樹(shù)，可以找到唯一的一棵二叉樹(shù)與之對(duì)應(yīng)。10. 用鏈表(llink-rlink)存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n-1個(gè)空指針。11樹(shù)形結(jié)構(gòu)中元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系。12將一棵樹(shù)轉(zhuǎn)成二叉樹(shù)，根結(jié)點(diǎn)沒(méi)有左子樹(shù)。13度為二的樹(shù)就是二叉樹(shù)。14. 二叉樹(shù)中序線索化后，不存在空指針域。15霍夫曼樹(shù)的結(jié)點(diǎn)個(gè)數(shù)不能是偶數(shù)。16哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。三、填空題1p-lchild=null & p-rchlid=null 2.(1)2k-1 (2)2k-13644. 2n n-1 n+1 5 先序遍歷 后序遍歷 中序遍歷 6.(1)2k-2+1（第k層1個(gè)結(jié)點(diǎn)，總結(jié)點(diǎn)個(gè)數(shù)是2H-1，其雙親是2H-1/2=2k-2）(2) log2i+1748任何結(jié)點(diǎn)至多只有右子女的二叉樹(shù)。9二叉排序樹(shù)10前序116912 *count