數(shù)據(jù)結(jié)構(gòu)第6章

1、第六章 樹(shù)和二叉樹(shù)一、選擇題1已知一算術(shù)表達(dá)式的中綴形式為 A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為( )A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE【北京航空航天大學(xué) 1999 一、3 （2分)】2算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（ ）【中山大學(xué) 1999 一、5】EFDGAB/+*-C*Aab+cde/* Babcde/+*+ Cabcde/*+ Dabcde*/+3. 設(shè)有一表示算術(shù)表達(dá)式的二叉樹(shù)（見(jiàn)下圖），它所表示的算術(shù)表達(dá)式是（ ）【南京理工大學(xué)1999 一、20（2分）】A. A*B+C/(D

2、*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G4. 設(shè)樹(shù)T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1 則T中的葉子數(shù)為（ ）A5 B6 C7 D8【南京理工大學(xué) 2000 一、8 （1.5分）】5. 在下述結(jié)論中，正確的是（ ）【南京理工大學(xué) 1999 一、4 （1分）】只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0; 二叉樹(shù)的度為2； 二叉樹(shù)的左右子樹(shù)可任意交換;深度為K的完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿(mǎn)二叉樹(shù)。 A B C D6. 設(shè)森林F對(duì)應(yīng)的二叉樹(shù)為B，它有m個(gè)結(jié)點(diǎn)，B的根為p

3、,p的右子樹(shù)結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)是（ ）Am-n Bm-n-1 Cn+1 D條件不足，無(wú)法確定 【南京理工大學(xué)2000 一、17（1.5分）】7. 樹(shù)是結(jié)點(diǎn)的有限集合，它（ (1）)根結(jié)點(diǎn)，記為T(mén)。其余結(jié)點(diǎn)分成為m（m>0）個(gè)(（2）)的集合T1，T2， ，m，每個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn)T稱(chēng)為T(mén)i的父結(jié)點(diǎn)，Ti稱(chēng)為T(mén)的子結(jié)點(diǎn)（1im）。一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的( （3） )。二叉樹(shù)與樹(shù)是兩個(gè)不同的概念，二叉樹(shù)也是結(jié)點(diǎn)的有限集合，它(（4）)根結(jié)點(diǎn)?？梢园褬?shù)的根結(jié)點(diǎn)的層數(shù)定義為1，其他結(jié)點(diǎn)的層數(shù)等于其父結(jié)點(diǎn)所在層數(shù)加上1。令T是一棵二叉樹(shù)，Ki和Kj是T中子結(jié)點(diǎn)

4、數(shù)小于2的結(jié)點(diǎn)中的任意兩個(gè)，它們所在的層數(shù)分別為Ki和Kj，當(dāng)關(guān)系式Ki-Kj1一定成立時(shí)，則稱(chēng)T為一棵（(5)）。供選擇的答案：（1）(4) A. 有0個(gè)或1個(gè) B. 有0個(gè)或多個(gè) C. 有且只有一個(gè) D. 有1個(gè)或1個(gè)以上（2） A. 互不相交 B.允許相交 C.允許葉結(jié)點(diǎn)相交 D.允許樹(shù)枝結(jié)點(diǎn)相交（3） A. 權(quán) B.維數(shù) C.次數(shù) D.序（5） A. 豐滿(mǎn)樹(shù) B.查找樹(shù) C.平衡樹(shù) D.完全樹(shù) 【上海海運(yùn)學(xué)院1999二、2(5分）】8若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（ ）A9 B11 C15 D不確定 【北京工商大學(xué)2001一.7(3分)】9在

5、一棵三元樹(shù)中度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為（ ）個(gè)A4 B5 C6 D7 【哈爾濱工業(yè)大學(xué) 2001 二、2 （2分）】10設(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ù)是（ ）?！颈狈浇煌ù髮W(xué) 2001 一、16 （2分）】AM1 BM1+M2 CM3 DM2+M311具有10個(gè)葉結(jié)點(diǎn)的二叉樹(shù)中有（ ）個(gè)度為2的結(jié)點(diǎn)，【北京航空航天大學(xué)2000 一、5（2分)】A8 B9 C10 Dll12一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ ）【西安交通大學(xué)

6、1996 三、2 (3分)】A 250 B 500 C254 D505 E以上答案都不對(duì) 13. 設(shè)給定權(quán)值總數(shù)有n 個(gè)，其哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為( ) 【福州大學(xué) 1998 一、5 (2分)】A不確定 B2n C2n+1 D2n-114. 有n個(gè)葉子的哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為（ ）?！厩鄭u大學(xué) 2002 二、1 （2分）】A不確定 B2n C2n+1 D2n-115若度為m的哈夫曼樹(shù)中，其葉結(jié)點(diǎn)個(gè)數(shù)為n，則非葉結(jié)點(diǎn)的個(gè)數(shù)為（ ）?！局锌圃河?jì)算所1999一、2（2分）】An-1 Bën/mû-1 Cé(n-1)/(m-1)ù D én/(m-1)&#

7、249;-1 Eé(n+1)/(m+1)ù-116. 有關(guān)二叉樹(shù)下列說(shuō)法正確的是（ ）【南京理工大學(xué) 2000 一、11 （1.5分）】A二叉樹(shù)的度為2 B一棵二叉樹(shù)的度可以小于2 C二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2 D二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為217二叉樹(shù)的第I層上最多含有結(jié)點(diǎn)數(shù)為（ ）【中山大學(xué)1998二、7 （2分）】【北京理工大學(xué) 2001 六、5（2分）】A2I B 2I-1-1 C 2I-1 D2I -118. 一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為（ ）【南京理工大學(xué) 1999 一、19 （2分）】A11 B10 C11至1025之間 D10至1024之間19

