已知某二叉樹的先序遍歷和中序遍歷的結(jié)果是先序遍歷ABDEGCF

樹與二叉樹復(fù)習(xí)一、填空1、由二叉樹的（中）序和（前、后）序遍歷序列可以唯一確定一棵二叉樹。2、任意一棵二叉樹，若度為0的結(jié)點(diǎn)個數(shù)為n0,度為2的結(jié)點(diǎn)個數(shù)為n2,則n0等于（n0=n2+1）。3、一棵二叉樹的第i（iNl）層最多有（2i-1）個結(jié)點(diǎn)。4、一棵有n個結(jié)點(diǎn)的二叉樹，若它有n0個葉子結(jié)點(diǎn)，則該二叉樹上度為1的結(jié)點(diǎn)個數(shù)n1=（n-2n0+1）。5、在一棵高度為5的完全二叉樹中，最少含有（16）個結(jié)點(diǎn)。2.有一個有序表為{1, 3,9,12, 32, 41, 45, 62, 75, 77,82, 95, 100},當(dāng)折半查找值為82的結(jié)點(diǎn)時，（C）次比較后查找成功。A.11B5C4D87、在有n個葉結(jié)點(diǎn)的哈夫曼樹中，總結(jié)點(diǎn)數(shù)（2n-1）。8、若一個問題的求解既可以用遞歸算法，也可以用遞推算法，則往往用（遞推）算法，因為（遞推算法效率高）。9、設(shè)一棵完全二叉樹有700個結(jié)點(diǎn)，則共有（350）葉子結(jié)點(diǎn)。10、設(shè)一棵完全二叉樹具有1000個結(jié)點(diǎn)，該樹有（500）個葉子結(jié)點(diǎn)，有（499）個度為2的結(jié)點(diǎn)，有（1）個結(jié)點(diǎn)只有非空左子樹。二、判斷1、（義）在哈夫曼樹中，權(quán)值最小的結(jié)點(diǎn)離根結(jié)點(diǎn)最近。2、（J）完全二叉樹中，若一個結(jié)點(diǎn)沒有左孩子，則它必是葉子結(jié)點(diǎn)。3、（J）二叉樹的前序遍歷序列中，任意一個結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面。4、（義）若一搜索樹（查找樹）是一個有n個結(jié)點(diǎn)的完全二叉樹，則該樹的最大值一定在葉結(jié)點(diǎn)上。5、（J）若以二叉鏈表作為樹和二叉樹的存儲結(jié)構(gòu)，則給定任一棵樹都可以找到唯一的一棵二叉樹與之對應(yīng)。6、（J）若一搜索樹（查找樹）是一個有n個結(jié)點(diǎn)的完全二叉樹，則該樹的最小

