第6章樹和二叉樹

《第6章樹和二叉樹》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

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

2、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ù)為（）A．5B．6C．7D．8【南京理工大學(xué)2000一、8（1.5分）】5.在下述結(jié)論中，正確的是（）【南京理工大學(xué)1999一、4（1分）】①只有一個結(jié)點的二叉樹的度為0;②二叉樹的度為2；③二叉樹的左右子樹可任意交換;④深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。A．①②③B．②③④C．②④D．①④6.設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p,p的右子

3、樹結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點個數(shù)是（）A．m-nB．m-n-1C．n+1D．條件不足，無法確定【南京理工大學(xué)2000一、17（1.5分）】7.樹是結(jié)點的有限集合，它（(1）)根結(jié)點，記為T。其余結(jié)點分成為m（m>0）個(（2）)的集合T1，T2，…，Ｔm，每個集合又都是樹，此時結(jié)點T稱為Ti的父結(jié)點，Ti稱為T的子結(jié)點（1≤i≤m）。一個結(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é)

4、點中的任意兩個，它們所在的層數(shù)分別為λKi和λKj，當(dāng)關(guān)系式│λKi-λKj│≤1一定成立時，則稱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ù)是（）A．9B．11C．15D．不確定【北京工商大學(xué)2001一.7(3分)】9．在一棵三元樹中度為3的結(jié)點數(shù)為2個，

5、度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為（）個A．4B．5C．6D．7【哈爾濱工業(yè)大學(xué)2001二、2（2分）】10．設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（）?！颈狈浇煌ù髮W(xué)2001一、16（2分）】A．M1B．M1+M2C．M3D．M2+M311．具有10個葉結(jié)點的二叉樹中有（）個度為2的結(jié)點，【北京航空航天大學(xué)2000一、5（2分)】A．8B．9C．10D．ll12．一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（）【西安交通大學(xué)1996三、2(3分)】A．250B．

6、500C．254D．505E．以上答案都不對13.設(shè)給定權(quán)值總數(shù)有n個，其哈夫曼樹的結(jié)點總數(shù)為()【福州大學(xué)1998一、5(2分)】A．不確定B．2nC．2n+1D．2n-114.有n個葉子的哈夫曼樹的結(jié)點總數(shù)為（）。【青島大學(xué)2002二、1（2分）】A．不確定B．2nC．2n+1D．2n-115．若度為m的哈夫曼樹中，其葉結(jié)點個數(shù)為n，則非葉結(jié)點的個數(shù)為（）?！局锌圃河嬎闼?999一、2（2分）】A．n-1B．?n/m?-1C．é(n-1)/(m-1)ùD．én/(m-1)ù-1E．é(n+1)/(m+1)ù-116.有關(guān)二叉樹下列說法正確的是（）【南京理工大學(xué)2000一、11（1

7、.5分）】A．二叉樹的度為2B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個結(jié)點的度為2D．二叉樹中任何一個結(jié)點的度都為217．二叉樹的第I層上最多含有結(jié)點數(shù)為（）【中山大學(xué)1998二、7（2分）】【北京理工大學(xué)2001六、5（2分）】A．2IB．2I-1-1C．2I-1D．2I-118.一個具有1025個結(jié)點的二叉樹的高h(yuǎn)為（）【南京理工大學(xué)1999一、19（2分）】A．11B．10C．11至1025之間D．10至1024之間19．一棵二叉樹高度為h,