8、一棵二叉樹(shù)高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹(shù)最少有( )結(jié)點(diǎn)A2h B2h-1 C2h+1 Dh+1 【南京理工大學(xué)2001一、11(1.5分）】 20對(duì)于有n 個(gè)結(jié)點(diǎn)的二叉樹(shù), 其高度為（ ）【武漢交通科技大學(xué) 1996 一、5 (4分)】Anlog2n Blog2n Cëlog2nû|+1 D不確定21. 一棵具有 n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的樹(shù)高度（深度）是（ ）【南京理工大學(xué) 1996一、8 （2分）】Aëlognû+1 Blogn+1 Cëlognû Dlogn-122深度為h的滿(mǎn)m叉樹(shù)的第k層有（ ）個(gè)結(jié)點(diǎn)。(1

9、=<k=<h)【北京航空航天大學(xué)2000一、4（2分）】Amk-1 Bmk-1 Cmh-1 Dmh-123在一棵高度為k的滿(mǎn)二叉樹(shù)中，結(jié)點(diǎn)總數(shù)為（ ）【北京工商大學(xué) 2001 一、3 (3分)】A2k-1 B2k C2k-1 Dëlog2kû+124高度為 K的二叉樹(shù)最大的結(jié)點(diǎn)數(shù)為（ ）?！旧綎|大學(xué) 2001 二、3 (1分)】A2k B2k-1 C2k -1 D2k-1-125. 一棵樹(shù)高為K的完全二叉樹(shù)至少有（ ）個(gè)結(jié)點(diǎn)【南京理工大學(xué) 1998 一、3 （2分）】A2k 1 B. 2k-1 1 C. 2k-1 D. 2k26. 將有關(guān)二叉樹(shù)的概念推廣到三叉樹(shù)

10、，則一棵有244個(gè)結(jié)點(diǎn)的完全三叉樹(shù)的高度（ ）A4 B5 C6 D7 【南京理工大學(xué)2000一、5 1.5分）】27. 利用二叉鏈表存儲(chǔ)樹(shù)，則根結(jié)點(diǎn)的右指針是（ ）?！厩鄭u大學(xué) 2001 五、5 （2分）】A指向最左孩子 B指向最右孩子 C空 D非空28對(duì)二叉樹(shù)的結(jié)點(diǎn)從1開(kāi)始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用( )次序的遍歷實(shí)現(xiàn)編號(hào)?！颈本├砉ご髮W(xué) 2000 一、4 （2分）】A先序 B. 中序 C. 后序 D. 從根開(kāi)始按層次遍歷29樹(shù)的后根遍歷序列等同于該樹(shù)對(duì)應(yīng)的二叉樹(shù)的( ). 【北京理工大學(xué) 2001

11、六、6 （2分）】A. 先序序列 B. 中序序列 C. 后序序列30若二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左、右子樹(shù)的位置，利用( )遍歷方法最合適。A前序 B中序 C后序 D按層次【北京航空航天大學(xué) 1999 一、4 （2分）】31在下列存儲(chǔ)形式中，哪一個(gè)不是樹(shù)的存儲(chǔ)形式？（ ）【北方交通大學(xué) 2001 一、23 （2分）】A雙親表示法 B孩子鏈表表示法 C孩子兄弟表示法 D順序存儲(chǔ)表示法32一棵二叉樹(shù)的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（ ）【北京工業(yè)大學(xué) 2001 一、2 (2分)】ACABDEFG BABCDEFG CDACEFBG DADCFEG 33已

12、知一棵二叉樹(shù)的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為（ ）。ACBEFDA B FEDCBA C CBEDFA D不定 【浙江大學(xué) 1999 四、2 ( 4分)】34已知某二叉樹(shù)的后序遍歷序列是dabec, 中序遍歷序列是debac , 它的前序遍歷是（ ）。 Aacbed Bdecab Cdeabc Dcedba 【山東大學(xué) 2001 二、7 ( 1分)】35. 某二叉樹(shù)中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E 則前序序列是：AE,G,F,A,C,D,B BE,A,C,B,D,G,F CE,A,G,C,F,B,D D上面的

13、都不對(duì) 【南京理工大學(xué) 2000 一、14 （1.5分）】36. 上題的二叉樹(shù)對(duì)應(yīng)的森林包括多少棵樹(shù)（ ）【南京理工大學(xué) 2000 一、15 （1.5分）】Al B2 C3 D概念上是錯(cuò)誤的 37二叉樹(shù)的先序遍歷和中序遍歷如下： 先序遍歷：EFHIGJK；中序遍歷: HFIEJKG 。該二叉樹(shù)根的右子樹(shù)的根是：【北方交通大學(xué) 2001 一、21（2分）】A、 E B、 F C、 G D、 H 38將一棵樹(shù)t 轉(zhuǎn)換為孩子兄弟鏈表表示的二叉樹(shù)h，則t的后根序遍歷是h 的A前序遍歷 B中序遍歷 C后序遍歷（ ） 【北京郵電大學(xué) 2001 一、2 （2分）】39. 某二叉樹(shù)T有n個(gè)結(jié)點(diǎn)，設(shè)按某種順序?qū)?/p>

14、T中的每個(gè)結(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)為1，2， ，n，且有如下性質(zhì)：T中任一結(jié)點(diǎn)V，其編號(hào)等于左子樹(shù)上的最小編號(hào)減1，而V的右子樹(shù)的結(jié)點(diǎn)中，其最小編號(hào)等于V左子樹(shù)上結(jié)點(diǎn)的最大編號(hào)加1。這時(shí)是按( )編號(hào)的。A.中序遍歷序列 B.前序遍歷序列 C.后序遍歷序列 D.層次順序 【長(zhǎng)沙鐵道學(xué)院1998三、1(2分)】40下面的說(shuō)法中正確的是（ ）.（1）任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在三種遍歷中的相對(duì)次序不變；（2）按二叉樹(shù)定義，具有三個(gè)結(jié)點(diǎn)的二叉樹(shù)共有6種。A(1)(2) B(1) C(2) D(1)、(2)都錯(cuò) 【南京理工大學(xué) 2001 一、10 （1.5分）】41對(duì)于前序遍歷與中序遍歷結(jié)果相同的二叉樹(shù)為（1

