[工學(xué)]數(shù)據(jù)結(jié)構(gòu)試題總結(jié)第六章樹(shù)和二叉樹(shù)

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ù)小于或等于深度相同的滿二叉樹(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。其余結(jié)點(diǎn)分成為m（m>0）個(gè)(（2）)的集合t1，t2， ，m，每個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn)t稱為ti的父結(jié)點(diǎn)，ti稱為t的子結(jié)點(diǎn)（1im）。一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)稱為該結(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í)，則稱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. 豐滿樹(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叉樹(shù)的第k層有（ ）個(gè)結(jié)點(diǎn)。(1

9、=<k=<h)【北京航空航天大學(xué)2000一、4（2分）】amk-1 bmk-1 cmh-1 dmh-123在一棵高度為k的滿二叉樹(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ū)

14、中的每個(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ù)一定滿足（ ）【南開(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ù)。【武漢大學(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在下列情況中，可稱為二叉樹(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 一、6

20、 （2分）】58由3 個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹(shù)？（ ）a2 b3 c4 d5 【北方交通大學(xué) 2001 一、7 （2分）】59.下述二叉樹(shù)中,哪一種滿足性質(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)度最小的樹(shù)

21、，其中對(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,101,

22、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采用二叉樹(shù)鏈表

24、作樹(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)。二、判斷題1. 二叉樹(shù)是度為2的有序樹(shù)?！鹃L(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分）】5. 二叉樹(shù)以后序遍歷序列與前序遍歷序列反映的

25、同樣的信息(他們反映的信息不獨(dú)立）。【華南理工大學(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ù)。【上海海運(yùn)學(xué)院 1995 一、6 （1分）】11. 一棵

26、一般樹(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 中序遍歷二叉鏈存儲(chǔ)的二叉樹(shù)時(shí)，一般要用堆棧；中序遍歷

27、檢索二叉樹(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ù)的前序遍歷。【西安交通大學(xué) 1996 二、1 (3分)】21由一棵二叉樹(shù)的前序序列和后序序列可以唯一確定它?！局锌圃很浖?1997 一、3 （1分）】22完全二叉樹(shù)中，若一

28、個(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）。【南京理工大學(xué) 1997 二、11 （2分）】25. 給定一棵樹(shù)，可以找到唯一的一棵二叉樹(shù)與之對(duì)應(yīng)?！厩鄭u大學(xué) 2001 一、5 （1分）】26. 一棵樹(shù)中的葉子數(shù)一定等于與其對(duì)應(yīng)的二叉樹(shù)的葉子數(shù)。【青島大

29、學(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ǔ)?！灸暇┖娇蘸教齑髮W(xué) 1997 一、4 （1分）】32完全二叉樹(shù)的

30、存儲(chǔ)結(jié)構(gòu)通常采用順序存儲(chǔ)結(jié)構(gòu)?！灸暇┖娇蘸教齑髮W(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ù)一定滿足：某結(jié)點(diǎn)若有左孩子，則其中序前驅(qū)一定沒(méi)有右孩子【合肥工業(yè)大學(xué) 2001 二、5 （1分）】38在任意一棵非空二叉排序樹(shù)，刪除某結(jié)點(diǎn)

31、后又將其插入，則所得二叉排序樹(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è)根和兩株互不相交的、稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。（2）（a）在一株二叉樹(shù)的級(jí)i上，最大結(jié)點(diǎn)數(shù)是2i-1（i1）（b）在一棵深度為k的二叉樹(shù)中，最大結(jié)點(diǎn)數(shù)是2k-1+1（k1）。（3）二叉樹(shù)是結(jié)點(diǎn)的集合，滿足如

32、下條件：（a）它或者是空集；（b）或者是由一個(gè)根和兩個(gè)互不相交的、稱為左子樹(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)路徑長(zhǎng)度等于其中所有分支結(jié)點(diǎn)的權(quán)值之和?！竞戏使I(yè)大

33、學(xué)2000二、4 (1分)】47. 哈夫曼樹(shù)無(wú)左右子樹(shù)之分。【青島大學(xué) 2000 四、8 （1分）】48當(dāng)一棵具有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)的wpl值為最小時(shí)，稱其樹(shù)為huffman樹(shù)，且其二叉樹(shù)的形狀必是唯一的?！灸暇┖娇蘸教齑髮W(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)_，_(2)_，_(3)_三個(gè)基本單元組成?！狙嗌?/p>

34、大學(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ù)的深度稱為該結(jié)點(diǎn)的_?！狙嗌酱髮W(xué)1998一、9(1分)】6具有256個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為_(kāi)?！狙嗌酱髮W(xué) 1998 一、4 （1分）】7已知一

35、棵度為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門大學(xué) 2000 六、2 （16%/3分）】8深度為k的完全二叉樹(shù)至少有_(1)_個(gè)結(jié)點(diǎn)，至多有_(2)_個(gè)結(jié)點(diǎn)?！緩B門大學(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和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是_?！緩B門大學(xué)

36、2002 六、3 （4分）】11在完全二叉樹(shù)中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處于同一層的條件是_?！竞戏使I(yè)大學(xué) 2000 三、6 （2分）】12一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)有_(1)_個(gè)度為1的結(jié)點(diǎn)、有_(2)_個(gè)分支 （非 終端）結(jié)點(diǎn)和_(3)_個(gè)葉子，該滿二叉樹(shù)的深度為_(kāi)(4)_。【華中理工大學(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é) 1999 二、4 （2分）】15設(shè)只含根結(jié)點(diǎn)的二叉樹(shù)

37、的高度為0，則高度為k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為_(kāi),最小結(jié)點(diǎn)數(shù)為_(kāi)。【北京大學(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)。【合肥工業(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ù)至少是_。【廈門大學(xué) 2002 六、4（4分）】20一個(gè)有2001個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為_(kāi)?！灸暇├砉ご髮W(xué) 1997 三、2（1分）】21設(shè)

38、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層）?！灸暇├砉ご髮W(xué) 2001 二、2（2分）】23如某二叉樹(shù)有20個(gè)葉子結(jié)點(diǎn)，有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)為_(kāi)?！灸暇├砉ご髮W(xué) 2001 二、3（2分）】24如果結(jié)

39、點(diǎn)a有 3個(gè)兄弟，而且b是a的雙親，則b的度是_。【西安電子科技大學(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é) 2001 一、3 (2分)】29具有n個(gè)結(jié)點(diǎn)的

40、二叉樹(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)_個(gè)葉子結(jié)點(diǎn)和_(3)_個(gè)非葉子結(jié)點(diǎn)，其中深度最

41、大的那棵樹(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ì)稱序列是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)的對(duì)稱序序列為a,b,c,d,e,f,g,后序序列

42、為b,d,c,a,f,g,e,則該二叉樹(shù)結(jié)點(diǎn)的前序序列為_(kāi)(1)_,則該二叉樹(shù)對(duì)應(yīng)的樹(shù)林包括_(2)_棵樹(shù)。【北京大學(xué) 1997 一、2 （4分）】37二叉樹(shù)的先序序列和中序序列相同的條件是_?！竞戏使I(yè)大學(xué) 2000 三、7（2分）】38已知一棵二叉樹(shù)的前序序列為abdecfhg,中序序列為dbeahfcg，則該二叉樹(shù)的根為_(kāi)(1)_，左子樹(shù)中有_(2)_， 右子樹(shù)中有_(3)_?！灸暇├砉ご髮W(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)的序列為abd.g.ce.h.f，則中序遍歷二叉樹(shù)時(shí)，訪問(wèn)的結(jié)

43、點(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ù)的孩子兄弟表示法存儲(chǔ)，可以將一棵樹(shù)轉(zhuǎn)換為_(kāi)?！局貞c大學(xué) 2000

44、一、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ù)為：_。【廈門大學(xué) 2002 六、1 （4分）】48具有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)，其葉結(jié)點(diǎn)

45、的個(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ù)的左線索指向其_，右線索指向其_?！竟枮I工業(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分別代表左，右孩子)x.ltag:= (1)_;

46、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ù)是_。【北京理工大學(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)度是_?！疚靼搽娮涌萍即髮W(xué)2001軟件 一、3 （2分）】【廈門大學(xué)

47、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)?！疚靼搽娮涌萍即髮W(xué)1999軟件 一、2（2分）】57二叉樹(shù)用來(lái)表示表達(dá)式，因?yàn)樾枰４娓髯訕?shù)的值，修改二叉樹(shù)的結(jié)點(diǎn)結(jié)

48、構(gòu)為(lchild,data,val,rchild)。其中l(wèi)child,rchild的意義同前，val用來(lái)存放以該結(jié)點(diǎn)為根的子樹(shù)的值，值的類型依具體情況而定。為了簡(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; break;-: t.val:=t. lchild. v

49、al - 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.item) begin r:=tempa; te

50、mpa:= (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) i