樹和二叉樹習(xí)題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第6章 樹和二叉樹一、選擇題1算術(shù)表達式a+b*（c+d/e）轉(zhuǎn)為后綴表達式后為（ B ）EFDGAB/+*-C*Aab+cde/* Babcde/+*+ Cabcde/*+ Dabcde*/+2. 設(shè)有一表示算術(shù)表達式的二叉樹（見下圖），它所表示的算術(shù)表達式是（ C ）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-G3. 設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1 則T中的葉子數(shù)為（ D ）A5 B6 C7 D84. 在下述

2、結(jié)論中，正確的是（ D ）只有一個結(jié)點的二叉樹的度為0; 二叉樹的度為2； 二叉樹的左右子樹可任意交換;深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。 A B C D5. 設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點個數(shù)是（ A ）Am-n Bm-n-1 Cn+1 D條件不足，無法確定 6若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（ B ）A9 B11 C15 D不確定 7設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（

3、 D ）。AM1 BM1+M2 CM3 DM2+M38一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（ E ）A 250 B 500 C254 D505 E以上答案都不對(501) 9. 有關(guān)二叉樹下列說法正確的是（ B ）A二叉樹的度為2 B一棵二叉樹的度可以小于2 C二叉樹中至少有一個結(jié)點的度為2 D二叉樹中任何一個結(jié)點的度都為210二叉樹的第I層上最多含有結(jié)點數(shù)為（ c ）A2I B 2I-1-1 C 2I-1 D2I -111. 一個具有1025個結(jié)點的二叉樹的高h為（ C ）A11 B10 C11至1025之間 D10至1024之間12一棵二叉樹高度為h,所有結(jié)點的度或為0，

4、或為2，則這棵二叉樹最少有( B )結(jié)點A2h B2h-1 C2h+1 Dh+1 13. 一棵樹高為K的完全二叉樹至少有（ C ）個結(jié)點A2k 1 B. 2k-1 1 C. 2k-1 D. 2k14對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用( C )次序的遍歷實現(xiàn)編號。A先序 B. 中序 C. 后序 D. 從根開始按層次遍歷15一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（ B ）ACABDEFG BABCDEFG CDACEFBG DADCFEG 16已知一棵二叉樹的前序遍歷

5、結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為（ A ）。ACBEFDA B FEDCBA C CBEDFA D不定 17對于前序遍歷與中序遍歷結(jié)果相同的二叉樹為（F）;對于前序遍歷和后序遍歷結(jié)果相同的二叉樹為（B）。A一般二叉樹 B只有根結(jié)點的二叉樹 C根結(jié)點無左孩子的二叉樹 D根結(jié)點無右孩子的二叉樹 E所有結(jié)點只有左子數(shù)的二叉樹 F所有結(jié)點只有右子樹的二叉樹18在下列情況中，可稱為二叉樹的是（ B ） A每個結(jié)點至多有兩棵子樹的樹 B. 哈夫曼樹 C每個結(jié)點至多有兩棵子樹的有序樹 D. 每個結(jié)點只有一棵右子樹 E以上答案都不對 19n個結(jié)點的線索二叉樹上含有的線索數(shù)為（

6、 C ）A2n Bnl Cnl Dn 20由3 個結(jié)點可以構(gòu)造出多少種不同的二叉樹？（ D ）A2 B3 C4 D5 21. 當一棵有n個結(jié)點的二叉樹按層次從上到下，同層次從左到右將數(shù)據(jù)存放在一維數(shù)組 Al.n中時，數(shù)組中第i個結(jié)點的左孩子為（ A ）AA2i(2i=<n) B. A2i+1(2i+1=< n) CAi/2 D無法確定二、填空題1二叉樹由_ 根節(jié)點_，_左子樹_，_右子樹_三個基本單元組成。2中綴式a+b*3+4*（c-d）對應(yīng)的前綴式為_+a*b3*4-cd_，若a=1，b=2，c=3，d=4，則后綴式db/cc*a-b*+的運算結(jié)果為_18_。3具有256個結(jié)點

7、的完全二叉樹的深度為_9_。4已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹有_12_個葉子結(jié)點。5深度為k的完全二叉樹至少有_2(k-1)_個結(jié)點，至多有_(2k)-1_個結(jié)點。6設(shè)有N個結(jié)點的完全二叉樹順序存放在向量A1:N中，其下標值最大的分支結(jié)點為_N/2_。7一個深度為k的，具有最少結(jié)點數(shù)的完全二叉樹按層次，（同層次從左到右）用自然數(shù)依此對結(jié)點編號，則編號最小的葉子的序號是_ 2(k-2)+1 _；編號是i的結(jié)點所在的層次號是_log2 i|+1 _（log2 i|表示向上取整（根所在的層次號規(guī)定為1層）。8具有N個結(jié)點的二叉樹，采用二叉鏈表存儲，共

8、有_N+1_個空鏈域。三、應(yīng)用題1將算術(shù)表達式（a+b）+c*(d+e)+f）*(g+h)轉(zhuǎn)化為二叉樹。前序序列：*+ab*c+def+gh二叉樹如下圖所示：2已知一棵滿二叉樹的結(jié)點個數(shù)為20到40之間的素數(shù)，此二叉樹的葉子結(jié)點有多少個？ 答案：結(jié)點個數(shù)在20到40的滿二叉樹且結(jié)點數(shù)是素數(shù)的數(shù)是31，其葉子數(shù)是16。3將下列由三棵樹組成的森林轉(zhuǎn)換為二叉樹。（只要求給出轉(zhuǎn)換結(jié)果）NPGHJMOLIKEDFBAC答案：4設(shè)某二叉樹的前序遍歷序列為:ABCDEFGHI，中序遍歷序列為:BCAEDGHFI：試畫出該二叉樹；答案：后序：CBEHGIFDA 5一棵二叉樹的先序、中序、后序序列如下，其中一部分未標出，請構(gòu)造出該二叉樹。先序序列 ：_ _ C D E _ G H I _ K 中序序列 ：C B _ _ F A _ J K I G后序序列 ：_ E F D B _ J I H _ A