15、）;對(duì)于前序遍歷和后序遍歷結(jié)果相同的二叉樹(shù)為（2）?！局锌圃河?jì)算所 1999 一、4 （4分）】A一般二叉樹(shù) B只有根結(jié)點(diǎn)的二叉樹(shù) C根結(jié)點(diǎn)無(wú)左孩子的二叉樹(shù) D根結(jié)點(diǎn)無(wú)右孩子的二叉樹(shù) E所有結(jié)點(diǎn)只有左子數(shù)的二叉樹(shù) F所有結(jié)點(diǎn)只有右子樹(shù)的二叉樹(shù)42一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿(mǎn)足（ ）【南開(kāi)大學(xué) 2000 一、2】A所有的結(jié)點(diǎn)均無(wú)左孩子B所有的結(jié)點(diǎn)均無(wú)右孩子C只有一個(gè)葉子結(jié)點(diǎn)D是任意一棵二叉樹(shù)43在二叉樹(shù)結(jié)點(diǎn)的先序序列，中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（ ）A都不相同B完全相同 C先序和中序相同，而與后序不同 D中序和后序相同，而與先序不同 【

16、北方交通大學(xué) 2001 一、25 （2分）】44某二叉樹(shù)的前序序列和后序序列正好相反，則該二叉樹(shù)一定是（）的二叉樹(shù)?！疚錆h大學(xué)2000二、4】A空或只有一個(gè)結(jié)點(diǎn) B任一結(jié)點(diǎn)無(wú)左子樹(shù) C高度等于其結(jié)點(diǎn)數(shù) D任一結(jié)點(diǎn)無(wú)右子樹(shù)45在完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒(méi)（ ）?！颈狈浇煌ù髮W(xué) 2001 一、22 （2分）】 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)46在下列情況中，可稱(chēng)為二叉樹(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ì) 【西安交通大學(xué) 1996 三、4

17、 (3分)】47. 一棵左子樹(shù)為空的二叉樹(shù)在先序線索化后，其中空的鏈域的個(gè)數(shù)是：( )A不確定 B. 0 C. 1 D. 2 【合肥工業(yè)大學(xué) 1999 一、5 （2分）】48. 一棵左右子樹(shù)均不空的二叉樹(shù)在先序線索化后，其中空的鏈域的個(gè)數(shù)是：( )。A. 0 B. 1 C. 2 D. 不確定 【合肥工業(yè)大學(xué) 2000 一、5 （2分）】49. 若X是二叉中序線索樹(shù)中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則x的前驅(qū)為( ) 【南京理工大學(xué)1996 一、6 (2分)】A.X的雙親 B.X的右子樹(shù)中最左的結(jié)點(diǎn) C.X的左子樹(shù)中最右結(jié)點(diǎn) D.X的左子樹(shù)中最右葉結(jié)點(diǎn)50. 引入二叉線索樹(shù)的目的是（ ）A加快查

18、找結(jié)點(diǎn)的前驅(qū)或后繼的速度 B為了能在二叉樹(shù)中方便的進(jìn)行插入與刪除C為了能方便的找到雙親 D使二叉樹(shù)的遍歷結(jié)果唯一 【南京理工大學(xué)1998 一、5 （2分）】51. 線索二叉樹(shù)是一種（ ）結(jié)構(gòu)。A 邏輯 B 邏輯和存儲(chǔ) C 物理 D線性 【西安電子科技大學(xué)1996 一、9 （2分）】52n個(gè)結(jié)點(diǎn)的線索二叉樹(shù)上含有的線索數(shù)為（ ）A2n Bnl Cnl Dn 【中山大學(xué) 1998 二、8 （2分）】53（ ）的遍歷仍需要棧的支持.A前序線索樹(shù) B中序線索樹(shù) C后序線索樹(shù) 【中科院計(jì)算所 1999 一、1 （2分）】54二叉樹(shù)在線索后，仍不能有效求解的問(wèn)題是（ ）。A前（先）序線索二叉樹(shù)中求前（先）

19、序后繼 B中序線索二叉樹(shù)中求中序后繼C中序線索二叉樹(shù)中求中序前驅(qū) D后序線索二叉樹(shù)中求后序后繼 【武漢大學(xué)2000 二、3 二、5】55. 設(shè)F是一個(gè)森林，B是由F變換得的二叉樹(shù)。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（ ）個(gè)。A n-1 Bn C n+1 D n+2 【西安電子科技大學(xué)1998 一、10 （2分）】56如果T2是由有序樹(shù)T轉(zhuǎn)換而來(lái)的二叉樹(shù)，那么T中結(jié)點(diǎn)的后序就是T2中結(jié)點(diǎn)的（ ）。A先序 B中序 C后序 D層次序 【西安電子科技大學(xué)1996 一、2 （2分）】57. 由3 個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的有向樹(shù)？（ ）A2 B3 C4 D5 【北方交通大學(xué) 2001

20、一、6 （2分）】58由3 個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹(shù)？（ ）A2 B3 C4 D5 【北方交通大學(xué) 2001 一、7 （2分）】59.下述二叉樹(shù)中,哪一種滿(mǎn)足性質(zhì):從任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序列按其關(guān)鍵字有序（）。 A二叉排序樹(shù) B哈夫曼樹(shù) CAVL樹(shù) D堆【中國(guó)科技大學(xué)1998二、8（2分）】【中科院計(jì)算所1998二、8(2分）】60在葉子數(shù)目和權(quán)值相同的所有二叉樹(shù)中，最優(yōu)二叉樹(shù)一定是完全二叉樹(shù)，該說(shuō)法（ ）。 A正確 B錯(cuò)誤 【中國(guó)科技大學(xué)1998 二、10（2分）】【中科院計(jì)算所1998 二、10（2分）】61最優(yōu)二叉樹(shù)（哈夫曼樹(shù)）、最優(yōu)查找樹(shù)均為平均查找路徑長(zhǎng)度最

21、小的樹(shù)，其中對(duì)最優(yōu)二叉樹(shù)，n表示（1），對(duì)最優(yōu)查找樹(shù)，n表示（2），構(gòu)造這兩種樹(shù)均（3）?！局锌圃河?jì)算所1999一、3 (6分）】A結(jié)點(diǎn)數(shù) B葉結(jié)點(diǎn)數(shù) C非葉結(jié)點(diǎn)數(shù) D度為2的結(jié)點(diǎn)數(shù) E需要一張n個(gè)關(guān)鍵字的有序表 F需要對(duì)n個(gè)關(guān)鍵字進(jìn)行動(dòng)態(tài)插入 G需要n個(gè)關(guān)鍵字的查找概率表 H不需要任何前提62下述編碼中哪一個(gè)不是前綴碼（ ）?！局锌圃河?jì)算所 2000 一、2 （2分）】A（00，01，10，11） B（0，1，00，11） C（0，10，110，111） D（1，01，000，001）63下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（ ）。A0,10,110,1111 B11,10,001,1

