計算機專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)樹和二叉樹歷年真題試卷匯編7

計算機專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)（樹和二叉樹）歷年真題試卷匯編7（總分：60.00，做題時間：90分鐘）一、綜合題（總題數(shù)：30，分?jǐn)?shù)：60.00）.若某非空二叉樹采用順序存儲結(jié)構(gòu)，結(jié)點的數(shù)據(jù)信息依次存放于一個一維數(shù)組中（假設(shè)數(shù)組的第一個元素的下標(biāo)為1）,下標(biāo)分別為i和j的兩個結(jié)點處在樹中同一層的條件是°（iWjW1）【北京航空航天大學(xué)2006一、6（1分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：[logi]=[logj]。編號為i的結(jié)點的高度是[logi]+1。）解析：.給定K（KN1）,對一棵含有IV個結(jié)點的K叉樹（N>0）,請討論其可能的最大高度和最小高度。【大連海事大學(xué)2001五（8分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：N個結(jié)點的K叉樹，最大高度N（只有一個葉結(jié)點的任意K叉樹）。設(shè)最小高度為H,第i（1WiWH）層的結(jié)點數(shù)為Fk+1,則（Ki+1+1）/（K-1）H-1）/（K-1）,由此得H=[log（N（K-1））]+1。）k解析：.已知一棵滿二叉樹的結(jié)點個數(shù)為20到40之間的素數(shù)，此二叉樹的葉子結(jié)點有多少個？【東北大學(xué)1999一、1（3分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：結(jié)點個數(shù)在20到40的滿二叉樹且結(jié)點數(shù)是素數(shù)的數(shù)是31,該二叉樹的葉子數(shù)是16。）解析：.一棵共有n個結(jié)點的樹，其中所有分支結(jié)點的度均為K,求該樹中葉子結(jié)點的個數(shù)?！緰|北大學(xué)2000一、3（4分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：設(shè)分支結(jié)點和葉子結(jié)點數(shù)分別是為nk和n0,因此有n=P/n0+nk（1）另外從樹的分支數(shù)B與結(jié)點的關(guān)系有n=B+1=K*nk+1（2）由（1）和（2）,有n0=n—nk=（n（K+1）+1）/Ko）解析：.已知在一棵含有n個結(jié)點的樹中，只有度七的分支結(jié)點和度為0的葉子結(jié)點，求該樹含有的葉子結(jié)點數(shù)。【大連理工大學(xué)2005二、2（20/4分）】【江蘇大學(xué)2004三、5（6分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：設(shè)分支結(jié)點和葉子結(jié)點數(shù)分別是為nk和n0,因此有n=P/n0+nk（1）另外從樹的分支數(shù)B與結(jié)點的關(guān)系有n=B+1=K*nk+1（2）由（1）和（2）,有n0=n—nk=（n（K+1）+1）/K。）解析：.證明：一棵滿k叉樹上的葉子結(jié)點數(shù)加和非葉子結(jié)點數(shù)，m之間滿足關(guān)系n0=（k-1）m+1?！颈本┙煌ù髮W(xué)2006四、1（5分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：因為n=n0+m和n=B+1=km+1,其中B為分支數(shù)。故n0+m=km+1,所以n0=（k-1）m+1。）解析：.如在內(nèi)存中存放一個完全二叉樹，在樹上只進行下面兩個操作：（1）尋找某個結(jié)點雙親；（2）尋找某個結(jié)點的兒子。請問應(yīng)該用何種結(jié)構(gòu)來存儲該二叉樹？【東北大學(xué)2001一、3（3分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：用順序存儲結(jié)構(gòu)存儲n個結(jié)點的完全二叉樹。編號為i的結(jié)點，其雙親編號是［i/2］（i=時為根結(jié)點，無雙親），其左子女是2i（若2iWn,否則i無左子女），右子女是2i+1（若2i+Wn,否則無右子女）。）解析：.試求有n個葉結(jié)點的非滿的完全二叉樹的高度?！局锌圃河嬎闼?000五（5分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：設(shè)完全二叉樹中葉子結(jié)點數(shù)為n,則根據(jù)完全二叉樹的性質(zhì)，度為2的結(jié)點數(shù)是n一1,而完全二叉樹中，度為1的結(jié)點數(shù)至多為1,所以具有n個葉子結(jié)點的完全二叉樹結(jié)點數(shù)是n+（n—1）+1=2n或2n—1（有或無度為1的結(jié)點）。由于具有2n（或2n—1）個結(jié)點的完全二叉樹的深度是［log（2n）］+1（或［log（2n-1）］+1）,即［logn］+1,故n個葉結(jié)點的非滿的完全二叉樹的高度是［logn］+1（最2 2 2 2下層結(jié)點數(shù)＞=2）,或log2n+2（最下層只一個葉結(jié)點）。）解析：.已知完全二叉樹的第七層有10個葉子結(jié)點，則整個二叉樹的結(jié)點數(shù)最多是多少?【西安電子科技大學(xué)2000計算機應(yīng)用一、4（5分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：235。由于本題求二叉樹的結(jié)點數(shù)最多是多少，第7層共有27-1=64個結(jié)點，已知有10個葉子，其余54個結(jié)點均為分支結(jié)點。它在第8層上有108個葉子結(jié)點。所以該二叉樹的結(jié)點數(shù)最多可達27一1+108=235。（注意；本題并未明說完全二叉樹的高度，但根據(jù)題意，只能8層。））解析：.已知一棵完全二叉樹有892個結(jié)點，試求：（1）樹的高度⑵葉結(jié)點個數(shù)⑶單支結(jié)點數(shù)（4）最后一個非終端結(jié)點的序號【中國海洋大學(xué)2006五（15分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：（1）根據(jù)公式：［log892］+1,所以樹的高度是10。（2）根據(jù)公式：n=n0+n1+n2=2n02一1+n1,所以葉結(jié)點數(shù)為446。（3）根據(jù)（2）,單支結(jié)點數(shù)為1。（4）最后一個非終端結(jié)點，即完全二叉樹最后結(jié)點的雙親，序號是［892/2］=446。）解析：.求含有n個結(jié)點、采用順序存儲結(jié)構(gòu)的完全二叉樹中的序號最小的葉子結(jié)點的下標(biāo)。要求寫出簡要步驟?！颈本┕I(yè)大學(xué)2000二、3（5分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：根據(jù)完全二叉樹的性質(zhì)，最后一個結(jié)點（編號為n）的雙親結(jié)點的編號是［n/2］,這是最后一個分支結(jié)點，在它之后是第一個葉子結(jié)點，故序號最小的葉子結(jié)點的下標(biāo)是［n/2］+1。）解析：.設(shè)二叉樹T中有n個頂點，其編號為1,2,3,…，n,若編號滿足如下性質(zhì)：（1）T中任一頂點1,的編號等于左子樹中最小編號減1;（2）對T中任一頂點v,其右子樹中最小編號等于其左子樹中的最大編號加1。試說明對二叉樹中頂點編號的規(guī)則（按何種順序編號）?！旧綎|大學(xué)1992一、1（3分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：按前序遍歷對頂點編號，即根結(jié)點從1開始，對前序遍歷序列的結(jié)點從小到大編號。）解析：.已知一棵度為M的樹中有n1個度為1的結(jié)點，n2個度為2結(jié)點，…，nm個度為m的結(jié)點，證明其葉結(jié)點個數(shù)為【中國海洋大學(xué)2004五（15分）】【山東大學(xué)1993一、2（4分）】【西安交通大學(xué)1996四、點個數(shù)為【中國海洋大學(xué)2004五（15分）】【山東大學(xué)1993一、2（4分）】【西安交通大學(xué)1996四、1（5分）】【東南大學(xué)1999一、4（8分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：設(shè)樹的結(jié)點數(shù)為n，分支數(shù)為B，則下面二式成立：n=n+n+n+…+n（1）n=B+1=n012m+2n+…-mn （2）由（1）和（2）得，葉子結(jié)點數(shù)I——）1 2 m解析：.若一棵度為7的樹有8個度為1的結(jié)點，有7個度為2的結(jié)點，有6個度為3的結(jié)點，有5個度為4的結(jié)點，有4個度為5的結(jié)點，有3個度為6的結(jié)點，有2個度為7的結(jié)點，則該樹一共有個結(jié)點。【北京航空航天大學(xué)2006一、5（1分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：78。）解析：.有一非空樹，其度為4,已知度為f的結(jié)點數(shù)有i個，其中1Wi<5,試問其葉結(jié)點個數(shù)是多少？【天津大學(xué)2005一、1（5分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：21）解析：.已知二叉樹有50個葉子結(jié)點，則二叉樹的總結(jié)點數(shù)至少應(yīng)為多少個?請給出計算過程?！局锌圃貉芯可?004五（7分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：99。由公式n=n0+n1+n2=n0+n1+n0—1=2n0+n1-1,當(dāng)n1=0時，二又樹的結(jié)點數(shù)最少。）解析：.下圖給出了一個二叉樹的順序存儲結(jié)構(gòu)，其中空白表示結(jié)點不存在。請回答下列問題：（1）畫出該二叉I審N匐樹。（2）給出該二叉樹的中序序列和后序序列。I 【北京理工大學(xué)2007三、3（6分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：二叉樹按完全二叉樹存儲，加了虛結(jié)點。二叉樹略。中序序列：BADCFE,后序序列：BDFECAo）解析：.下列完全二叉樹共有d層及n個結(jié)點，試在下圖涂黑的結(jié)點（葉結(jié)點）上標(biāo)上相應(yīng)的序號（用d或n表示）o【浙江大學(xué)2004三（5分）】I——I（分?jǐn)?shù)：2.00）正確答案：（正確答案：第一個結(jié)點是編號最小的葉子結(jié)點，編號為[n/2]+1；第二個結(jié)點是d-1層最后一個，編號為2d-1一1；第三個結(jié)點是d層第一個結(jié)點，編號為2d-1；第一個結(jié)點是d層最后一個結(jié)點，編號為no）解析：.一棵完全二叉樹有500個結(jié)點，請問該完全二叉樹有多少個葉子結(jié)點?有多少個度為1的結(jié)點?有多少個度為2的結(jié)點?如果完全二叉樹有501個結(jié)點，結(jié)果如何?請寫出推導(dǎo)過程?！緰|南大學(xué)2004一、1（5分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：二叉樹度為2的結(jié)點n2和度為0的結(jié)點n0間有關(guān)系式n2=n0-1，且完全二叉樹中度為1的結(jié)點n1至多為1，由上述關(guān)系得知完全二叉樹結(jié)點間的公式n=2n0+n1-1。故當(dāng)n=500時，n0=250，n1=1，n2=249;n=501時，n0=251，n1=0，n2=250。）解析：.對于具有n個葉子結(jié)點，且所有非葉子結(jié)點都有左、右孩子的二叉樹，（1）試問這種二叉樹的結(jié)點總數(shù)是多少？（5分）（2）試證明I——。其中：lt表示第i個葉子結(jié)點所在的層號（設(shè)根結(jié)點所在層號為1）。（10分）【北方交通大學(xué)1995三（15分）】 ,（分?jǐn)?shù)：2.00）正確答案：（正確答案：（1）根據(jù)二叉樹度為2結(jié)點個數(shù)等于葉子結(jié)點個數(shù)減1的性質(zhì)，故具有n個葉子結(jié)點且非葉子結(jié)點均有左右子樹的二叉樹的結(jié)點數(shù)是2n-1。（2）證明：當(dāng)i=1時，2-（k-1）=20=1，公式成立。設(shè)當(dāng)i=n-1時公式成立，證明當(dāng)i=n時公式仍成立。設(shè)某葉子結(jié)點的層號為t，當(dāng)將該結(jié)點變?yōu)閮?nèi)部結(jié)點，從而再增加兩個葉子結(jié)點時，這兩個葉子結(jié)點的層號都是t+1，對于公式的變化，是減少了一個原來的葉子結(jié)點，增加了兩個新葉子結(jié)點，反映到公式中，因為2-（t-1）=2-（t+1-1）+2-（t+1-1），所以結(jié)果不變，這就證明當(dāng)i=n時公式仍成立。證畢。）解析：.假設(shè)高度為H的二叉樹上只有度為0和度為2的結(jié)點，問此類二叉樹中的結(jié)點數(shù)可能達到的最大值和最小值各為多少？【北京郵電大學(xué)1996一、1（4分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：結(jié)點數(shù)的最大值2h—1（滿二叉樹）；最小值2h-1（第一層根結(jié)點，其余每層均兩個結(jié)點）。）解析：.一棵滿k叉樹，按層次遍歷存儲在一維數(shù)組中，試計算結(jié)點下標(biāo)為"的結(jié)點的第f個孩子的下標(biāo)以及結(jié)點下標(biāo)為1,的結(jié)點的父母結(jié)點的下標(biāo)?！颈本┼]電大學(xué)2001四、4（5分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案:（1）k（u-1）+1+i（2）［（v-2）/k+1）解析：.二叉樹有n個頂點，編號為1,2,3,…，n,設(shè)：T中任一頂點V的編號等于左子樹中最小編號減1；T中任一頂點V的右子樹中最小編號等于其左子樹中的最大編號加1。試描繪該二叉樹。【東南大學(xué)1999一、2（7分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：該二叉樹是按前序遍歷順序編號，以根結(jié)點為編號1,前序遍歷的順序是“根一左一右”。）解析：.設(shè)T是具有n個內(nèi)結(jié)點的擴充二叉樹，I是它的內(nèi)路徑長度，E是它的外路徑長度。（1）試?yán)脷w納法證明E=I+2n,nN0。（5分）（2）利用（1）的結(jié)果，試說明：成功查找的平均比較次數(shù)s與不成功查找的平均比較次數(shù)u之間的關(guān)系可用公式表示s=（1+1/n）u-1,n>=1?！厩迦A大學(xué)1998四（10分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：（1）設(shè)n=1,則e+2*1=2（只有一個根結(jié)點時，有兩個外部結(jié)點），公式成立。設(shè)有n個結(jié)點時，公式成立，即E°=1n+2n（1）現(xiàn)在要證明，當(dāng)有n+1個結(jié)點時公式成立。增加一個內(nèi)部

