資源描述：
《樹和二叉樹習(xí)題及答案》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、一、填空題1.不相交的樹的聚集稱之為森林。2.從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是_樹可采用孩子-兄弟鏈表（二叉鏈表）做存儲結(jié)構(gòu)，目的是利用二叉樹的已有算法解決樹的有關(guān)問題。3.深度為k的完全二叉樹至少有2k-1個結(jié)點。至多有2k-1個結(jié)點，若按自上而下，從左到右次序給結(jié)點編號（從1開始），則編號最小的葉子結(jié)點的編號是2k-2+1。4.在一棵二叉樹中，度為零的結(jié)點的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，則有n0=n2+1。5.一棵二叉樹的第i（i≥1）層最多有2i-1
2、個結(jié)點；一棵有n（n>0）個結(jié)點的滿二叉樹共有（n+1）/2個葉子和（n-1）/2個非終端結(jié)點。6.現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有5種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果?！?.哈夫曼樹是帶權(quán)路徑最小的二叉樹。8.前綴編碼是指任一個字符的編碼都不是另一個字符編碼的前綴的一種編碼方法，是設(shè)計不等長編碼的前提。9.以給定的數(shù)據(jù)集合{4，5，6，7，10，12，18}為結(jié)點權(quán)值構(gòu)造的Huffman樹的加權(quán)路徑長度是165。10.樹被定義為連通而不具有回路的（無向）圖。11.若一棵根樹的每個結(jié)點最多只
3、有兩個孩子，且孩子又有左、右之分，次序不能顛倒，則稱此根樹為二叉樹。12.高度為k，且有個結(jié)點的二叉樹稱為二叉樹。2k-1滿13.帶權(quán)路徑長度最小的二叉樹稱為最優(yōu)二叉樹，它又被稱為樹。Huffman14.在一棵根樹中，樹根是為零的結(jié)點，而為零的結(jié)點是結(jié)點。入度出度樹葉15.Huffman樹中，結(jié)點的帶權(quán)路徑長度是指由到之間的路徑長度與結(jié)點權(quán)值的乘積。結(jié)點樹根16.滿二叉樹是指高度為k，且有個結(jié)點的二叉樹。二叉樹的每一層i上，最多有個結(jié)點。2k-12i-1二、單選題1.具有10個葉結(jié)點的二叉樹中有(B)個
4、度為2的結(jié)點。(A)8(B)9(C)10(D)112．對二叉樹的結(jié)點從1開始進(jìn)行連續(xù)編號，要求每個結(jié)點的編號大于其左右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，則可采用_（3）次序的遍歷實現(xiàn)編號。（1）先序（2）中序（3）后序（4）從根開始按層遍歷3.由2、3、4、7作為結(jié)點權(quán)值構(gòu)造的樹的加權(quán)路徑長度B。A、33B、30C、36D、404.高度為6的滿二叉樹，總共有的結(jié)點數(shù)是B。A、15B、63C、20D、255.下面描述根樹轉(zhuǎn)換成二叉樹的特性中，正確的是C。A、根樹轉(zhuǎn)換成的二
5、叉樹是唯一的，二叉樹的根結(jié)點有左、右孩子。B、根樹轉(zhuǎn)換成的二叉樹是不唯一的，二叉樹的根結(jié)點只有左孩子。C、根樹轉(zhuǎn)換成的二叉樹是唯一的，二叉樹的根結(jié)點只有左孩子。D、根樹轉(zhuǎn)換成的二叉樹是不唯一的，二叉樹的根結(jié)點有左、右孩子。6.如圖所示的4棵二叉樹中，不是完全二叉樹的是。A、○B(yǎng)、○○○○○○○○○○○C、○D、○○○○○○○○○C7.某二叉樹先序遍歷的結(jié)點序列是abdgcefh，中序遍歷的結(jié)點序列是dgbaechf，則其后序遍歷的結(jié)點序列是D。A、bdgcefhaB、gdbecfhaC、bdgaechf
6、D、gdbehfca8.已知二叉樹按中序遍歷所得到的結(jié)點序列為DCBGEAHFIJK，按后序遍歷所得到的結(jié)點序列為DCEGBFHKJIA，按先序遍歷所得到的結(jié)點序列為ABCDGEIHFJK。9.設(shè)n，m為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，n在m前的條件是C。A、n在m右方B、n是m祖先C、n在m左方D、n是m子孫10.二叉樹第i層結(jié)點的結(jié)點個數(shù)最多是（設(shè)根的層數(shù)為1）：AA）2i-1B）2i-1C）2iD）2i-111.樹的后根遍歷序列等同于該樹對應(yīng)的二叉樹的：BA）先序序列B）中序序列C）后序序列
7、12.樹最適合用來表示_C___。?A.有序數(shù)據(jù)元素???????????????????B.無序數(shù)據(jù)元素?C.元素之間具有分支層次關(guān)系的數(shù)據(jù)??D.元素之間無聯(lián)系的數(shù)據(jù)13.由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹是一種特殊的樹，這種說法_B___。?A.正確?????????B.錯誤14.假定在一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30個，則葉子結(jié)點數(shù)為????B??個。?A．15??????B．16????C．17???D．4715.按照二叉樹的定義，具有3個結(jié)點的不同形狀的二叉樹有
8、__C__種。?A.3???????B.4??????C.5??????D.616.深度為5的二叉樹至多有__C__個結(jié)點。?A.16?????B.32????C.31?????D.1017.對一個滿二叉樹，m個樹葉，n個結(jié)點，深度為h，則__D__。?A.n=h+m??????B.h+m=2n??????C.m=h-1???????D.n=2h-118.任何一棵二叉樹的葉結(jié)點在先序、中序和后序遍歷序列中的相對次序_A___。?A.不發(fā)生改