22、01,0001 C00,010,0110,1000Db,c,aa,ac,aba,abb,abc 【西安電子科技大學(xué)2001 應(yīng)用 一、6（2分）】64. 當(dāng)一棵有n個(gè)結(jié)點(diǎn)的二叉樹(shù)按層次從上到下，同層次從左到右將數(shù)據(jù)存放在一維數(shù)組 Al.n中時(shí)，數(shù)組中第i個(gè)結(jié)點(diǎn)的左孩子為（ ）【南京理工大學(xué) 1999一、18(2分）】AA2i(2i=<n) B. A2i+1(2i+1=< n) CAi/2 D無(wú)法確定65. 一棵有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

23、<=n) BA2i+1(2i+1<=n) CAi-2 D條件不充分，無(wú)法確定【南京理工大學(xué)2000 一、4(1.5分）】66從下列有關(guān)樹(shù)的敘述中,選出5條正確的敘述(共5分) （ ）A二叉樹(shù)中每個(gè)結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn),而樹(shù)無(wú)此限制,因此二叉樹(shù)是樹(shù)的特殊情況。B當(dāng)K1時(shí)高度為K的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)。C用樹(shù)的前序周游和中序周游可以導(dǎo)出樹(shù)的后序周游。D線索二叉樹(shù)的優(yōu)點(diǎn)是便于在中序下查找前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。E將一棵樹(shù)轉(zhuǎn)換成二叉樹(shù)后,根結(jié)點(diǎn)沒(méi)有左子樹(shù)。F一棵含有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù),它的高度是ëLOG2Nû+1。G在二叉樹(shù)中插入結(jié)點(diǎn),該二叉樹(shù)便不再是二叉樹(shù)。H采用二叉

24、樹(shù)鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu),樹(shù)的前序周游和其相應(yīng)的二叉樹(shù)的前序周游的結(jié)果是一樣的。I哈夫曼樹(shù)是帶權(quán)路徑最短的樹(shù),路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。J用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí),總是以前序周游存儲(chǔ)結(jié)點(diǎn)?！旧綎|工業(yè)大學(xué) 1995 三、 (5分)】二、判斷題1. 二叉樹(shù)是度為2的有序樹(shù)。【長(zhǎng)沙鐵道學(xué)院1997一、3(1分)】【中科院軟件所1997一、9(1分)】2. 完全二叉樹(shù)一定存在度為1的結(jié)點(diǎn)?！厩鄭u大學(xué) 2002 一、4 （1分）】3. 對(duì)于有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，其高度為log2n?！旧虾：＿\(yùn)學(xué)院 1998 一、6 （1分）】4深度為K的二叉樹(shù)中結(jié)點(diǎn)總數(shù)2k-1?！灸暇┖娇蘸教齑髮W(xué) 1995 五、1 （1分）

