數(shù)據(jù)結(jié)構(gòu)習(xí)題第六章樹和二叉樹(已修改)
2025-04-06 03:01 本頁面
【正文】 第六章 樹和二叉樹一、選擇題1．已知一算術(shù)表達(dá)式的中綴形式為 A+B*CD/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*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)+(FG) B. (A*B+C)/(D*E)+(FG) C. (A*B+C)/(D*E+（FG）) D. A*B+C/D*E+FG4. 設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1 則T中的葉子數(shù)為（ ）A．5 B．6 C．7 D．8【南京理工大學(xué) 2000 一、8 （）】5. 在下述結(jié)論中，正確的是（ ）【南京理工大學(xué) 1999 一、4 （1分）】①只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0。 ②二叉樹的度為2； ③二叉樹的左右子樹可任意交換。④深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。 A．①②③ B．②③④ C．②④ D．①④6. 設(shè)森林F對(duì)應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p,p的右子樹結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是（ ）A．mn B．mn1 C．n+1 D．條件不足，無法確定 【南京理工大學(xué)2000 一、17（）】7. 樹是結(jié)點(diǎn)的有限集合，它（ (1）)根結(jié)點(diǎn)，記為T。其余結(jié)點(diǎn)分成為m（m0）個(gè)(（2）)的集合T1，T2， …，Ｔm，每個(gè)集合又都是樹，此時(shí)結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn)，Ti稱為T的子結(jié)點(diǎn)（1≤i≤m）。一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)稱為該結(jié)點(diǎn)的( （3） )。二叉樹與樹是兩個(gè)不同的概念，二叉樹也是結(jié)點(diǎn)的有限集合，它(（4）)根結(jié)點(diǎn)?？梢园褬涞母Y(jié)點(diǎn)的層數(shù)定義為1，其他結(jié)點(diǎn)的層數(shù)等于其父結(jié)點(diǎn)所在層數(shù)加上1。令T是一棵二叉樹，Ki和Kj是T中子結(jié)點(diǎn)數(shù)小于2的結(jié)點(diǎn)中的任意兩個(gè)，它們所在的層數(shù)分別為λKi和λKj，當(dāng)關(guān)系式│λKiλKj│≤1一定成立時(shí)，則稱T為一棵（(5)）。供選擇的答案：（1）(4) A. 有0個(gè)或1個(gè) B. 有0個(gè)或多個(gè) C. 有且只有一個(gè) D. 有1個(gè)或1個(gè)以上（2） A. 互不相交 （3） A. 權(quán) （5） A. 豐滿樹 【上海海運(yùn)學(xué)院1999二、2(5分）】8．若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（ ）A．9 B．11 C．15 D．不確定 【(3分)】9．在一棵三元樹中度為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è)A．4 B．5 C．6 D．7 【哈爾濱工業(yè)大學(xué) 2001 二、2 （2分）】10．設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2和M3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是（ ）?！颈狈浇煌ù髮W(xué) 2001 一、16 （2分）】A．M1 B．M1+M2 C．M3 D．M2+M311．具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有（ ）個(gè)度為2的結(jié)點(diǎn)，【北京航空航天大學(xué)2000 一、5（2分)】A．8 B．9 C．10 D．ll12．一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ ）【西安交通大學(xué) 1996 三、2 (3分)】A． 250 B． 500 C．254 D．505 E．以上答案都不對(duì) 13. 設(shè)給定權(quán)值總數(shù)有n 個(gè)，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為( ) 【福州大學(xué) 1998 一、5 (2分)】A．不確定 B．2n C．2n+1 D．2n114. 有n個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（ ）?！厩鄭u大學(xué) 2002 二、1 （2分）】A．不確定 B．2n C．2n+1 D．2n115．若度為m的哈夫曼樹中，其葉結(jié)點(diǎn)個(gè)數(shù)為n，則非葉結(jié)點(diǎn)的個(gè)數(shù)為（ ）?！局锌圃河?jì)算所1999一、2（2分）】A．n1 B．235。n/m1 C．233。(n1)/(m1)249。 D． 233。n/(m1)249。1 E．233。(n+1)/(m+1)249。116. 有關(guān)二叉樹下列說法正確的是（ ）【南京理工大學(xué) 2000 一、11 （）】A．二叉樹的度為2 B．一棵二叉樹的度可以小于2 C．二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2 D．二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為217．二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為（ ）【中山大學(xué)1998二、7 （2分）】【北京理工大學(xué) 2001 六、5（2分）】A．2I B． 2I11 C． 2I1 D．2I 118. 一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（ ）【南京理工大學(xué) 1999 一、19 （2分）】A．11 B．10 C．11至1025之間 D．10至1024之間19．一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹最少有( )結(jié)點(diǎn)A．2h B．2h1 C．2h+1 D．h+1 【南京理工大學(xué)2001一、11(）】 20．對(duì)于有n 個(gè)結(jié)點(diǎn)的二叉樹, 其高度為（ ）【武漢交通科技大學(xué) 1996 一、5 (4分)】A．nlog2n B．log2n C．235。log2n|+1 D．不確定21. 一棵具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的樹高度（深度）是（ ）【南京理工大學(xué) 1996一、8 （2分）】A．235。logn+1 B．logn+1 C．235。logn D．logn122．深度為h的滿m叉樹的第k層有（ ）個(gè)結(jié)點(diǎn)。(1=k=h)【北京航空航天大學(xué)2000一、4（2分）】A．mk1 B．mk1 C．mh1 D．mh123．在一棵高度為k的滿二叉樹中，結(jié)點(diǎn)總數(shù)為（ ）【北京工商大學(xué) 2001 一、3 (
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1