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

第六章 樹和二叉樹一、選擇題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ù)表達(dá)式是（ ）【南京理工大學(xué)1999 一、20（2分）】A. A*B+C/(D*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è)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1 則T中的葉子數(shù)為（ ）A5 B6 C7 D8【南京理工大學(xué) 2000 一、8 （1.5分）】5. 在下述結(jié)論中，正確的是（ ）【南京理工大學(xué) 1999 一、4 （1分）】只有一個結(jié)點的二叉樹的度為0; 二叉樹的度為2； 二叉樹的左右子樹可任意交換;深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。 A B C D6. 設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點個數(shù)是（ ）Am-n Bm-n-1 Cn+1 D條件不足，無法確定 【南京理工大學(xué)2000 一、17（1.5分）】7. 樹是結(jié)點的有限集合，它（ (1）)根結(jié)點，記為T。其余結(jié)點分成為m（m0）個(（2）)的集合T1，T2， ，m，每個集合又都是樹，此時結(jié)點T稱為Ti的父結(jié)點，Ti稱為T的子結(jié)點（1im）。一個結(jié)點的子結(jié)點個數(shù)稱為該結(jié)點的( （3） )。二叉樹與樹是兩個不同的概念，二叉樹也是結(jié)點的有限集合，它(（4）)根結(jié)點?？梢园褬涞母Y(jié)點的層數(shù)定義為1，其他結(jié)點的層數(shù)等于其父結(jié)點所在層數(shù)加上1。令T是一棵二叉樹，Ki和Kj是T中子結(jié)點數(shù)小于2的結(jié)點中的任意兩個，它們所在的層數(shù)分別為Ki和Kj，當(dāng)關(guān)系式Ki-Kj1一定成立時，則稱T為一棵（(5)）。供選擇的答案：（1）(4) A. 有0個或1個 B. 有0個或多個 C. 有且只有一個 D. 有1個或1個以上（2） A. 互不相交 B.允許相交 C.允許葉結(jié)點相交 D.允許樹枝結(jié)點相交（3） A. 權(quán) B.維數(shù) C.次數(shù) D.序（5） A. 豐滿樹 B.查找樹 C.平衡樹 D.完全樹 【上海海運學(xué)院1999二、2(5分）】8若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（ ）A9 B11 C15 D不確定 【北京工商大學(xué)2001一.7(3分)】9在一棵三元樹中度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為（ ）個A4 B5 C6 D7 【哈爾濱工業(yè)大學(xué) 2001 二、2 （2分）】10設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（ ）?！颈狈浇煌ù髮W(xué) 2001 一、16 （2分）】AM1 BM1+M2 CM3 DM2+M311具有10個葉結(jié)點的二叉樹中有（ ）個度為2的結(jié)點，【北京航空航天大學(xué)2000 一、5（2分)】A8 B9 C10 Dll12一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（ ）【西安交通大學(xué) 1996 三、2 (3分)】A 250 B 500 C254 D505 E以上答案都不對 13. 設(shè)給定權(quán)值總數(shù)有n 個，其哈夫曼樹的結(jié)點總數(shù)為( ) 【福州大學(xué) 1998 一、5 (2分)】A不確定 B2n C2n+1 D2n-114. 有n個葉子的哈夫曼樹的結(jié)點總數(shù)為（ ）?！厩鄭u大學(xué) 2002 二、1 （2分）】A不確定 B2n C2n+1 D2n-115若度為m的哈夫曼樹中，其葉結(jié)點個數(shù)為n，則非葉結(jié)點的個數(shù)為（ ）。【中科院計算所1999一、2（2分）】An-1 Bn/m-1 C(n-1)/(m-1) D n/(m-1)-1 E(n+1)/(m+1)-116. 有關(guān)二叉樹下列說法正確的是（ ）【南京理工大學(xué) 2000 一、11 （1.5分）】A二叉樹的度為2 B一棵二叉樹的度可以小于2 C二叉樹中至少有一個結(jié)點的度為2 D二叉樹中任何一個結(jié)點的度都為217二叉樹的第I層上最多含有結(jié)點數(shù)為（ ）【中山大學(xué)1998二、7 （2分）】【北京理工大學(xué) 2001 六、5（2分）】A2I B 2I-1-1 C 2I-1 D2I -118. 一個具有1025個結(jié)點的二叉樹的高h(yuǎn)為（ ）【南京理工大學(xué) 1999 一、19 （2分）】A11 B10 C11至1025之間 D10至1024之間19一棵二叉樹高度為h,所有結(jié)點的度或為0，或為2，則這棵二叉樹最少有( )結(jié)點A2h B2h-1 C2h+1 Dh+1 【南京理工大學(xué)2001一、11(1.5分）】 20對于有n 個結(jié)點的二叉樹, 其高度為（ ）【武漢交通科技大學(xué) 1996 一、5 (4分)】Anlog2n Blog2n Clog2n|+1 D不確定21. 一棵具有 n個結(jié)點的完全二叉樹的樹高度（深度）是（ ）【南京理工大學(xué) 1996一、8 （2分）】Alogn+1 Blogn+1 Clogn Dlogn-122深度為h的滿m叉樹的第k層有（ ）個結(jié)點。(1=k=h)【北京航空航天大學(xué)2000一、4（2分）】Amk-1 Bmk-1 Cmh-1 Dmh-123在一棵高度為k的滿二叉樹中，結(jié)點總數(shù)為（ ）【北京工商大學(xué) 2001 一、3 (3分)】A2k-1 B2k C2k-1 Dlog2k+124高度為 K的二叉樹最大的結(jié)點數(shù)為（ ）。【山東大學(xué) 2001 二、3 (1分)】A2k B2k-1 C2k -1 D2k-1-125. 一棵樹高為K的完全二叉樹至少有（ ）個結(jié)點【南京理工大學(xué) 1998 一、3 （2分）】A2k 1 B. 2k-1 1 C. 2k-1 D. 2k26. 將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度（）A4 B5 C6 D7 【南京理工大學(xué)2000一、5 1.5分）】27. 利用二叉鏈表存儲樹，則根結(jié)點的右指針是（ ）。【青島大學(xué) 2001 五、5 （2分）】A指向最左孩子 B指向最右孩子 C空 D非空28對二叉樹的結(jié)點從1開始進(jìn)行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用( )次序的遍歷實現(xiàn)編號?！颈本├砉ご髮W(xué) 2000 一、4 （2分）】A先序 B. 中序 C. 后序 D. 從根開始按層次遍歷29樹的后根遍歷序列等同于該樹對應(yīng)的二叉樹的( ). 【北京理工大學(xué) 2001 六、6 （2分）】A. 先序序列 B. 中序序列 C. 后序序列30若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利用( )遍歷方法最合適。A前序 B中序 C后序 D按層次【北京航空航天大學(xué) 1999 一、4 （2分）】31在下列存儲形式中，哪一個不是樹的存儲形式？（ ）【北方交通大學(xué) 2001 一、23 （2分）】A雙親表示法 B孩子鏈表表示法 C孩子兄弟表示法 D順序存儲表示法32一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（ ）【北京工業(yè)大學(xué) 2001 一、2 (2分)】ACABDEFG BABCDEFG CDACEFBG DADCFEG 33已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為（ ）。ACBEFDA B FEDCBA C CBEDFA D不定 【浙江大學(xué) 1999 四、2 ( 4分)】34已知某二叉樹的后序遍歷序列是dabec, 中序遍歷序列是debac , 它的前序遍歷是（ ）。 Aacbed Bdecab Cdeabc Dcedba 【山東大學(xué) 2001 二、7 ( 1分)】35. 某二叉樹中序序列為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上面的都不對 【南京理工大學(xué) 2000 一、14 （1.5分）】36. 上題的二叉樹對應(yīng)的森林包括多少棵樹（ ）【南京理工大學(xué) 2000 一、15 （1.5分）】Al B2 C3 D概念上是錯誤的 37二叉樹的先序遍歷和中序遍歷如下： 先序遍歷：EFHIGJK；中序遍歷: HFIEJKG 。該二叉樹根的右子樹的根是：【北方交通大學(xué) 2001 一、21（2分）】A、 E B、 F C、 G D、 H 38將一棵樹t 轉(zhuǎn)換為孩子兄弟鏈表表示的二叉樹h，則t的后根序遍歷是h 的A前序遍歷 B中序遍歷 C后序遍歷（ ） 【北京郵電大學(xué) 2001 一、2 （2分）】39. 某二叉樹T有n個結(jié)點，設(shè)按某種順序?qū)中的每個結(jié)點進(jìn)行編號，編號為1，2， ，n，且有如下性質(zhì)：T中任一結(jié)點V，其編號等于左子樹上的最小編號減1，而V的右子樹的結(jié)點中，其最小編號等于V左子樹上結(jié)點的最大編號加1。這時是按( )編號的。A.中序遍歷序列 B.前序遍歷序列 C.后序遍歷序列 D.層次順序 【長沙鐵道學(xué)院1998三、1(2分)】40下面的說法中正確的是（ ）.（1）任何一棵二叉樹的葉子結(jié)點在三種遍歷中的相對次序不變；（2）按二叉樹定義，具有三個結(jié)點的二叉樹共有6種。A(1)(2) B(1) C(2) D(1)、(2)都錯 【南京理工大學(xué) 2001 一、10 （1.5分）】41對于前序遍歷與中序遍歷結(jié)果相同的二叉樹為（1）;對于前序遍歷和后序遍歷結(jié)果相同的二叉樹為（2）?！局锌圃河嬎闼?1999 一、4 （4分）】A一般二叉樹 B只有根結(jié)點的二叉樹 C根結(jié)點無左孩子的二叉樹 D根結(jié)點無右孩子的二叉樹 E所有結(jié)點只有左子數(shù)的二叉樹 F所有結(jié)點只有右子樹的二叉樹42一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（ ）【南開大學(xué) 2000 一、2】A所有的結(jié)點均無左孩子B所有的結(jié)點均無右孩子C只有一個葉子結(jié)點D是任意一棵二叉樹43在二叉樹結(jié)點的先序序列，中序序列和后序序列中，所有葉子結(jié)點的先后順序（ ）A都不相同B完全相同 C先序和中序相同，而與后序不同 D中序和后序相同，而與先序不同 【北方交通大學(xué) 2001 一、25 （2分）】44某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。【武漢大學(xué)2000二、4】A空或只有一個結(jié)點 B任一結(jié)點無左子樹 C高度等于其結(jié)點數(shù) D任一結(jié)點無右子樹45在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒（ ）?！颈狈浇煌ù髮W(xué) 2001 一、22 （2分）】 A左子結(jié)點 B右子結(jié)點 C左子結(jié)點和右子結(jié)點 D左子結(jié)點，右子結(jié)點和兄弟結(jié)點46在下列情況中，可稱為二叉樹的是（ ） A每個結(jié)點至多有兩棵子樹的樹 B. 哈夫曼樹 C每個結(jié)點至多有兩棵子樹的有序樹 D. 每個結(jié)點只有一棵右子樹 E以上答案都不對 【西安交通大學(xué) 1996 三、4 (3分)】47. 一棵左子樹為空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：( )A不確定 B. 0 C. 1 D. 2 【合肥工業(yè)大學(xué) 1999 一、5 （2分）】48. 一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：( )。A. 0 B. 1 C. 2 D. 不確定 【合肥工業(yè)大學(xué) 2000 一、5 （2分）】49. 若X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，則x的前驅(qū)為( ) 【南京理工大學(xué)1996 一、6 (2分)】A.X的雙親 B.X的右子樹中最左的結(jié)點 C.X的左子樹中最右結(jié)點 D.X的左子樹中最右葉結(jié)點50. 引入二叉線索樹的目的是（ ）A加快查找結(jié)點的前驅(qū)或后繼的速度 B為了能在二叉樹中方便的進(jìn)行插入與刪除C為了能方便的找到雙親 D使二叉樹的遍歷結(jié)果唯一【南京理工大學(xué)1998 一、5 （2分）】51. 線索二叉樹是一種（ ）結(jié)構(gòu)。A 邏輯 B 邏輯和存儲 C 物理 D線性【西安電子科技大學(xué)1996 一、9 （2分）】52n個結(jié)點的線索二叉樹上含有的線索數(shù)為（ ）A2n Bnl Cnl Dn 【中山大學(xué) 1998 二、8 （2分）】53（ ）的遍歷仍需要棧的支持.A前序線索樹 B中序線索樹 C后序線索樹 【中科院計算所 1999 一、1 （2分）】54二叉樹在線索后，仍不能有效求解的問題是（ ）。A前（先）序線索二叉樹中求前（先）序后繼 B中序線索二叉樹中求中序后繼C中序線索二叉樹中求中序前驅(qū) D后序線索二叉樹中求后序后繼 【武漢大學(xué)2000 二、3 二、5】55. 設(shè)F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有（ ）個。A n-1 Bn C n+1 D n+2 【西安電子科技大學(xué)1998 一、10 （2分）】56如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的后序就是T2中結(jié)點的（ ）。A先序 B中序 C后序 D層次序 【西安電子科技大學(xué)1996 一、2 （2分）】57. 由3 個結(jié)點可以構(gòu)造出多少種不同的有向樹？（ ）A2 B3 C4 D5 【北方交通大學(xué) 2001 一、6 （2分）】58由3 個結(jié)點可以構(gòu)造出多少種不同的二叉樹？（ ）A2 B3 C4 D5 【北方交通大學(xué) 2001 一、7 （2分）】59.下述二叉樹中,哪一種滿足性質(zhì):從任一結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字有序（）。 A二叉排序樹 B哈夫曼樹 CAVL樹 D堆【中國科技大學(xué)1998二、8（2分）】【中科院計算所1998二、8(2分）】60在葉子數(shù)目和權(quán)值相同的所有二叉樹中，最優(yōu)二叉樹一定是完全二叉樹，該說法（ ）。 A正確 B錯誤 【中國科技大學(xué)1998 二、10（2分）】【中科院計算所1998 二、10（2分）】61最優(yōu)二叉樹（哈夫曼樹）、最優(yōu)查找樹均為平均查找路徑長度最小的樹，其中對最優(yōu)二叉樹，n表示（1），對最優(yōu)查找樹，n表示（2），構(gòu)造這兩種樹均（3）。【中科院計算所1999一、3 (6分）】A結(jié)點數(shù) B葉結(jié)點數(shù) C非葉結(jié)點數(shù) D度為2的結(jié)點數(shù) E需要一張n個關(guān)鍵字的有序表 F需要對n個關(guān)鍵字進(jìn)行動態(tài)插入 G需要n個關(guān)鍵字的查找概率表 H不需要任何前提62下述編碼中哪一個不是前綴碼（ ）?！局锌圃河嬎闼?2000 一、2 （2分）】A（00，01，10，11） B（0，1，00，11） C（0，10，110，111） D（1，01，000，001）63下面幾個符號串編碼集合中，不是前綴編碼的是（ ）。A0,10,110,1111 B11,10,001,101,0001 C00,010,0110,1000Db,c,aa,ac,aba,abb,abc 【西安電子科技大學(xué)2001 應(yīng)用 一、6（2分）】64. 當(dāng)一棵有n個結(jié)點的二叉樹按層次從上到下，同層次從左到右將數(shù)據(jù)存放在一維數(shù)組 Al.n中時，數(shù)組中第i個結(jié)點的左孩子為（ ）【南京理工大學(xué) 1999一、18(2分）】AA2i(2i=n) B. A2i+1(2i+1= n) CAi/2 D無法確定65. 一棵有n個結(jié)點的二叉樹，按層次從上到下，同一層從左到右順序存儲在一維數(shù)組A1.n中，則二叉樹中第i個結(jié)點（i從1開始用上述方法編號）的右孩子在數(shù)組A中的位置是（ ）AA2i(2i=n) BA2i+1(2i+1=n) CAi-2 D條件不充分，無法確定【南京理工大學(xué)2000 一、4(1.5分）】66從下列有關(guān)樹的敘述中,選出5條正確的敘述(共5分) （ ）A二叉樹中每個結(jié)點有兩個子結(jié)點,而樹無此限制,因此二叉樹是樹的特殊情況。B當(dāng)K1時高度為K的二叉樹至多有2k-1個結(jié)點。C用樹的前序周游和中序周游可以導(dǎo)出樹的后序周游。D線索二叉樹的優(yōu)點是便于在中序下查找前驅(qū)結(jié)點和后繼結(jié)點。E將一棵樹轉(zhuǎn)換成二叉樹后,根結(jié)點沒有左子樹。F一棵含有N個結(jié)點的完全二叉樹,它的高度是LOG2N+1。G在二叉樹中插入結(jié)點,該二叉樹便不再是二叉樹。H采用二叉樹鏈表作樹的存儲結(jié)構(gòu),樹的前序周游和其相應(yīng)的二叉樹的前序周游的結(jié)果是一樣的。I哈夫曼樹是帶權(quán)路徑最短的樹,路徑上權(quán)值較大的結(jié)點離根較近。J用一維數(shù)組存儲二叉樹時,總是以前序周游存儲結(jié)點?！旧綎|工業(yè)大學(xué) 1995 三、 (5分)】二、判斷題1. 二叉樹是度為2的有序樹?！鹃L沙鐵道學(xué)院1997一、3(1分)】【中科院軟件所1997一、9(1分)】2. 完全二叉樹一定存在度為1的結(jié)點?！厩鄭u大學(xué) 2002 一、4 （1分）】3. 對于有N個結(jié)點的二叉樹，其高度為log2n?！旧虾：＿\學(xué)院 1998 一、6 （1分）】4深度為K的二叉樹中結(jié)點總數(shù)2k-1。【南京航空航天大學(xué) 1995 五、1 （1分）】5. 二叉樹以后序遍歷序列與前序遍歷序列反映的同樣的信息(他們反映的信息不獨立）?！救A南理工大學(xué)2002一、7 (1分）】6. 二叉樹的遍歷結(jié)果不是唯一的.【南京理工大學(xué) 1997 二、8 （2分）】7. 二叉樹的遍歷只是為了在應(yīng)用中找到一種線性次序?！厩鄭u大學(xué) 2001 四、4 （1分）】8. 樹可用投影法進(jìn)行中序遍歷。 【青島大學(xué) 2002 一、6 （1分）】9. 一個樹的葉結(jié)點，在前序遍歷和后序遍歷下，皆以相同的相對位置出現(xiàn)?！旧虾：＿\學(xué)院 1995 一、4 （1分）】10. 二叉樹的前序遍歷并不能唯一確定這棵樹，但是，如果我們還知道該樹的根結(jié)點是那一個，則可以確定這棵二叉樹?！旧虾：＿\學(xué)院 1995 一、6 （1分）】11. 一棵一般樹的結(jié)點的前序遍歷和后序遍歷分別與它相應(yīng)二叉樹的結(jié)點前序遍歷和后序遍歷是一致的?！旧虾：＿\學(xué)院 1996 一、6 （1分）】12對一棵二叉樹進(jìn)行層次遍歷時，應(yīng)借助于一個棧。【南京航空航天大學(xué) 1995 五、3 （1分）】13用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的后序遍歷?！颈本┼]電大學(xué) 1999 二、3 （2分）】14采用二叉鏈表作存儲結(jié)構(gòu)，樹的前序遍歷和其相應(yīng)的二叉樹的前序遍歷的結(jié)果是一樣的。【北京郵電大學(xué)2000一、2(1分）】15. 用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結(jié)點。【上海海運學(xué)院 1995 一、8 （1分）】16 中序遍歷二叉鏈存儲的二叉樹時，一般要用堆棧；中序遍歷檢索二叉樹時，也必須使用堆棧?！旧虾：＿\學(xué)院1998一、7(1分）】17中序遍歷一棵二叉排序樹的結(jié)點就可得到排好序的結(jié)點序列【中科院軟件所 1999 六、1-1 （2分）】18. 后序線索二叉樹是不完善的，要對它進(jìn)行遍歷，還需要使用棧?！?長沙鐵道學(xué)院 1998 一、2 (1分)】19任何二叉樹的后序線索樹進(jìn)行后序遍歷時都必須用棧。【西安交通大學(xué) 1996 二、2 ( 3分) 】20任何一棵二叉樹都可以不用棧實現(xiàn)前序線索樹的前序遍歷?！疚靼步煌ù髮W(xué) 1996 二、1 (3分)】21由一棵二叉樹的前序序列和后序序列可以唯一確定它。【中科院軟件所 1997 一、3 （1分）】22完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是樹葉?！緰|南大學(xué) 2001一、1-8（1分）】【中科院軟件所1997一、2（1分）】【山東大學(xué)2001一、4 (1分)】23. 二叉樹只能用二叉鏈表表示。【南京理工大學(xué) 1997 二、6 （2分）】24. 一棵有n個結(jié)點的二叉樹，從上到下，從左到右用自然數(shù)依次給予編號，則編號為i的結(jié)點的左兒子的編號為2i(2i n)，右兒子是2i+1（2i+1=1)?！狙嗌酱髮W(xué) 1998 二、3 （2分）】31必須把一般樹轉(zhuǎn)換成二叉樹后才能進(jìn)行存儲?！灸暇┖娇蘸教齑髮W(xué) 1997 一、4 （1分）】32完全二叉樹的存儲結(jié)構(gòu)通常采用順序存儲結(jié)構(gòu)。【南京航空航天大學(xué) 1996 六、3 （1分）】33將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點沒有左子樹；【北京郵電大學(xué) 1999 二、2 （2分）】34在二叉樹中插入結(jié)點，則此二叉樹便不再是二叉樹了?！颈本┼]電大學(xué) 2000 一、5 （1分）】35二叉樹是一般樹的特殊情形?！颈本┼]電大學(xué) 2000 一、9 （1分） 2002 一、6 （1分）】36樹與二叉樹是兩種不同的樹型結(jié)構(gòu)。【東南大學(xué) 2001 一、1-7 （1分）】37. 非空的二叉樹一定滿足：某結(jié)點若有左孩子，則其中序前驅(qū)一定沒有右孩子【合肥工業(yè)大學(xué) 2001 二、5 （1分）】38在任意一棵非空二叉排序樹，刪除某結(jié)點后又將其插入，則所得二叉排序樹與刪除前原二叉排序樹相同?！局锌圃很浖?1997 一、7 （1分）】39度為二的樹就是二叉樹?！敬筮B海事大學(xué) 2001 一、7 (1分)】40深度為k具有n個結(jié)點的完全二叉樹，其編號最小的結(jié)點序號為 2k-2+1?！緰|北大學(xué) 1997 二、3 (2分)】41.下面二叉樹的定義只有一個是正確的，請在正確的地方畫“”。（1）它是由一個根和兩株互不相交的、稱為左子樹和右子樹的二叉樹組成。（2）（a）在一株二叉樹的級i上，最大結(jié)點數(shù)是2i-1（i1）（b）在一棵深度為k的二叉樹中，最大結(jié)點數(shù)是2k-1+1（k1）。（3）二叉樹是結(jié)點的集合，滿足如下條件：（a）它或者是空集；（b）或者是由一個根和兩個互不相交的、稱為左子樹和右子樹的二叉樹組成。【中科院自動化所1995一、2（6分）】42. 在中序線索二叉樹中，每一非空的線索均指向其祖先結(jié)點?！竞戏使I(yè)大學(xué) 2000 二、5 （1分）】43. 線索二叉樹的優(yōu)點是便于是在中序下查找前驅(qū)結(jié)點和后繼結(jié)點?！旧虾：＿\學(xué)院1995 ,96,97 一、7（1分）】44. 二叉樹中序線索化后，不存在空指針域?！厩鄭u大學(xué) 2000 四、3 （1分）】45霍夫曼樹的結(jié)點個數(shù)不能是偶數(shù)。【北京郵電大學(xué) 2000 一、6 （1分）】46. 一棵哈夫曼樹的帶權(quán)路徑長度等于其中所有分支結(jié)點的權(quán)值之和。【合肥工業(yè)大學(xué)2000二、4 (1分)】47. 哈夫曼樹無左右子樹之分?！厩鄭u大學(xué) 2000 四、8 （1分）】48當(dāng)一棵具有n個葉子結(jié)點的二叉樹的WPL值為最小時，稱其樹為Huffman樹，且其二叉樹的形狀必是唯一的。【南京航空航天大學(xué) 1995 五、6 （1分）】49哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近?！颈本┼]電大學(xué) 1999 二、5 （2分）】50. 用鏈表（llink-rlink）存儲包含n個結(jié)點的二叉樹時，結(jié)點的2n個指針區(qū)域中有n+1個空指針。( )【上海海運學(xué)院 1999 一、6（1分）】三、填空題1二叉樹由_(1)_，_(2)_，_(3)_三個基本單元組成?！狙嗌酱髮W(xué) 1998 一、5 （3分）】2樹在計算機(jī)內(nèi)的表示方式有_(1)_，_(2)_，_(3)_?！竟枮I工業(yè)大學(xué) 2000 二、4 (3分)】3在二叉樹中，指針p所指結(jié)點為葉子結(jié)點的條件是_?！竞戏使I(yè)大學(xué)1999 三、7（2分）】4中綴式a+b*3+4*（c-d）對應(yīng)的前綴式為_(1)_，若a=1，b=2，c=3，d=4，則后綴式db/cc*a-b*+的運算結(jié)果為_(2)_?！疚髂辖煌ù髮W(xué) 2000 一、6】5二叉樹中某一結(jié)點左子樹的深度減去右子樹的深度稱為該結(jié)點的_。【燕山大學(xué)1998一、9(1分)】6具有256個結(jié)點的完全二叉樹的深度為_。【燕山大學(xué) 1998 一、4 （1分）】7已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹有_個葉子結(jié)點?！緩B門大學(xué) 2000 六、2 （16%/3分）】8深度為k的完全二叉樹至少有_(1)_個結(jié)點，至多有_(2)_個結(jié)點?！緩B門大學(xué) 2001 一、4 （14%/5分）】 【南京理工大學(xué) 1999 二、5 （4分）】9深度為H 的完全二叉樹至少有_(1)_個結(jié)點；至多有_(2)_個結(jié)點；H和結(jié)點總數(shù)N之間的關(guān)系是 (3)_?！局锌圃河嬎闼?998 一、3（3分）1999 二、4（3分）】【中國科技大學(xué) 1998 一、3(4分）】10在順序存儲的二叉樹中，編號為i和j的兩個結(jié)點處在同一層的條件是_?！緩B門大學(xué) 2002 六、3 （4分）】11在完全二叉樹中，編號為i和j的兩個結(jié)點處于同一層的條件是_?！竞戏使I(yè)大學(xué) 2000 三、6 （2分）】12一棵有n個結(jié)點的滿二叉樹有_(1)_個度為1的結(jié)點、有_(2)_個分支 （非 終端）結(jié)點和_(3)_個葉子，該滿二叉樹的深度為_(4)_?！救A中理工大學(xué) 2000 一、6 （3分）13假設(shè)根結(jié)點的層數(shù)為，具有個結(jié)點的二叉樹的最大高度是_?！颈狈浇煌ù髮W(xué) 2001 二、1】14在一棵二叉樹中，度為零的結(jié)點的個數(shù)為N0,度為2的結(jié)點的個數(shù)為N2,則有N0 =_【北方交通大學(xué) 2001 二、6】【南京理工大學(xué) 1999 二、4 （2分）】15設(shè)只含根結(jié)點的二叉樹的高度為0，則高度為k的二叉樹的最大結(jié)點數(shù)為_,最小結(jié)點數(shù)為_?！颈本┐髮W(xué) 1997 一、1 （4分）】16設(shè)有N個結(jié)點的完全二叉樹順序存放在向量A1:N中，其下標(biāo)值最大的分支結(jié)點為_?！?長沙鐵道學(xué)院 1997 二、3 (2分)】17高度為K的完全二叉樹至少有_個葉子結(jié)點?！竞戏使I(yè)大學(xué) 1999 二、6（2分）】18高度為8的完全二叉樹至少有_個葉子結(jié)點?！竞戏使I(yè)大學(xué) 2001 三、6（2分）】19已知二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少是_?！緩B門大學(xué) 2002 六、4（4分）】20一個有2001個結(jié)點的完全二叉樹的高度為_。【南京理工大學(xué) 1997 三、2（1分）】21設(shè)F是由T1,T2,T3三棵樹組成的森林,與F對應(yīng)的二叉樹為B,已知T1,T2,T3的結(jié)點數(shù)分別為n1,n2和n3則二叉樹B的左子樹中有_(1)_個結(jié)點，右子樹中有_(2)_個結(jié)點。【南京理工大學(xué) 2000 二、9（3分）】22一個深度為k的，具有最少結(jié)點數(shù)的完全二叉樹按層次，（同層次從左到右）用自然數(shù)依此對結(jié)點編號，則編號最小的葉子的序號是_(1)_；編號是i的結(jié)點所在的層次號是_(2)_（根所在的層次號規(guī)定為1層）?！灸暇├砉ご髮W(xué) 2001 二、2（2分）】23如某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)為_。【南京理工大學(xué) 2001 二、3（2分）】24如果結(jié)點A有 3個兄弟，而且B是A的雙親，則B的度是_。【西安電子科技大學(xué)1999軟件 一、4（2分）】25高度為h的2-3樹中葉子結(jié)點的數(shù)目至多為_?！疚靼搽娮涌萍即髮W(xué)1999軟件 一、6（2分）】26完全二叉樹中，結(jié)點個數(shù)為n，則編號最大的分支結(jié)點的編號為_?！颈本┹p工業(yè)學(xué)院 2000 一、3 (2分)】27設(shè)一棵完全二叉樹葉子結(jié)點數(shù)為k,最后一層結(jié)點數(shù)2，則該二叉樹的高度為_。【北京科技大學(xué) 1998 一、3】28對于一個具有n個結(jié)點的二元樹，當(dāng)它為一棵_(1)_二元樹時具有最小高度，當(dāng)它為一棵_(2)_時，具有最大高度?！竟枮I工業(yè)大學(xué) 2001 一、3 (2分)】29具有N個結(jié)點的二叉樹，采用二叉鏈表存儲，共有_個空鏈域?！局貞c大學(xué) 2000 一、8】308層完全二叉樹至少有_個結(jié)點，擁有100個結(jié)點的完全二叉樹的最大層數(shù)為_?！疚髂辖煌ù髮W(xué) 2000 一、1】31含4個度為2的結(jié)點和5個葉子結(jié)點的二叉樹，可有_個度為1的結(jié)點?！颈本┕I(yè)大學(xué) 2001 一、6 (2分)】32一棵樹T中，包括一個度為1的結(jié)點，兩個度為2的結(jié)點，三個度為3的結(jié)點，四個度為4的結(jié)點和若干葉子結(jié)點，則T的葉結(jié)點數(shù)為_?！旧綎|大學(xué) 2001 三、2 (2分)】33 n（n大于1）個結(jié)點的各棵樹中，其深度最小的那棵樹的深度是_(1)_。它共有_(2)_個葉子結(jié)點和_(3)_個非葉子結(jié)點，其中深度最大的那棵樹的深度是_(4)_，它共有_(5)_個葉子結(jié)點和_(6)_個非葉子結(jié)點?！旧綎|大學(xué) 2001 三、7 (2分)】34 每一棵樹都能唯一的轉(zhuǎn)換為它所對應(yīng)的二叉樹。若已知一棵二叉樹的前序序列是BEFCGDH，對稱序列是FEBGCHD，則它的后序序列是_(1)_。設(shè)上述二叉樹是由某棵樹轉(zhuǎn)換而成，則該樹的先根次序序列是_(2)_?！旧綎|工業(yè)大學(xué) 1997 二、 (6分)】35先根次序周游樹林正好等同于按_(1)_周游對應(yīng)的二叉樹，后根次序周游樹林正好等同于按_(2)_周游對應(yīng)的二叉樹。【山東工業(yè)大學(xué) 1999 二、1 （4分）】36二叉樹結(jié)點的對稱序序列為A,B,C,D,E,F,G,后序序列為B,D,C,A,F,G,E,則該二叉樹結(jié)點的前序序列為_(1)_,則該二叉樹對應(yīng)的樹林包括_(2)_棵樹?！颈本┐髮W(xué) 1997 一、2 （4分）】37二叉樹的先序序列和中序序列相同的條件是_?！竞戏使I(yè)大學(xué) 2000 三、7（2分）】38已知一棵二叉樹的前序序列為abdecfhg,中序序列為dbeahfcg，則該二叉樹的根為_(1)_，左子樹中有_(2)_， 右子樹中有_(3)_?！灸暇├砉ご髮W(xué) 1996 二、1（6分）】39設(shè)二叉樹中每個結(jié)點均用一個字母表示，若一個結(jié)點的左子樹或右子樹為空，用 表示，現(xiàn)前序遍歷二叉樹，訪問的結(jié)點的序列為ABD.G.CE.H.F，則中序遍歷二叉樹時，訪問的結(jié)點序列為_(1)_;后序遍歷二叉樹時，訪問的結(jié)點序列為_(2)_。【南京理工大學(xué) 1999 二、3（4分）】40已知二叉樹前序為ABDEGCF，中序為DBG