25、】5. 二叉樹(shù)以后序遍歷序列與前序遍歷序列反映的同樣的信息(他們反映的信息不獨(dú)立）?！救A南理工大學(xué)2002一、7 (1分）】6. 二叉樹(shù)的遍歷結(jié)果不是唯一的.【南京理工大學(xué) 1997 二、8 （2分）】7. 二叉樹(shù)的遍歷只是為了在應(yīng)用中找到一種線性次序。【青島大學(xué) 2001 四、4 （1分）】8. 樹(shù)可用投影法進(jìn)行中序遍歷。 【青島大學(xué) 2002 一、6 （1分）】9. 一個(gè)樹(shù)的葉結(jié)點(diǎn)，在前序遍歷和后序遍歷下，皆以相同的相對(duì)位置出現(xiàn)?！旧虾：＿\(yùn)學(xué)院 1995 一、4 （1分）】10. 二叉樹(shù)的前序遍歷并不能唯一確定這棵樹(shù)，但是，如果我們還知道該樹(shù)的根結(jié)點(diǎn)是那一個(gè)，則可以確定這棵二叉樹(shù)。【上海海

26、運(yùn)學(xué)院 1995 一、6 （1分）】11. 一棵一般樹(shù)的結(jié)點(diǎn)的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹(shù)的結(jié)點(diǎn)前序遍歷和后序遍歷是一致的。【上海海運(yùn)學(xué)院 1996 一、6 （1分）】12對(duì)一棵二叉樹(shù)進(jìn)行層次遍歷時(shí)，應(yīng)借助于一個(gè)棧?！灸暇┖娇蘸教齑髮W(xué) 1995 五、3 （1分）】13用樹(shù)的前序遍歷和中序遍歷可以導(dǎo)出樹(shù)的后序遍歷。【北京郵電大學(xué) 1999 二、3 （2分）】14采用二叉鏈表作存儲(chǔ)結(jié)構(gòu)，樹(shù)的前序遍歷和其相應(yīng)的二叉樹(shù)的前序遍歷的結(jié)果是一樣的?！颈本┼]電大學(xué)2000一、2(1分）】15. 用一維數(shù)組存儲(chǔ)二叉樹(shù)時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)?！旧虾：＿\(yùn)學(xué)院 1995 一、8 （1分）】16 中序

27、遍歷二叉鏈存儲(chǔ)的二叉樹(shù)時(shí)，一般要用堆棧；中序遍歷檢索二叉樹(shù)時(shí)，也必須使用堆棧?！旧虾：＿\(yùn)學(xué)院1998一、7(1分）】17中序遍歷一棵二叉排序樹(shù)的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列【中科院軟件所 1999 六、1-1 （2分）】18. 后序線索二叉樹(shù)是不完善的，要對(duì)它進(jìn)行遍歷，還需要使用棧。【 長(zhǎng)沙鐵道學(xué)院 1998 一、2 (1分)】19任何二叉樹(shù)的后序線索樹(shù)進(jìn)行后序遍歷時(shí)都必須用棧?！疚靼步煌ù髮W(xué) 1996 二、2 ( 3分) 】20任何一棵二叉樹(shù)都可以不用棧實(shí)現(xiàn)前序線索樹(shù)的前序遍歷?！疚靼步煌ù髮W(xué) 1996 二、1 (3分)】21由一棵二叉樹(shù)的前序序列和后序序列可以唯一確定它?！局锌圃很浖?1

28、997 一、3 （1分）】22完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必是樹(shù)葉?！緰|南大學(xué) 2001一、1-8（1分）】【中科院軟件所1997一、2（1分）】【山東大學(xué)2001一、4 (1分)】23. 二叉樹(shù)只能用二叉鏈表表示?！灸暇├砉ご髮W(xué) 1997 二、6 （2分）】24. 一棵有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，從上到下，從左到右用自然數(shù)依次給予編號(hào)，則編號(hào)為i的結(jié)點(diǎn)的左兒子的編號(hào)為2i(2i< n)，右兒子是2i+1（2i+1<n）?！灸暇├砉ご髮W(xué) 1997 二、11 （2分）】25. 給定一棵樹(shù)，可以找到唯一的一棵二叉樹(shù)與之對(duì)應(yīng)。【青島大學(xué) 2001 一、5 （1分）】26. 一棵樹(shù)中的

29、葉子數(shù)一定等于與其對(duì)應(yīng)的二叉樹(shù)的葉子數(shù)?！厩鄭u大學(xué) 2002 一、5 （1分）】27. 用鏈表(llink-rlink)存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n-1個(gè)空指針。【上海海運(yùn)學(xué)院1996一.5(1分）】28. 二叉樹(shù)中每個(gè)結(jié)點(diǎn)至多有兩個(gè)子結(jié)點(diǎn),而對(duì)一般樹(shù)則無(wú)此限制.因此,二叉樹(shù)是樹(shù)的特殊情形.【上海海運(yùn)學(xué)院1997一.5(1分）】29樹(shù)形結(jié)構(gòu)中元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系。【燕山大學(xué) 1998 二、1 （2分）】30在二叉樹(shù)的第i層上至少有2i-1個(gè)結(jié)點(diǎn)(i>=1)。【燕山大學(xué) 1998 二、3 （2分）】31必須把一般樹(shù)轉(zhuǎn)換成二叉樹(shù)后才能進(jìn)行存儲(chǔ)?！灸暇┖娇蘸教齑?/p>

30、學(xué) 1997 一、4 （1分）】32完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)通常采用順序存儲(chǔ)結(jié)構(gòu)。【南京航空航天大學(xué) 1996 六、3 （1分）】33將一棵樹(shù)轉(zhuǎn)成二叉樹(shù)，根結(jié)點(diǎn)沒(méi)有左子樹(shù)；【北京郵電大學(xué) 1999 二、2 （2分）】34在二叉樹(shù)中插入結(jié)點(diǎn)，則此二叉樹(shù)便不再是二叉樹(shù)了?！颈本┼]電大學(xué) 2000 一、5 （1分）】35二叉樹(shù)是一般樹(shù)的特殊情形。【北京郵電大學(xué) 2000 一、9 （1分） 2002 一、6 （1分）】36樹(shù)與二叉樹(shù)是兩種不同的樹(shù)型結(jié)構(gòu)。【東南大學(xué) 2001 一、1-7 （1分）】37. 非空的二叉樹(shù)一定滿(mǎn)足：某結(jié)點(diǎn)若有左孩子，則其中序前驅(qū)一定沒(méi)有右孩子【合肥工業(yè)大學(xué) 2001 二、5 （

31、1分）】38在任意一棵非空二叉排序樹(shù)，刪除某結(jié)點(diǎn)后又將其插入，則所得二叉排序樹(shù)與刪除前原二叉排序樹(shù)相同。【中科院軟件所 1997 一、7 （1分）】39度為二的樹(shù)就是二叉樹(shù)。【大連海事大學(xué) 2001 一、7 (1分)】40深度為k具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其編號(hào)最小的結(jié)點(diǎn)序號(hào)為 ë2k-2û+1?！緰|北大學(xué) 1997 二、3 (2分)】41.下面二叉樹(shù)的定義只有一個(gè)是正確的，請(qǐng)?jiān)谡_的地方畫(huà)“”。（1）它是由一個(gè)根和兩株互不相交的、稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。（2）（a）在一株二叉樹(shù)的級(jí)i上，最大結(jié)點(diǎn)數(shù)是2i-1（i1）（b）在一棵深度為k的二叉樹(shù)中，最大結(jié)點(diǎn)數(shù)是2k-

32、1+1（k1）。（3）二叉樹(shù)是結(jié)點(diǎn)的集合，滿(mǎn)足如下條件：（a）它或者是空集；（b）或者是由一個(gè)根和兩個(gè)互不相交的、稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成?！局锌圃鹤詣?dòng)化所1995一、2（6分）】42. 在中序線索二叉樹(shù)中，每一非空的線索均指向其祖先結(jié)點(diǎn)?！竞戏使I(yè)大學(xué) 2000 二、5 （1分）】43. 線索二叉樹(shù)的優(yōu)點(diǎn)是便于是在中序下查找前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)?！旧虾：＿\(yùn)學(xué)院1995 ,96,97 一、7（1分）】44. 二叉樹(shù)中序線索化后，不存在空指針域?！厩鄭u大學(xué) 2000 四、3 （1分）】45霍夫曼樹(shù)的結(jié)點(diǎn)個(gè)數(shù)不能是偶數(shù)。【北京郵電大學(xué) 2000 一、6 （1分）】46. 一棵哈夫曼樹(shù)的帶權(quán)路徑