結(jié)點，設(shè)路徑長度為1,則In+1=In+l（2）該內(nèi)部結(jié)點，其實是從一個外部結(jié)點變來的，即這時相當(dāng)于也增加了一個外部結(jié)點（原外部結(jié)點變成內(nèi)部結(jié)點時，增加兩個外部結(jié)點），則En+1=En+1+2（3）由（1）和（2），則（3）推導(dǎo)為En+1=In+2n+1+2=In+1—1+2n+1+2=In+1+2（n+1）故命題成立。"（2）成功查找的平均比較次數(shù)s=I/n不成功查找的平均比較次數(shù)u=（E,n）/（n+；）［（I+n）/n+1由以上二式，有s=（1+1/n）*u一1。）解析：.對于一個堆棧，若其入棧序列為1,2,3,…，n,不同的出入棧操作將產(chǎn)生不同的出棧序列。其出棧序列的個數(shù)正好等于結(jié)點個數(shù)為n的二叉樹的個數(shù)，且與不同形態(tài)的二叉樹一一對應(yīng)。請簡要敘述一種從堆棧輸入（固定為1,2,3,…，n）/輸出序列對應(yīng)一種二叉樹形態(tài)的方法，并以入棧序列1,2,3（即n=3）為例加以說明?！菊憬髮W(xué)1998五、1（7分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：由于二叉樹前序遍歷序列和中序遍歷序列可唯一確定一棵二叉樹，因此，若入棧序列為1,2,3,…，n,相當(dāng)于前序遍歷序列是1,2,3,…，n,出棧序列就是該前序遍歷對應(yīng)的二叉樹的中序序列。因為中序遍歷的實質(zhì)就是一個結(jié)點進棧和出棧的過程，二叉樹的形態(tài)確定了結(jié)點進棧和出棧的順序，也就確定了結(jié)點的中序序列。下圖以入棧序列1,2,3（解釋為二叉樹的前序序列）為例，說明不同形態(tài)的二叉樹在中序遍歷時棧的狀態(tài)和訪問結(jié)點次序的關(guān)系:解析：.如果給出了一個二叉樹結(jié)點的前序序列和對稱序序列，能否構(gòu)造出此二叉樹?若能，請證明之。若不能，請給出反例。如果給出了一個二叉樹結(jié)點的前序序列和后序序列，能否構(gòu)造出此二叉樹?若能，請證明之。若不能，請給出反例。【北京大學(xué)1998二、2（5分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：給定二叉樹結(jié)點的前序序列和對稱序（中序）序列，可以唯一確定該二叉樹。因為前序序列的第一個元素是根結(jié)點，該元素將二叉樹中序序列分成兩部分，左邊（設(shè)l個元素）表示左子樹，若左邊無元素，則說明左子樹為空；右邊（設(shè)r個元素）是右子樹，若為空，則右子樹為空。根據(jù)前序遍歷中“根一左子樹一右子樹”的順序，則由從第二元素開始的l個結(jié)點序列和中序序列根左邊的l個結(jié)點序列構(gòu)造左子樹，由前序序列最后r個元素序列與中序序列根右邊的r個元素序列構(gòu)造右子樹。由二叉樹的前序序列和后序序列不能唯一確定一棵二叉樹，因無法確定左、右子樹兩部分。例如，任何結(jié)點只有左子樹的一棵二叉樹和任何結(jié)點只有右子樹的一棵二叉樹，其兩棵樹的前序序列相同，后序序列相同，但卻是兩棵不同的二叉樹。）解析：.試證明：同一棵二叉樹的所有葉子結(jié)點，在前序序列。對稱序序列以及后序序列中都按相同的相對位置出現(xiàn)（即先后順序相同），例如前序abc，后序bca，對稱序bac。【山東工業(yè)大學(xué)1997七（10分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：前序遍歷是“根一左一右”，中序遍歷是“左一根一右”，后序遍歷是“左一右一根”。三種遍歷中只是訪問“根”結(jié)點的時機不同，對左右子樹均是按先左后右順序來遍歷的，因此所有葉子都按相同的相對位置出現(xiàn)。）解析：.證明：在二叉樹的三種遍歷序列中，所有葉子結(jié)點間的先后關(guān)系都是相同的。要求每步論斷都指出根據(jù)?！颈本┕I(yè)大學(xué)2001二、3（5分）】（分?jǐn)?shù)：2.00）正確答案：（正確答案：前序遍歷是“根一左一右”，中序遍歷是“左一根一右”，后序遍歷是“左一右一根”。若將“根”去掉，三種遍歷就?！白笠挥摇薄ＨN遍歷中的差別就是訪問根結(jié)點的時機不同。二叉樹是遞歸定義的，對左右子樹均是按左右順序來遍歷的，因此三種遍歷中葉子結(jié)點間的先后關(guān)系都是相同的。）解析：.現(xiàn)在按前序遍歷二叉樹的結(jié)果為abc,有哪幾種不同的二叉樹可以得到這一結(jié)果?畫出這些二叉樹?！颈本├砉ご髮W(xué)2006六、3（50/7分）】.由二叉樹的中序序列及前序序列能唯一地建立二叉樹，試問中序序列及后序序列是否也能唯一地建立二叉樹，不能，則說明理由，若能，對中序序列DBEAFGC和后序序列DEBGFCA構(gòu)造二叉樹?！灸暇├砉ご髮W(xué)