值一定在葉結(jié)點(diǎn)上。三、選擇1、樹最適合用來表示（C）A、有序數(shù)據(jù)元素 B、無序數(shù)據(jù)元素C、元素之間具有分支層次關(guān)系的數(shù)據(jù) D、元素之間無聯(lián)系的數(shù)據(jù)2、在有n（n>0）個結(jié)點(diǎn)的二叉鏈表中，空鏈域的個數(shù)為（B）。A、n B、n+1 C、n-1 D、不確定3、已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為（A）。A、CBEFDAB、FEDCBA C、CBEDFA D、不定4、對于有n個結(jié)點(diǎn)的完全二叉樹，其高度為（C）A、nlog2n B、log2n C、110g2n」+1 D、不確定5、在有n個結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個數(shù)為（A）A、n-1 B、2n-1C、n+1D、2n+16、將一棵有100個結(jié)點(diǎn)的完全二叉樹從根開始編號，每層上從左到右依次對結(jié)點(diǎn)進(jìn)行編號，跟結(jié)點(diǎn)的編號為1，則編號為49的結(jié)點(diǎn)的左孩子編號為（A）A、98 B、99C、50D、48、7、設(shè)有一表示算術(shù)表達(dá)式的二叉樹（見下圖），它所表示的算術(shù)表達(dá)式是（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-G8、已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E,后綴形式為ABC*+DE/-,其前綴形式為（D）。A、-A+B*C/DE B、-A+B*CD/E C、 -+*ABC/DE D、-+A*BC/DE9、堆的形狀是一棵（C）A.二叉排序樹6.滿二叉樹C.完全二叉樹D.平衡二叉樹10、若一組記錄的排序碼為（46,79,56,38,40,84，則利用堆排序的方法建立的初始堆為（B）。A.79, 46,56,38,40, 84 B.84, 79, 56,38,40, 46C.84, 79,56,46,40, 38 D.84, 56, 79,40,46, 3811.查找效率最高的二叉排序樹是（C）。A.所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹。B.所有結(jié)點(diǎn)的右子樹都為空的二叉排序樹?？谄胶舛鏄洹.沒有左子樹的二叉排序樹。12.判斷序列是否為堆（小根堆或大根堆），如果不是，將其調(diào)整為堆。17,18,60,40,7,32,73,6596,83,72,45,28,54,60,23,38,1525,48,16,35,79,82,23,40,36,7212,24,18,65,33,56,33,92,86,7013、下面編碼中哪一個不是前綴碼（B）。A. （00,01,10, 11） B. （0, 1,00,11）C. （0,10,110, 111） D. （1, 01,000,001）11、在解決遞歸問題時，若不用遞歸函數(shù)就應(yīng)借助于數(shù)據(jù)結(jié)構(gòu)（B）。A、線性表B、棧C、隊列 口、雙向隊列14、一棵完全二叉樹的第6層有8個葉結(jié)點(diǎn)，該二叉樹的結(jié)點(diǎn)個數(shù)最多是（111）。15、在分量1~11的數(shù)組中按從小到大順序存放11個元素，如果進(jìn)行二分查找，查找次數(shù)最少的元素位于什么位置？A.1 B.5 C.6 D.1116、如果一個完全二叉樹最底下一層為第六層（根為第一層）且該層共有8個葉結(jié)點(diǎn)，那么該完全二叉樹共有多少個結(jié)點(diǎn)？A.31 B.39 C.63 D.7117、若有一二叉樹的總結(jié)點(diǎn)數(shù)為98,只有一個兒子的結(jié)點(diǎn)數(shù)為48,則該樹的葉結(jié)點(diǎn)數(shù)是多少？A.25 B.50C.不確定 D.這樣的樹不存在18、假定只有四個結(jié)點(diǎn)A、B、C、D的二叉樹，其前序遍歷序列為ABCD,則下面哪個序列是不可能的中序遍歷序列？A.ABCDB.ACDBC.DCBAD.DABC19、對于二叉樹，如果其中序遍歷結(jié)果與前序遍歷結(jié)果一樣，那么可以斷定該二叉樹—A.是完全二叉樹B.所有結(jié)點(diǎn)都沒有左兒子C.所有結(jié)點(diǎn)都沒有右兒子D.這樣的樹不存在正確答案：B你選對了20、已知一二叉樹的后序和中序遍歷的結(jié)果分別是FDEBGCA和FDBEACG,那么該二叉樹的前序遍歷結(jié)果是什么？A.ABDFECGB.ABDEFCGC.ABDFEGCD.ABCDEFG21、已知一棵由1、2、3、4、5、6、7共7個結(jié)點(diǎn)組成的二叉搜索樹（查找樹），其結(jié)構(gòu)如圖所示，問：根結(jié)點(diǎn)是什么？A.4 一二一；不能確定 uBn22、在上題的搜索樹中刪除結(jié)點(diǎn)1，那么刪除后該搜索樹的后序遍歷結(jié)果是：A.243765B.432765C.234567D.76543223、將1、2、3、4、5、6順序插入初始為空的AVL樹中，當(dāng)完成這6個元素的插入后，該AVL樹共有多少層？A.2 B.3 C.4 D.524、25、在最大堆{97,76,65,50,49,13,27}中插入83后，該最大堆為：A.{97,76,65,83,49,13,27,50}B.{97,83,65,76,49,13,27,50}C.{97,83,65,76,50,13,27,49}D.{97,83,65,76,49,50,13,27}26、下列序列中哪個是最小堆？A.2,55,52,72,28,98,71TOC\o"1-5"\h\zB.2,28, 71, 72, 55, 98, 52C.2,28, 52, 72, 55, 98, 71D.28,2, 71, 72, 55, 98, 5227、對由同樣的n個整數(shù)構(gòu)成的二叉搜索樹（查找樹）和最小堆，下面哪個說法是不正確的：兒二叉搜索樹（查找樹）高度大于等于最小堆高度B.對該二叉搜索樹（查找樹）進(jìn)行中序遍歷可得到從小到大的序列C.從最小堆根節(jié)點(diǎn)到其任何葉結(jié)點(diǎn)的路徑上的結(jié)點(diǎn)值構(gòu)成從小到大的序列D.對該最小堆進(jìn)行按層序（levelorder）遍歷可得到從小到大的序列28、一段文本中包含對象｛a,b,c,d,e｝，其出現(xiàn)次數(shù)相應(yīng)為｛3,2,4,2,1｝，則經(jīng)過哈夫曼編碼后，該文本所占總位數(shù)為：A.12 B.27 C.36D.以上都不是29、為五個使用頻率不同的字符設(shè)計哈夫曼編碼，下列方案中哪個不可能是哈夫曼編碼？A.00，100，101，110，111B.000，001，01，10，11C.0000，0001，001，01，1D.000，001，010，011，130、如果哈夫曼樹有67個結(jié)點(diǎn)，則可知葉結(jié)點(diǎn)總數(shù)為：A.22 B.33 C.34D.不確定四、應(yīng)用1、設(shè)一正文所用的字符集為X=｛x1,x2,x3,x4,x5,x6,x7｝，各字符在正文中出現(xiàn)的頻率分別為2,3,4,6,8,11,12。請用哈夫曼算法為這個字符集設(shè)計一套二進(jìn)制編碼,使正文中字符的二進(jìn)制內(nèi)部表示最短。要求：（1）畫出對應(yīng)的哈夫曼樹；⑵給出X中各字符的編碼表；⑶以X中各字符出現(xiàn)的頻度為權(quán)，計算其帶權(quán)路徑的長度。2.設(shè)有序順序表中的元素依次為017,094,154,170,275,503,509,512,553,612,677,765,897,908。試畫出對其進(jìn)行折半搜索時的判定樹，并計算搜索成功的平均搜索長度和搜索不成功的平均搜索長度。

折半搜索時的判定樹:ASLsucc=1/14(1+2*2+3*4+4*7)=45/14ASLunsucc=1/15(4*1+5*14)=74/153、試畫出從空樹開始