33、長(zhǎng)度等于其中所有分支結(jié)點(diǎn)的權(quán)值之和?！竞戏使I(yè)大學(xué)2000二、4 (1分)】47. 哈夫曼樹(shù)無(wú)左右子樹(shù)之分?！厩鄭u大學(xué) 2000 四、8 （1分）】48當(dāng)一棵具有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)的WPL值為最小時(shí)，稱(chēng)其樹(shù)為Huffman樹(shù)，且其二叉樹(shù)的形狀必是唯一的。【南京航空航天大學(xué) 1995 五、6 （1分）】49哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近?！颈本┼]電大學(xué) 1999 二、5 （2分）】50. 用鏈表（llink-rlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)時(shí)，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)空指針。( )【上海海運(yùn)學(xué)院 1999 一、6（1分）】三、填空題1二叉樹(shù)由_(1)_

34、，_(2)_，_(3)_三個(gè)基本單元組成?！狙嗌酱髮W(xué) 1998 一、5 （3分）】2樹(shù)在計(jì)算機(jī)內(nèi)的表示方式有_(1)_，_(2)_，_(3)_?！竟枮I工業(yè)大學(xué) 2000 二、4 (3分)】3在二叉樹(shù)中，指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_?！竞戏使I(yè)大學(xué)1999 三、7（2分）】4中綴式a+b*3+4*（c-d）對(duì)應(yīng)的前綴式為_(kāi)(1)_，若a=1，b=2，c=3，d=4，則后綴式db/cc*a-b*+的運(yùn)算結(jié)果為_(kāi)(2)_?！疚髂辖煌ù髮W(xué) 2000 一、6】5二叉樹(shù)中某一結(jié)點(diǎn)左子樹(shù)的深度減去右子樹(shù)的深度稱(chēng)為該結(jié)點(diǎn)的_。【燕山大學(xué)1998一、9(1分)】6具有256個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為_(kāi)。

35、【燕山大學(xué) 1998 一、4 （1分）】7已知一棵度為3的樹(shù)有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹(shù)有_個(gè)葉子結(jié)點(diǎn)?！緩B門(mén)大學(xué) 2000 六、2 （16%/3分）】8深度為k的完全二叉樹(shù)至少有_(1)_個(gè)結(jié)點(diǎn)，至多有_(2)_個(gè)結(jié)點(diǎn)?！緩B門(mén)大學(xué) 2001 一、4 （14%/5分）】 【南京理工大學(xué) 1999 二、5 （4分）】9深度為H 的完全二叉樹(shù)至少有_(1)_個(gè)結(jié)點(diǎn)；至多有_(2)_個(gè)結(jié)點(diǎn)；H和結(jié)點(diǎn)總數(shù)N之間的關(guān)系是 (3)_?！局锌圃河?jì)算所1998 一、3（3分）1999 二、4（3分）】【中國(guó)科技大學(xué) 1998 一、3(4分）】10在順序存儲(chǔ)的二叉樹(shù)中，編號(hào)為i

36、和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是_?！緩B門(mén)大學(xué) 2002 六、3 （4分）】11在完全二叉樹(shù)中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處于同一層的條件是_。【合肥工業(yè)大學(xué) 2000 三、6 （2分）】12一棵有n個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)有_(1)_個(gè)度為1的結(jié)點(diǎn)、有_(2)_個(gè)分支 （非 終端）結(jié)點(diǎn)和_(3)_個(gè)葉子，該滿(mǎn)二叉樹(shù)的深度為_(kāi)(4)_?！救A中理工大學(xué) 2000 一、6 （3分）13假設(shè)根結(jié)點(diǎn)的層數(shù)為，具有個(gè)結(jié)點(diǎn)的二叉樹(shù)的最大高度是_?！颈狈浇煌ù髮W(xué) 2001 二、1】14在一棵二叉樹(shù)中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為N0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為N2,則有N0 =_【北方交通大學(xué) 2001 二、6】【南京理工大學(xué) 19

37、99 二、4 （2分）】15設(shè)只含根結(jié)點(diǎn)的二叉樹(shù)的高度為0，則高度為k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為_(kāi),最小結(jié)點(diǎn)數(shù)為_(kāi)?！颈本┐髮W(xué) 1997 一、1 （4分）】16設(shè)有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)順序存放在向量A1:N中，其下標(biāo)值最大的分支結(jié)點(diǎn)為_(kāi)?！?長(zhǎng)沙鐵道學(xué)院 1997 二、3 (2分)】17高度為K的完全二叉樹(shù)至少有_個(gè)葉子結(jié)點(diǎn)?！竞戏使I(yè)大學(xué) 1999 二、6（2分）】18高度為8的完全二叉樹(shù)至少有_個(gè)葉子結(jié)點(diǎn)。【合肥工業(yè)大學(xué) 2001 三、6（2分）】19已知二叉樹(shù)有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)至少是_?！緩B門(mén)大學(xué) 2002 六、4（4分）】20一個(gè)有2001個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為_(kāi)。

38、【南京理工大學(xué) 1997 三、2（1分）】21設(shè)F是由T1,T2,T3三棵樹(shù)組成的森林,與F對(duì)應(yīng)的二叉樹(shù)為B,已知T1,T2,T3的結(jié)點(diǎn)數(shù)分別為n1,n2和n3則二叉樹(shù)B的左子樹(shù)中有_(1)_個(gè)結(jié)點(diǎn)，右子樹(shù)中有_(2)_個(gè)結(jié)點(diǎn)?！灸暇├砉ご髮W(xué) 2000 二、9（3分）】22一個(gè)深度為k的，具有最少結(jié)點(diǎn)數(shù)的完全二叉樹(shù)按層次，（同層次從左到右）用自然數(shù)依此對(duì)結(jié)點(diǎn)編號(hào)，則編號(hào)最小的葉子的序號(hào)是_(1)_；編號(hào)是i的結(jié)點(diǎn)所在的層次號(hào)是_(2)_（根所在的層次號(hào)規(guī)定為1層）。【南京理工大學(xué) 2001 二、2（2分）】23如某二叉樹(shù)有20個(gè)葉子結(jié)點(diǎn)，有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)為_(kāi)。【南

