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

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