39、京理工大學(xué) 2001 二、3（2分）】24如果結(jié)點(diǎn)A有 3個(gè)兄弟，而且B是A的雙親，則B的度是_?！疚靼搽娮涌萍即髮W(xué)1999軟件 一、4（2分）】25高度為h的2-3樹(shù)中葉子結(jié)點(diǎn)的數(shù)目至多為_(kāi)?！疚靼搽娮涌萍即髮W(xué)1999軟件 一、6（2分）】26完全二叉樹(shù)中，結(jié)點(diǎn)個(gè)數(shù)為n，則編號(hào)最大的分支結(jié)點(diǎn)的編號(hào)為_(kāi)?！颈本┹p工業(yè)學(xué)院 2000 一、3 (2分)】27設(shè)一棵完全二叉樹(shù)葉子結(jié)點(diǎn)數(shù)為k,最后一層結(jié)點(diǎn)數(shù)>2，則該二叉樹(shù)的高度為_(kāi)?！颈本┛萍即髮W(xué) 1998 一、3】28對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的二元樹(shù)，當(dāng)它為一棵_(1)_二元樹(shù)時(shí)具有最小高度，當(dāng)它為一棵_(2)_時(shí)，具有最大高度?！竟枮I工業(yè)大學(xué)

40、 2001 一、3 (2分)】29具有N個(gè)結(jié)點(diǎn)的二叉樹(shù)，采用二叉鏈表存儲(chǔ)，共有_個(gè)空鏈域?！局貞c大學(xué) 2000 一、8】308層完全二叉樹(shù)至少有_個(gè)結(jié)點(diǎn)，擁有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的最大層數(shù)為_(kāi)?！疚髂辖煌ù髮W(xué) 2000 一、1】31含4個(gè)度為2的結(jié)點(diǎn)和5個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，可有_個(gè)度為1的結(jié)點(diǎn)?！颈本┕I(yè)大學(xué) 2001 一、6 (2分)】32一棵樹(shù)T中，包括一個(gè)度為1的結(jié)點(diǎn)，兩個(gè)度為2的結(jié)點(diǎn)，三個(gè)度為3的結(jié)點(diǎn)，四個(gè)度為4的結(jié)點(diǎn)和若干葉子結(jié)點(diǎn)，則T的葉結(jié)點(diǎn)數(shù)為_(kāi)?！旧綎|大學(xué) 2001 三、2 (2分)】33 n（n大于1）個(gè)結(jié)點(diǎn)的各棵樹(shù)中，其深度最小的那棵樹(shù)的深度是_(1)_。它共有_(2)

41、_個(gè)葉子結(jié)點(diǎn)和_(3)_個(gè)非葉子結(jié)點(diǎn)，其中深度最大的那棵樹(shù)的深度是_(4)_，它共有_(5)_個(gè)葉子結(jié)點(diǎn)和_(6)_個(gè)非葉子結(jié)點(diǎn)?！旧綎|大學(xué) 2001 三、7 (2分)】34 每一棵樹(shù)都能唯一的轉(zhuǎn)換為它所對(duì)應(yīng)的二叉樹(shù)。若已知一棵二叉樹(shù)的前序序列是BEFCGDH，對(duì)稱(chēng)序列是FEBGCHD，則它的后序序列是_(1)_。設(shè)上述二叉樹(shù)是由某棵樹(shù)轉(zhuǎn)換而成，則該樹(shù)的先根次序序列是_(2)_?！旧綎|工業(yè)大學(xué) 1997 二、 (6分)】35先根次序周游樹(shù)林正好等同于按_(1)_周游對(duì)應(yīng)的二叉樹(shù)，后根次序周游樹(shù)林正好等同于按_(2)_周游對(duì)應(yīng)的二叉樹(shù)。【山東工業(yè)大學(xué) 1999 二、1 （4分）】36二叉樹(shù)結(jié)點(diǎn)的

42、對(duì)稱(chēng)序序列為A,B,C,D,E,F,G,后序序列為B,D,C,A,F,G,E,則該二叉樹(shù)結(jié)點(diǎn)的前序序列為_(kāi)(1)_,則該二叉樹(shù)對(duì)應(yīng)的樹(shù)林包括_(2)_棵樹(shù)?！颈本┐髮W(xué) 1997 一、2 （4分）】37二叉樹(shù)的先序序列和中序序列相同的條件是_。 【合肥工業(yè)大學(xué) 2000 三、7（2分）】38已知一棵二叉樹(shù)的前序序列為abdecfhg,中序序列為dbeahfcg，則該二叉樹(shù)的根為_(kāi)(1)_，左子樹(shù)中有_(2)_， 右子樹(shù)中有_(3)_。【南京理工大學(xué) 1996 二、1（6分）】39設(shè)二叉樹(shù)中每個(gè)結(jié)點(diǎn)均用一個(gè)字母表示，若一個(gè)結(jié)點(diǎn)的左子樹(shù)或右子樹(shù)為空，用 表示，現(xiàn)前序遍歷二叉樹(shù)，訪問(wèn)的結(jié)點(diǎn)的序列為AB

43、D.G.CE.H.F，則中序遍歷二叉樹(shù)時(shí)，訪問(wèn)的結(jié)點(diǎn)序列為_(kāi)(1)_;后序遍歷二叉樹(shù)時(shí)，訪問(wèn)的結(jié)點(diǎn)序列為_(kāi)(2)_?！灸暇├砉ご髮W(xué) 1999 二、3（4分）】40已知二叉樹(shù)前序?yàn)锳BDEGCF，中序?yàn)镈BGEACF，則后序一定是_?！厩鄭u大學(xué)2000 六、3(2分）】41現(xiàn)有按中序遍歷二叉樹(shù)的結(jié)果為abc，問(wèn)有_(1)_種不同的二叉樹(shù)可以得到這一遍歷結(jié)果，這些二叉樹(shù)分別是_(2)_?！局袊?guó)礦業(yè)大學(xué) 2000 一、5（3分）】42一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵_樹(shù)而變成一個(gè)有序序列，構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。【西安電子科技大學(xué)1999軟件 一、4（2分）】43利用樹(shù)的孩子兄弟表示法

44、存儲(chǔ)，可以將一棵樹(shù)轉(zhuǎn)換為_(kāi)?！局貞c大學(xué) 2000 一、9】44若一個(gè)二叉樹(shù)的葉子結(jié)點(diǎn)是某子樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的_序列中的最后一個(gè)結(jié)點(diǎn)?！疚錆h大學(xué) 2000 一、2】45先根次序周游樹(shù)林正好等同于按_周游對(duì)應(yīng)的二叉樹(shù)；后根次序周游樹(shù)林正好等同于_周游對(duì)應(yīng)的二叉樹(shù)。【山東大學(xué) 1999 二、 (分)】46. 在一棵存儲(chǔ)結(jié)構(gòu)為三叉鏈表的二叉樹(shù)中，若有一個(gè)結(jié)點(diǎn)是它的雙親的左子女，且它的雙親有右子女，則這個(gè)結(jié)點(diǎn)在后序遍歷中的后繼結(jié)點(diǎn)是_?！局袊?guó)人民大學(xué) 2001 一、4 （2分）】47一棵左子樹(shù)為空的二叉樹(shù)在先序線索化后，其中的空鏈域的個(gè)數(shù)為：_?！緩B門(mén)大學(xué) 2002 六、

45、1 （4分）】48具有n個(gè)結(jié)點(diǎn)的滿(mǎn)二叉樹(shù)，其葉結(jié)點(diǎn)的個(gè)數(shù)是_?！颈本┐髮W(xué) 1994】49設(shè)一棵后序線索樹(shù)的高是50，結(jié)點(diǎn)x是樹(shù)中的一個(gè)結(jié)點(diǎn)，其雙親是結(jié)點(diǎn)y,y的右子樹(shù)高度是31，x是y的左孩子。則確定x的后繼最多需經(jīng)過(guò)_中間結(jié)點(diǎn)（不含后繼及x本身）【南京理工大學(xué) 2000 二、8（1.5分）】50線索二元樹(shù)的左線索指向其_，右線索指向其_。【哈爾濱工業(yè)大學(xué) 2000 二、3 (2分)】51設(shè)y指向二叉線索樹(shù)的一葉子，x指向一待插入結(jié)點(diǎn)，現(xiàn)x作為y的左孩子插入，樹(shù)中標(biāo)志域?yàn)閘tag和rtag，并規(guī)定標(biāo)志為1是線索，則下面的一段算法將x插入并修改相應(yīng)的線索，試補(bǔ)充完整：(lchild,rchild

46、分別代表左，右孩子)x.ltag:= (1)_; x.lchild:= (2)_; y.ltag:= (3)_; y.lchild:= (4)_; x.rtag:= (5)_; x.rchild:= (6)_;IF (x.lchild<>NIL) AND (xlchild.rtag=1) THEN x.lchild.rchild:= (7)_;【南京理工大學(xué) 1997 三、7 （9分）】52哈夫曼樹(shù)是_?！颈本├砉ご髮W(xué) 2001 七、4 （2）】【 長(zhǎng)沙鐵道學(xué)院 1998 二、3 (2分)】53若以4，5，6，7，8作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹(shù)，則其帶權(quán)路徑長(zhǎng)度是_?！疚靼搽娮涌?/p>

47、技大學(xué)2001軟件 一、3 （2分）】【廈門(mén)大學(xué) 2002 六、2（4分）】54有數(shù)據(jù)WG=7，19，2，6，32，3，21，10，則所建Huffman樹(shù)的樹(shù)高是_(1)_，帶權(quán)路徑長(zhǎng)度WPL為_(kāi)(2)_?！灸暇├砉ご髮W(xué) 1999 三、6（4分）】55有一份電文中共使用 6個(gè)字符:a,b,c,d,e,f,它們的出現(xiàn)頻率依次為2,3,4,7,8,9，試構(gòu)造一棵哈夫曼樹(shù)，則其加權(quán)路徑長(zhǎng)度WPL為_(kāi)(1)_，字符c的編碼是_(2)_?！局袊?guó)礦業(yè)大學(xué)2000 一、7（3分）】56設(shè)n0為哈夫曼樹(shù)的葉子結(jié)點(diǎn)數(shù)目，則該哈夫曼樹(shù)共有_個(gè)結(jié)點(diǎn)。【西安電子科技大學(xué)1999軟件 一、2（2分）】57二叉樹(shù)用來(lái)表示

48、表達(dá)式，因?yàn)樾枰４娓髯訕?shù)的值，修改二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)為(Lchild,Data,Val,Rchild)。其中Lchild,Rchild的意義同前，Val用來(lái)存放以該結(jié)點(diǎn)為根的子樹(shù)的值，值的類(lèi)型依具體情況而定。為了簡(jiǎn)便起見(jiàn)，算法假定所考慮的表達(dá)式只有+，-，*，/ 四種二目運(yùn)算，且已表示成相應(yīng)的二叉樹(shù)。算法所計(jì)算的表達(dá)式值放在根結(jié)點(diǎn)的Val域中。PROC Postorder-eval(t:ptrType)BEGIN IF (t!=NULL) BEGIN (1)_; (2)_; CASE t.data: +: t.Val:=t. Lchild. Val + t. Rchild . Val; BRE

49、AK;-: t.Val:=t. Lchild. Val - t. Rchild . Val; BREAK;*: t.Val:=t. Lchild. Val * t. Rchild . Val; BREAK;/: t.Val:=t. Lchild. Val / t. Rchild . Val; BREAK; otherwise: (3)_; BREAK; ENDCASE ENDEND;PROC Delete(x:datatype,A:tree)BEGIN tempA:= (4)_; WHILE (tempA.Item!=x) AND (tempA!=NULL) DO IF (x<tempA

50、.item) BEGIN r:=tempA; tempA:= (5)_; END ELSE BEGIN r:=tempA;tempA:=tempA.Rchild;END;/tempA為要?jiǎng)h結(jié)點(diǎn)，r為tempA的父親 IF (6)_ return(x); IF (tempA.Lchild!=NULL) AND (tempA.rchild!=NULL) BEGIN t:=tempA; q:=tempA.Rchild; WHILE (q.Lchild!=NULL) DO BEGIN t:=q; q:=q.Lchild; END;t.Lchild:= (7)_; /刪去q q.Lchild :=tempA.Lchild; q.Rchild:=tempA.Rchild; IF (tempA.item< r.item) r.Lchild := (8)_ ELSE r.Rchild:=q /用q代替 tempAEND;ELSE IF(tempA.Lchild!=NULL) IF