樹和二叉樹筆試題

1、 樹和二叉樹筆試題 GSM全球移動通信系統(tǒng)概述樹和二叉樹學(xué)習(xí) 2009-12-10 17:34:37 閱讀1252 評論0 字號：大中小訂閱 四、應(yīng)用題1從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。【西安電子科技大學(xué)2001軟件 二、1（5分）】2樹和二叉樹之間有什么樣的區(qū)別與聯(lián)系？【西北工業(yè)大學(xué)1998一、3(4分)】【廈門大學(xué)2000五、2(14%/3分)】【燕山大學(xué)2001三、1(5分)】3請分析線性表、樹、廣義表的主要結(jié)構(gòu)特點，以及相互的差異與關(guān)聯(lián)。【大連海事大學(xué)2001三(10分)】4. 設(shè)有一棵算術(shù)表達式樹，

2、用什么方法可以對該樹所表示的表達式求值？【中國人民大學(xué)2001二、3(4分）】5將算術(shù)表達式（a+b）+c*(d+e)+f）*(g+h)轉(zhuǎn)化為二叉樹?！緰|北大學(xué) 2000 三、1 （4分）】6. 一棵有n(n0)個結(jié)點的d度樹, 若用多重鏈表表示, 樹中每個結(jié)點都有d個鏈域, 則在表示該樹的多重鏈表中有多少個空鏈域? 為什么? 【長沙鐵道學(xué)院 1998 四、1 (6分)】7. 一棵二叉樹中的結(jié)點的度或為0或為2，則二叉樹的枝數(shù)為2(n0-1)，其中n0是度為0的結(jié)點的個數(shù)。 【南京理工大學(xué) 1998 六、 (3分)】 類似本題的另外敘述有：（1）若二叉樹中度為1的結(jié)點數(shù)為0，則該二叉樹的總分支

3、數(shù)為2（n0-1），其中n0為葉結(jié)點數(shù)?！疚鞅惫I(yè)大學(xué) 1998 三、1（5分）】8一個深度為L的滿K叉樹有以下性質(zhì)：第L層上的結(jié)點都是葉子結(jié)點，其余各層上每個結(jié)點都有K棵非空子樹，如果按層次順序從1開始對全部結(jié)點進行編號，求：1）各層的結(jié)點的數(shù)目是多少？ 2）編號為n的結(jié)點的雙親結(jié)點（若存在）的編號是多少？3）編號為n的結(jié)點的第i 個孩子結(jié)點（若存在）的編號是多少？4）編號為n的結(jié)點有右兄弟的條件是什么？如果有，其右兄弟的編號是多少？請給出計算和推導(dǎo)過程?！疚鞅惫I(yè)大學(xué)1999五(10分)】【中科院自動化所1996二、1(10分)】類似本題的另外敘述有：（1）一棵高度為h的滿k叉樹有如下性質(zhì)

4、：根據(jù)結(jié)點所在層次為0；第h層上的結(jié)點都是葉子結(jié)點；其余各層上每個結(jié)點都有k棵非空子樹，如果按層次自頂向下，同一層自左向右,順序從1開始對全部結(jié)點進行編號，試問：1)各層的結(jié)點個數(shù)是多少?(3分) 2)編號為i的結(jié)點的雙親結(jié)點（若存在）的編號是多少?(3分)3)編號為i的結(jié)點的第m個孩子結(jié)點（若存在）的編號是多少？（3分）4)編號為i的結(jié)點有右兄弟的條件是什么？其右兄弟結(jié)點的編號是多少？（3分)【清華大學(xué) 1999 八 (12分)】9證明任一結(jié)點個數(shù)為n 的二叉樹的高度至少為O(logn).【浙江大學(xué) 2000 四、 (5分)】10有n個結(jié)點并且其高度為n的二叉樹的數(shù)目是多少?【西安電子科技大

5、學(xué)2000計應(yīng)用一、3(5分)】11已知完全二叉樹的第七層有10個葉子結(jié)點，則整個二叉樹的結(jié)點數(shù)最多是多少？【西安電子科技大學(xué)2000計應(yīng)用一、4 （5分）】12高度為10的二叉樹，其結(jié)點最多可能為多少？【首都經(jīng)貿(mào)大學(xué) 1998 一、1 （4分）】13任意一個有n個結(jié)點的二叉樹，已知它有m個葉子結(jié)點，試證明非葉子結(jié)點有（m-1）個度為2，其余度為1?！疚靼搽娮涌萍即髮W(xué)2001計應(yīng)用 二、3 （5分）】14. 已知A1.N是一棵順序存儲的完全二叉樹，如何求出Ai和Aj的最近的共同祖先？ 【中國人民大學(xué) 2001 二、5 （4分）】15給定K(K=1),對一棵含有N個結(jié)點的K叉樹（N）、請討論其可

6、能的最大高度和最小高度?！敬筮B海事大學(xué) 2001 五、 (分)】16已知一棵滿二叉樹的結(jié)點個數(shù)為20到40之間的素數(shù)，此二叉樹的葉子結(jié)點有多少個？【東北大學(xué) 1999 一、1 （3分）】17一棵共有n個結(jié)點的樹，其中所有分支結(jié)點的度均為K，求該樹中葉子結(jié)點的個數(shù)?！緰|北大學(xué) 2000 一、3 （4分）】18 如在內(nèi)存中存放一個完全二叉樹，在樹上只進行下面兩個操作：（1）尋找某個結(jié)點雙親 （2）尋找某個結(jié)點的兒子；請問應(yīng)該用何種結(jié)構(gòu)來存儲該二叉樹？【東北大學(xué) 2001 一、3 （3分）】19求含有n個結(jié)點、采用順序存儲結(jié)構(gòu)的完全二叉樹中的序號最小的葉子結(jié)點的下標。要求寫出簡要步驟?！颈本┕I(yè)大學(xué)

7、 2000 二、3 （ 5分）】20設(shè)二叉樹T中有n個頂點，其編號為1，2，3，,n,若編號滿足如下性質(zhì)：（1）T中任一頂點v的編號等于左子樹中最小編號減1；（2）對T中任一頂點v,其右子樹中最小編號等于其左子樹中的最大編號加1。試說明對二叉樹中頂點編號的規(guī)則（按何種順序編號）?！旧綎|大學(xué) 1992 一、1 （3分）】21若一棵樹中有度數(shù)為1至m的各種結(jié)點數(shù)為n1,n2,nm(nm表示度數(shù)為m的結(jié)點個數(shù))請推導(dǎo)出該樹中共有多少個葉子結(jié)點n0的公式?！颈本┼]電大學(xué)1993二1(6分)】【西安交通大學(xué)1996四、1(5分)】【南京航空航天大學(xué)1998五(10分)】【東南大學(xué)1999一 4（8分)】

8、【山東大學(xué)1993一2(4分)】【山東師范大學(xué)2001 二3(12分) 2001二2(15分)】22若一棵完全二叉樹中葉子結(jié)點的個數(shù)為n,且最底層結(jié)點數(shù)2，則此二叉樹的深度H=？【北京科技大學(xué) 2001 一、6 （2分）】23已知完全二叉樹有30個結(jié)點，則整個二叉樹有多少個度為0的結(jié)點？【山東師范大學(xué)1996五、3(2分)】24在一棵表示有序集S的二叉搜索樹(binary search tree)中,任意一條從根到葉結(jié)點的路徑將S分為3部分：在該路徑左邊結(jié)點中的元素組成的集合Sl；在該路徑上的結(jié)點中的元素組成的集合S2；在該路徑右邊結(jié)點中的元素組成的集合S3。S=S1S2S3。若對于任意的aS

9、l,bS2，cS3是否總有abc?為什么?【清華大學(xué) 2000 四(10分)】【武漢大學(xué) 2000 三、3】25試證明,在具有n(n=1)個結(jié)點的m次樹中,有n(m-1)+1個指針是空的?！緩?fù)旦大學(xué)1998四(8分)】26對于任何一棵非空的二叉樹,假設(shè)葉子結(jié)點的個數(shù)為n0,而次數(shù)為2的結(jié)點個數(shù)為n2,請給出n0和n2之間所滿足的關(guān)系式n0=f(n2).要求給出推導(dǎo)過程。【復(fù)旦大學(xué) 1998 五 (8分)】27對于任意一棵非空的二叉樹T，我們用n0表示T中葉子結(jié)點的個數(shù)，用n2表示T中有兩棵非空子樹的結(jié)點的個數(shù)。（1）給出n0和n2所滿足的關(guān)系式。（2）證明你在（1）中給出的關(guān)系式成立?！緩?fù)旦大

10、學(xué) 1997 三 (10分)】28試求有n個葉結(jié)點的非滿的完全二叉樹的高度;【中科院計算所 2000 五、 (5分)】29對于具有n個葉子結(jié)點，且所有非葉子結(jié)點都有左右孩子的二叉樹，(1)試問這種二叉樹的結(jié)點總數(shù)是多少？（5分）(2)試證明=1。其中:li表示第i個葉子結(jié)點所在的層號(設(shè)根結(jié)點所在層號為1)。(10分)【北方交通大學(xué) 1995 三、 (15分)】30假設(shè)高度為H的二叉樹上只有度為0和度為2的結(jié)點，問此類二叉樹中的結(jié)點數(shù)可能達到的最大值和最小值各為多少？【北京郵電大學(xué) 1996 一、1 （4分）】31一棵滿k叉樹，按層次遍歷存儲在一維數(shù)組中，試計算結(jié)點下標的u的結(jié)點的第i個孩子的

11、下標以及結(jié)點下標為v的結(jié)點的父母結(jié)點的下標?！颈本┼]電大學(xué) 2001 四、4(5分）】32二叉樹有n個頂點，編號為1，2，3， ，n，設(shè)：* T中任一頂點V的編號等于左子樹中最小編號減1；* T中任一頂點V的右子樹中的最小編號等于其左子樹中的最大編號加1；試描繪該二叉樹?！緰|南大學(xué) 1999 一、2 （7分）】33設(shè)T是具有n個內(nèi)結(jié)點的擴充二叉樹，I是它的內(nèi)路徑長度，E是它的外路徑長度。（1）試利用歸納法證明E=I+2n, n=0.（5分)（2）利用（1）的結(jié)果試說明：成功查找的平均比較次數(shù)s與不成功查找的平均比較次數(shù)u 之間的關(guān)系可用公式表示s=(1+1/n)u-1,n=1。 【清華大學(xué) 1

12、998 四、 (10分)】34一棵非空的有向樹中恰有一個頂點入度為0, 其它頂點入度為1,但一個恰有一個頂點入度為0,其它頂點入度為1的有向圖卻不一定是一棵有向樹,請舉例說明?！局锌圃河嬎闼?1999 三、1 （5分）】35試給出下列有關(guān)并查集（mfsets）的操作序列的運算結(jié)果：union(1,2),union(3,4),union(3,5),union(1,7),union(3,6),union(8,9),union(1,8),union(3,10),union(3,11),union(3,12),union(3,13),union(14,15),union(16,0),union(14,

13、16),union(1,3),union(1,14).(union是合并運算，在以前的書中命名為merge)要求（1）對于union(i,j),以i作為j的雙親； （5分)（2）按i和j為根的樹的高度實現(xiàn)union(i,j),高度大者為高度小者的雙親； （5分)（3）按i和j為根的樹的結(jié)點個數(shù)實現(xiàn)union(i,j),結(jié)點個數(shù)大者為結(jié)點個數(shù)小者的雙親。（5分)【清華大學(xué) 2001 一、 (15分)】36證明：在任何一棵非空二叉樹中有下面的等式成立：葉結(jié)點的個數(shù)=二度結(jié)點的個數(shù)+1【天津大學(xué) 1999 四】37. 對于一個堆棧，若其入棧序列為1，2，3，n，不同的出入棧操作將產(chǎn)生不同的出棧序列。

14、其出棧序列的個數(shù)正好等于結(jié)點個數(shù)為n的二叉樹的個數(shù)，且與不同形態(tài)的二叉樹一一對應(yīng)。請簡要敘述一種從堆棧輸入（固定為1，2，3n）/輸出序列對應(yīng)一種二叉樹形態(tài)的方法，并以入棧序列1，2，3（即n=3）為例加以說明?！菊憬髮W(xué) 1998年 五、1 (7分)】38. 如果給出了一個二叉樹結(jié)點的前序序列和對稱序序列，能否構(gòu)造出此二叉樹?若能，請證明之。若不能，請給出反例。如果給出了一個二叉樹結(jié)點的前序序列和后序序列，能否構(gòu)造出此二叉樹?若能，請證明之。若不能，請給出反例?！颈本┐髮W(xué) 1998 二、2 （5分)】類似本題的另外敘述有：（1） 二叉樹的中序與后序序列能唯一地定義一棵二叉樹嗎? 這里所指序列

15、中的符號代表樹結(jié)點中的標識符嗎？二叉樹的前序與后序序列能唯一地定義一棵二叉樹嗎?為什么?【東南大學(xué)1993一、4（8分）】39試證明:同一棵二叉樹的所有葉子結(jié)點，在前序序列。對稱序序列以及后序序列中都按相同的相對位置出現(xiàn)（即先后順序相同），例如前序abc,后序bca對稱序bac?！旧綎|工業(yè)大學(xué) 1997 七、 (10分)】40. 由二叉樹的中序序列及前序序列能唯一的建立二叉樹，試問中序序列及后序序列是否也能唯一的建立二叉樹，不能則說明理由，若能對中序序列DBEAFGC和后序序列DEBGFCA構(gòu)造二叉樹。 【南京理工大學(xué) 1998 四、 (3分)】41. 證明，由一棵二叉樹的前序序列和中序序列可

16、唯一確定這棵二叉樹。設(shè)一棵二叉樹的前序序列為ABDGECFH，中序序列為：DGBEAFHC 。試畫出該二叉樹?！菊憬髮W(xué) 1996 六、 (8分)】類似本題的另外敘述有：(1) 證明：由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹?！鹃L沙鐵道學(xué)院1997五、2(10分)】（2）證明：由二叉樹的中序遍歷序列和后序遍歷序列可唯一地確定出該二叉樹?！救A南理工大學(xué) 2001 一、3 （4分)】（3）二叉樹已知其中序掃描序列和后序掃描序列如何確定這一棵二叉樹,并舉例說明. 【山東大學(xué) 2001軟件與理論二 、1 （4分）】42試證明：僅僅已知一棵二叉樹的后序遍歷序列和先序遍歷序列，不能唯一地確定這

17、棵二叉樹?！敬筮B海事大學(xué) 2001 九、 (分)】類似本題的另外敘述有：(1) 由二叉樹的前序遍歷和后序遍歷結(jié)果能否唯一確定一棵二叉樹？解釋你的論斷。【西安電子科技大學(xué)2001計應(yīng)用 二、4 （5分）】(2) 假定某二叉樹的前序遍歷序列為ABCDEFGHIJ,后序遍歷序列為CEFDBJIHGA,據(jù)此兩個序列能否唯一確定此二叉樹? 若不能,試畫出兩樣具有同樣上述遍歷序列的二叉樹.【武漢交通科技大學(xué)1996二8（3分）】43. 試找出滿足下列條件的二叉樹1）先序序列與后序序列相同 2）中序序列與后序序列相同3）先序序列與中序序列相同 4）中序序列與層次遍歷序列相同 已知一棵二叉樹的中序序列和后序序

18、列分別為DBEAFIHCG和DEBHIFGCA，畫出這棵二叉樹?！緰|北大學(xué) 1999 六、 (4分)】類似本題的另外敘述有：（1）試畫出在先根次序和中根次序下結(jié)點排列順序皆相同的所有類型的二叉樹形。試畫出在先根次序和后根次序下結(jié)點排列順序皆相同的所有類型的二叉樹形?！炯执髮W(xué) 1995 四、1,2 （每題7分)】（2）找出所有的二叉樹，其結(jié)點在下列兩種遍歷下恰好都有同樣的遍歷序列。1）先序遍歷和中序遍歷 2）先序遍歷和后序遍歷【北京理工大學(xué) 1999 三(6分)】（3）找出所有的二叉樹，其結(jié)點在下列兩種遍歷下，恰好都是以同樣的順序出現(xiàn)： 1）前序遍歷和中序遍歷。 2）前序遍歷和后序遍歷。【南京

19、航空航天大學(xué) 1995 六(5分)】（4）試找出分別滿足下列條件的所有二叉樹。1）先序序列和中序序列相同 2）中序序列和后序序列相同 3）先序序列和后序序列相同 【南京航空航天大學(xué) 2001 二、（10分)】（5）找出所有滿足下列條件的二叉樹：1）它們在先序遍歷和中序遍歷時，得到的結(jié)點訪問序列相同；2）它們在后序遍歷和中序遍歷時，得到的結(jié)點訪問序列相同；3）它們在先序遍歷和后序遍歷時，得到的結(jié)點訪問序列相同；【東南大學(xué)2000一、4(6分）】44將下列由三棵樹組成的森林轉(zhuǎn)換為二叉樹。（只要求給出轉(zhuǎn)換結(jié)果）【南京航空航天大學(xué) 1998 一、 (10分)】45. 閱讀下列說明和流程圖，回答問題（1

20、）和問題（2）。說明：流程圖是用來實現(xiàn)中序遍歷，二叉樹存放在數(shù)組tree中，每個數(shù)組元素存放樹中一個結(jié)點，每個結(jié)點的形式為（值，左指針，右指針），分別用treei.v，treei.l，treei.r來表示第i個結(jié)點的值，左指針，右指針，其中左，右指針的值為所指結(jié)點在數(shù)組中的下標，若指針的值為0，表示它指向空樹，圖中指針root用以指向二叉樹的根結(jié)點。問題： （1）填充流程圖中的、，使其按中序遍歷二叉樹。（2）把流程圖中的（A）框移至哪個位置（圖中）使流程圖的算法從中序遍歷變成后序遍歷。【上海海運學(xué)院 1997年四、（13分）】46設(shè)一棵二叉樹的先序、中序遍歷序列分別為先序遍歷序列： A B D

21、 F C E G H 中序遍歷序列： B F D A G E H C（1）畫出這棵二叉樹。（2）畫出這棵二叉樹的后序線索樹。 （3）將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹（或森林）?！灸暇┖娇蘸教齑髮W(xué) 1997 二、 (10分)】47已知一棵二叉樹的對稱序和后序序列如下：對稱序：GLDHBEIACJFK 后序： LGHDIEBJKFCA(1) (1) （2分)給出這棵二叉樹：(2) (2) （2分)轉(zhuǎn)換為對應(yīng)的森林：(3) (3) （4分)畫出該森林的帶右鏈的先根次序表示法： Itag= (4) (4分) 畫出該森林帶度數(shù)的后根次序表示法：(5) (4分)在帶度數(shù)的后根次序表示法中，不包含指針，但仍能完全

22、反映樹的結(jié)構(gòu)。寫出以結(jié)點x為根的子樹在后根次序序列中的前驅(qū)的求法。（用語言敘述，不用寫算法）【山東大學(xué) 1998 八、（16分）】48設(shè)某二叉樹的前序遍歷序列為:ABCDEFGGI，中序遍歷序列為:BCAEDGHFI：（1）試畫出該二叉樹；（2）寫出由給定的二叉樹的前序遍歷序列和中序遍歷序列構(gòu)造出該二叉樹的算法。（3）設(shè)具有四個結(jié)點的二叉樹的前序遍歷序列為；為長度等于四的由，排列構(gòu)成的字符序列，若任取作為上述算法的中序遍歷序列，試問是否一定能構(gòu)造出相應(yīng)的二叉樹，為什么？試列出具有四個結(jié)點二叉樹的全部形態(tài)及相應(yīng)的中序遍歷序列。 【浙江大學(xué) 1997 六、 (15分)】類似本題的另外敘述有：（1）

23、已知二叉樹的先序序列: CBHEGAF, 中序序列: HBGEACF, 試構(gòu)造該二叉樹【北京理工大學(xué) 2001 八、2 （4分）】（2）已知二叉樹按中序排列為BFDAEGC，按前序排列為ABDFCEG，要求畫出該二叉樹?！旧綎|師范大學(xué) 1996 五、1 (2分)】（3）已知一棵二叉樹的前序序列 A,B,D,C,E,F，中序序列B,D,A,E,F,C. 畫出這棵二叉樹?！狙嗌酱髮W(xué) 1999 四、 (5分)】（4）已知一棵二叉樹的前序遍歷結(jié)果是：ABCDEFGHIJ,中序遍歷的結(jié)果是：BCEDAGHJIF,試畫出這棵二叉樹。【廈門大學(xué) 1998 六、1 （7分)】（5）已知二叉樹BT各結(jié)點的先序、

24、中序遍歷序列分別為ABCDEGF和CBAEDF，試畫出該二叉樹?！颈本┕I(yè)大學(xué) 1998 二、 (6分)】49. 假設(shè)一棵二叉樹的前序序列為ABCD,它的中序序列可能是DABC嗎?【石油大學(xué)1998一、1(5分)】類似本題的另外敘述有：（1）一棵前序序列為1，2，3，4，的二叉樹，其中序序列可能是4，1，2，3嗎？設(shè)一棵二叉樹的前序序列為1，2，3，4，5，6，7，8，9，其中序序列為2，3，1，5，4，7，8，6，9，試畫出該二叉樹?！緰|南大學(xué) 1996一、2 （7分) 1998 一、3】50一棵非空的二叉樹其先序序列和后序序列正好相反，畫出這棵二叉樹的形狀?！疚靼搽娮涌萍即髮W(xué)2000軟件一

25、、8 （5分）】51已知一棵二叉樹的后序遍歷序列為EICBGAHDF，同時知道該二叉樹的中序遍歷序列為CEIFGBADH，試畫出該二叉樹?！局貞c大學(xué) 2000 二、2】類似本題的另外敘述有：（1）已知二叉樹各結(jié)點的中序和后序序列分別為和，試構(gòu)造出該二叉樹，并作簡要說明?！颈狈浇煌ù髮W(xué) 1997 二、 (8分)】（2）已知二叉樹的中序遍歷序列為G F B E A N H M，后序遍歷的結(jié)點序列為G E B F H N M A ，畫出此二叉樹的形態(tài)?！厩鄭u海洋大學(xué) 1999 一、5（5分)】（3）已知二叉樹的后序序列為ABCDEFG 和中序序列為ACBGEDF，構(gòu)造出該二叉樹?！靖Ｖ荽髮W(xué) 1998

26、 三、1 (6分)】（4）已知某二叉樹的后序遍歷和中序遍歷如下，構(gòu)造出該二叉樹。后序遍歷序列： G D B E I H F C A 中序遍歷序列：D G B A E C H I F【廈門大學(xué) 2000 七、1 （20%/3分)】（5）已知一個二分樹的中序序列和后序序列如下：中序：A B C D E F G H I J 后序：A C D B H J I G F E 試畫出此二分樹的結(jié)構(gòu)。 【首都經(jīng)貿(mào)大學(xué) 1998 二、1 （10分）】52假設(shè)一棵二叉樹的層次序列為ABCDEFGHIJ，中序序列DBGEHJACIF。請畫出這棵二叉樹?！疚錆h大學(xué) 2000 三、1】【東南大學(xué) 2000 一、1 （6

27、分）】類似本題的另外敘述有：（1）假設(shè)一棵二叉樹的層次次序（按層次遞增順序排列，同一層次自左向右）為ABECFGDHI,中序序列為BCDAFEHIG。請畫出該二叉樹，并將其轉(zhuǎn)換為對應(yīng)的森林。【山東大學(xué) 2001 四、 (6分)】53. 已知一個森林的先序序列和后序序列如下，請構(gòu)造出該森林。先序序列：ABCDEFGHIJKLMNO后序序列：CDEBFHIJGAMLONK 【合肥工業(yè)大學(xué) 2000 四、1 （5分）】54 畫出同時滿足下列兩條件的兩棵不同的二叉樹。 (1)按先根序遍歷二叉樹順序為ABCDE。 (2)高度為5其對應(yīng)的樹（森林）的高度最大為4?！緰|北大學(xué) 1997 一、3 （5分）】5

28、5用一維數(shù)組存放的一棵完全二叉樹；ABCDEFGHIJKL。請寫出后序遍歷該二叉樹的訪問結(jié)點序列?！疚靼搽娮涌萍即髮W(xué)1999計應(yīng)用一、6 （5分）】56一棵二叉樹的先序、中序、后序序列如下，其中一部分未標出，請構(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 【廈門大學(xué) 2002 七、1 （6分)】類似本題的另外敘述有：（1）一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分為顯示出來。試求出空格處的內(nèi)容，并畫出該二叉樹。先序序列: _ B F I C E H

29、 G中序序列：D K F I A E J C 后序序列： K F B H J G A 【西安電子科技大學(xué)2000計應(yīng)用 五、2 （5分)】（2）已知一棵二叉樹的先序 中序和后序序列如下，其中空缺了部分，請畫出該二叉樹。先序：_ B C _ E F G _ I J K _中序：C B E D _ G A J _ H _ L后序：_ E _ F D _ J _ L _ H A 【合肥工業(yè)大學(xué) 2001 四、1 （5分)】（3）已知含有8個結(jié)點的一棵二叉樹，按先序、中序、后序進行遍歷后，有些結(jié)點序號不清楚如下圖示。要求構(gòu)造出一棵符合條件的二叉樹。先根序遍歷 _ 2 3 _ 5 _ 7 8中根序遍歷

30、3 _ 4 1 _ 7 8 6后根序遍歷 _ 4 2 _ _ 6 5 1 【東北大學(xué) 1996 一、3 （5分）】57M 叉樹的前序和后序遍歷分別與由它轉(zhuǎn)換成的二叉樹的哪種遍歷相對應(yīng)？【中國人民大學(xué) 2000 一、2 （4分）】58證明：在二叉樹的三種遍歷序列中，所有葉子結(jié)點間的先后關(guān)系都是相同的。要求每步論斷都指出根據(jù)。【北京工業(yè)大學(xué) 2001 二、3 （5分）】59. 下表中MN分別是一棵二叉樹中的兩個結(jié)點，表中行號i=1，2，3，4分別表示四種MN的相對關(guān)系，列號j=1，2，3分別表示在前序、中序、后序遍歷中M,N之間的先后次序關(guān)系。要求在i，j所表示的關(guān)系能夠發(fā)生的方格內(nèi)打上對號。例如

31、：如果你認為n是m的祖先，并且在中序遍歷中n能比m先被訪問，則在（3，2）格內(nèi)打上對號 先根遍歷時n先被訪問中根遍歷時n先被訪問后根遍歷時n先被訪問N在M的左邊N在M的右邊N是M的祖先N是M的子孫【南京理工大學(xué) 2001 四、 (10分)】60用一維數(shù)組存放的一棵完全二叉樹如下圖所示： ABCDEFGHIJKL寫出后序遍歷該二叉樹時訪問結(jié)點的順序?！颈本┕I(yè)大學(xué) 1996 一、4 （6分）】61設(shè)樹形T在后根次序下的結(jié)點排列和各結(jié)點相應(yīng)的次數(shù)如下：后根次序：次數(shù)：請畫出的樹形結(jié)構(gòu)圖。 【吉林大學(xué) 2001 一、2 （4分）】62已知二叉樹采用二叉鏈表方式存放，要求返回二叉樹T的后序序列中的第一

32、個結(jié)點的指針，是否可不用遞歸且不用棧來完成？請簡述原因。【西北大學(xué) 2001 三 6】63對于二叉樹T的兩個結(jié)點n1和n2，我們應(yīng)該選擇樹T結(jié)點的前序、中序和后序中哪兩個序列來判斷結(jié)點n1必定是結(jié)點n2的祖先,并給出判斷的方法。不需證明判斷方法的正確性?！緩?fù)旦大學(xué) 1999 五 (10分)】64設(shè)二叉樹的存儲結(jié)構(gòu)如下(每題5分,共15分) LINK 0 0 2 3 7 5 8 0 10 1 INFO J H F D B A C E G I RLINK 0 0 0 9 4 0 0 0 0 0其中,T為樹根結(jié)點的指針,LLINK、RLINK分別指向結(jié)點的左右子女,INFO為其數(shù)據(jù)域,請完成下列各題

33、:（1）畫出二叉樹T的邏輯結(jié)構(gòu). （2）寫出按前序、中序和后序周游二叉樹T得到的結(jié)點序列.（3）畫出二叉樹T的后序線索樹。 【山東工業(yè)大學(xué) 1995 六、（15分）】65在二叉樹的前序遍歷和中序遍歷的遞歸算法中，最后一個遞歸調(diào)用語句在調(diào)用時所保留的參數(shù)有什么作用？如何清除最后這個遞歸語句？【北京郵電大學(xué) 1994 三、 (8分)】66在二叉樹的link-Rlink存儲表示中，引入“線索”的好處是什么？【山東大學(xué) 1999 六、(分）】67按下面要求解下圖中二叉樹的有關(guān)問題： (1)對此二叉樹進行后序后繼線索化 ；(2)將此二叉樹變換為森林；(3)用后根序遍歷該森林，；寫出遍歷后的結(jié)點序列?！颈?/p>

34、京郵電大學(xué) 1996 五、 (10分)】類似本題的另外敘述有：（1）已知一棵二叉樹的先序遍歷序列為：AEFBGCDHIKJ，中序遍歷序列為：EFAGBCHKIJD。試寫出此二叉樹的后序遍歷序列，并用圖畫出它的后序線索二叉樹?！就瑵髮W(xué) 2000 一、 (10分)】68對下圖所示二叉樹分別按前序中序后序遍歷，給出相應(yīng)的結(jié)點序列，同時給二叉樹加上中序線索?！厩鄭u海洋大學(xué) 1999年一、1 （5分）】 第67題圖69. 假設(shè)一個二叉樹的兩種遍歷如下：前序：ABFGCHDEIJLK 中序：FGBHCDILJKEA（1）畫出這棵二叉樹以及它的中序線索樹；（2）寫出在中序線索樹的情況下，找到結(jié)點N的前驅(qū)結(jié)

35、點的算法INORDER-PRIOR(N,X)【上海海運學(xué)院 1996 四、 (10分)】70已知一棵二叉樹的中序（或中根）遍歷結(jié)點排列為DGBAECHIF，后序（或后根）遍歷結(jié)點排列為GDBEIHFCA，（1）試畫出該二叉樹；（2）試畫出該二叉樹的中序穿線（或線索）樹；（3）試畫出該二叉樹（自然）對應(yīng)的森林；【吉林大學(xué) 2000 一、1 （5分）】71設(shè)二叉樹BT的存儲結(jié)構(gòu)如下: 1 2 3 4 5 6 7 8 9 10 Lchild00237580101DataJHFDBACE GIRchild0009 4 00 000其中BT為樹根結(jié)點的指針，其值為6,Lchild,Rchild分別為結(jié)點

36、的左、右孩子指針域,data為結(jié)點的數(shù)據(jù)域。試完成下列各題:（l）畫出二叉樹BT的邏輯結(jié)構(gòu);（2）寫出按前序、中序、后序遍歷該二叉樹所得到的結(jié)點序列;（3）畫出二叉樹的后序線索樹。【中國礦業(yè)大學(xué) 2000 二、 (15分)】72請說明是否存在這樣的二叉樹，即它可以實現(xiàn)后序線索樹進行后序遍歷時不使用棧；而對前序線索樹進行前序遍歷時，又有什么樣的二叉樹可不使用棧?！疚靼搽娮涌萍即髮W(xué) 1996 二、1 (5分）】73一棵左右子樹均不空的二叉樹在先序線索化后，其空指針域數(shù)為多少？【西安電子科技大學(xué) 2000計應(yīng)用 一、2 （5分）】74在前序線索樹上，要找出結(jié)點p的直接后繼結(jié)點，請寫出相關(guān)浯句。結(jié)點結(jié)

37、構(gòu)為(ltag,lc,data,rtag,rc)?！疚鞅贝髮W(xué) 2000 二、6 （5分）】75對于后序線索二叉樹，怎樣查找任意結(jié)點的直接后繼；對于中序線索二叉樹，怎樣查找任意結(jié)點的直接前驅(qū)？【西北工業(yè)大學(xué) 1998 一、4 （4分）】76將下列樹的孩子兄弟鏈表改為后根遍歷全線索鏈表?！厩迦A大學(xué) 1994 二、 (10分)】 DataABCDEFGHIJKLtag00000000000Fch205780110000Rtag00000000000Nsib03406009100077. 已知一棵二叉樹的前序遍歷為ABECDFGHIJ，中序遍歷為EBCDAFHIGJ。試畫出這棵樹和它的中序線索樹。假定

38、用于通訊的電文僅有8個字母C1，C2，C8組成，各個字母在電文中出現(xiàn)的頻率分別為5，25，3，6，10，11，36，4，試為這8個字母設(shè)計哈夫曼編碼樹?！旧虾：＿\學(xué)院1998四(10分)】78設(shè)有正文AADBAACACCDACACAAD,字符集為A,B,C,D,設(shè)計一套二進制編碼，使得上述正文的編碼最短?！臼锥冀?jīng)貿(mào)大學(xué) 1997 一、5 （4分)】類似本題的另外敘述有：（1）設(shè)有正文MNOPPPOPMMPOPOPPOPNP，字符集為M，N，O，P，設(shè)計一套二進制編碼，使得上述正文的編碼最短。【首都經(jīng)貿(mào)大學(xué) 1998 一、5 （4分）】79給定集合15,3,14,2,6,9,16,17(1)（3

39、分）用表示外部結(jié)點，用表示內(nèi)部結(jié)點，構(gòu)造相應(yīng)的huffman樹：(2) (2分)計算它的帶權(quán)路徑長度：(3)（3分)寫出它的huffman編碼：(4)（3分)huffman編碼常用來譯碼，請用語言敘述寫出其譯碼的過程?！旧綎|大學(xué) 1998 七、】【山東工業(yè)大學(xué) 2000 七、 (11分)】類似本題的另外敘述有：（1） 如果通信字符a,b,c,d出現(xiàn)頻度分別為：7，5，2，4請畫出哈夫曼樹并給出相應(yīng)的哈夫曼編碼?！厩鄭u大學(xué) 2001 七、1 （5分)】（2）給定一組數(shù)列（15,8,10,21,6,19,3）分別代表字符A,B,C,D,E,F,G出現(xiàn)的頻度，試敘述建立哈夫曼樹的算法思想，畫出哈夫曼

40、樹，給出各字符的編碼值，并說明這種編碼的優(yōu)點。【青島大學(xué) 2000 七、 (10分)】（3）設(shè)通信中出現(xiàn)5中字符A、B、C、D、E對應(yīng)的頻率為0.2,0.1,0.5,0.15,0.25構(gòu)造哈夫曼樹，并給出對應(yīng)字符的編碼?！厩鄭u大學(xué) 2002 四、2 （10分）】（4） 設(shè)A、B、C、D、E、F六個字母出現(xiàn)的概率分別為7,19,2,6,32,3。試寫出為這六個字母設(shè)計的HUFFMAN編碼, 并畫出對應(yīng)的HUFFMAN樹.【山東工業(yè)大學(xué) 1995 四(10分)】（5）設(shè)用于通信的電文由8個字母組成, 字母在電文中出現(xiàn)的頻率分別為:7,19,2,6,32,3,21,10。試為這8個字母設(shè)計哈夫曼編碼

41、.使用0-7的二進制表示形式是另一種編碼方案,試比較這兩種方案的優(yōu)缺點?！灸暇┖娇蘸教齑髮W(xué) 1999 四、 (10分)】（6）假設(shè)用于通訊的電文由8個字符組成，其出現(xiàn)的頻率為5,29,7,8,14,23,3,11。試為這8個字符設(shè)計哈夫曼編碼?！狙嗌酱髮W(xué) 1999 五、 (5分)】（7）假設(shè)用于通信的電文由字符集a,b,c,d,e,f,g中的字母構(gòu)成。它們在電文中出現(xiàn)的頻度分別為0.31,0.16,0.10,0.08,0.11,0.20,0.04, 1) 為這7個字母設(shè)計哈夫曼編碼；2）對這7個字母進行等長編碼，至少需要幾位二進制數(shù)？哈夫曼編碼比等長編碼使電文總長壓縮多少？【北京郵電大學(xué) 20

42、01 四、2 （5分)】（8）試構(gòu)造一棵二叉樹,包含權(quán)為1,4,9,16,25,36,49,64,81,100等10個終端結(jié)點,且具有最小的加權(quán)路徑長度WPL?！颈狈浇煌ù髮W(xué) 1993年 五（12分)】（9）帶權(quán)結(jié)點為5,6,7,8,9，構(gòu)造Huffman樹，計算帶權(quán)路徑長度。【西北大學(xué)2001年三、3】（10）以數(shù)據(jù)集2,5,7,9,13為權(quán)值構(gòu)造一棵哈夫曼樹，并計算其帶權(quán)路徑長度?！疚靼搽娮涌萍即髮W(xué)1999計應(yīng)用一、4 （5分）】（11）假設(shè)用于通訊的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為7,19,2,6,32,3，21,10。試為這8個字母設(shè)計哈夫曼編碼。使用07的二進制表示

43、形式是另一 種編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。【大連海事大學(xué) 1996 五、2 (8分)】。（12）設(shè)用于通訊的電文僅由8個字母組成，他們在電文中出現(xiàn)的頻率分別為0.30，0.07，0.10，0.03，0.20，0.06,0.22，0.02，試設(shè)計哈夫曼樹及其編碼。使用0-7的二進制表示形式是另一種編碼方案。給出兩種編碼的對照表、帶權(quán)路徑長度WPL值并比較兩種方案的優(yōu)缺點?！緩B門大學(xué) 1999 三、3】(13) 給定一組權(quán)值2,3,5,7,11,13,17,19,23,29，31，37，41，試畫出用Huffman算法建造的Huffman樹?！炯执髮W(xué) 2000 一、2 （4分)

44、】(14) 以數(shù)據(jù)集3,4,5,8,12,18,20,30為葉結(jié)點，構(gòu)造一棵哈夫曼樹，并求其帶權(quán)路徑長度?！旧綎|師范大學(xué) 1996 五 5(2分)】80 給定權(quán)W1,W2,，Wm 。說明怎樣來構(gòu)造一個具有最小的加權(quán)路徑長度的k叉樹。試對于權(quán)1,4,9,16,25, 36,49,64,81,100來構(gòu)造最優(yōu)的三叉樹，并給出其最小加權(quán)路徑長度?！颈狈浇煌ù髮W(xué)1994年 四(12分）】81已知下列字符A、B、C、D、E、F、G的權(quán)值分別為3、12、7、4、2、8，11，試填寫出其對應(yīng)哈夫曼樹HT的存儲結(jié)構(gòu)的初態(tài)和終態(tài)?！颈本┕I(yè)大學(xué) 1998 五、 (10分)】82什么是前綴編碼？舉例說明如何利用二

45、叉樹來設(shè)計二進制的前綴編碼?！局猩酱髮W(xué)1999三、1 (3分)】83如果一棵huffman樹T有n0個葉子結(jié)點，那么，樹T有多少個結(jié)點，要求給出求解過程?！緩?fù)旦大學(xué) 1999 四、 (10分)】84設(shè)T是一棵二叉樹，除葉子結(jié)點外，其它結(jié)點的度數(shù)皆為2，若 T中有6個葉結(jié)點，試問：（1）T樹的最大深度Kmax=?最小可能深度Kmin=?（2）T樹中共有多少非葉結(jié)點？(3) 若葉結(jié)點的權(quán)值分別為1,2,3,4,5,6。請構(gòu)造一棵哈曼夫樹，并計算該哈曼夫樹的帶權(quán)路徑長度wpl?！颈本┼]電大學(xué) 1992 一、3】85對如下算法，解答下列問題。PROCEDURE inorder(T:bitree);BE

46、GIN top:=1; stop:=T;REPEAT WHILE stopNIL DO BEGIN stop+1:=stop.lchild; top:=top+1; END;IF top1 THEN BEGIN top:=top-1;WRITE (stop.data);stop:=stop.rchild;END;UNTIL top=0END;（1）該算法正確嗎？循環(huán)結(jié)束條件top=0能否滿足？（2）若將IF top1改為IF top0是否正確？（3）若將結(jié)束條件改為top=1,其它不變，是否正確？（4）若僅將結(jié)束處條件改為(top=1)AND (stop=NIL),是否正確？（5）試找出二叉樹

47、中各結(jié)點在棧中所處層次的規(guī)律。 【西安電子科技大學(xué)2000計應(yīng)用 三(10分)】五、算法設(shè)計題1假設(shè)一個僅包含二元運算符的算術(shù)表達式以鏈表形式存儲在二叉樹BT中，寫出計算該算術(shù)表達式值的算法?！緰|北大學(xué) 2000 三、2 （10分）】2給出算法將二叉樹表示的表達式二叉樹按中綴表達式輸出，并加上相應(yīng)的括號?！颈本┼]電大學(xué) 2001 五、3 （10分）】3（此題統(tǒng)考生做） 用PASCAL語言（或類PASCAL語言）完成下列各題：（1）設(shè)表達式a+b*(c-d)-e/f 可以表示成如下二叉樹結(jié)構(gòu)： t其中t為根結(jié)點指針，試運用后序遍歷二叉樹的規(guī)則，寫出對表達式求值的算法：EXPVALUE【北京科技大

48、學(xué) 1998年八、1 （10分）】4編程求以孩子兄弟表示法存儲的森林的葉子結(jié)點數(shù)。要求描述結(jié)構(gòu)?！颈本┕I(yè)大學(xué)2000五(10分)】5假定用兩個一維數(shù)組LN和RN作為有N個結(jié)點1，2,， N的二元樹的存儲結(jié)構(gòu)。Li和Ri分別指示結(jié)點 i的左兒子和右兒子；Li=0（Ri=0）表示i的左（右）兒子為空。試寫一個算法，由L和R建立一個一維數(shù)組Tn，使Ti存放結(jié)點i的父親；然后再寫一個判別結(jié)點U是否為結(jié)點V的后代的算法。【哈爾濱工業(yè)大學(xué) 1999 七 (14分)】類似本題的另外敘述有：（1）假定用兩個一維數(shù)組L1.n和R1.n作為有n個結(jié)點的二叉樹的存儲結(jié)構(gòu)，Li和Ri分別指示結(jié)點i的左孩子和右孩子，

49、0表示空。寫一算法，建立一維數(shù)組T1.n，使T中第i(i=1,2,.,n)個分量指示結(jié)點i的雙親，然后判別結(jié)點u是否為v的子孫的算法?！救A南師范大學(xué)2000 六(17分)】6要求二叉樹按二叉鏈表形式存儲，（1）寫一個建立二叉樹的算法。（2）寫一個判別給定的二叉樹是否是完全二叉樹的算法。完全二叉樹定義為：深度為K，具有N個結(jié)點的二叉樹的每個結(jié)點都與深度為K的滿二叉樹中編號從1至N的結(jié)點一一對應(yīng)。此題以此定義為準?！疚鞅贝髮W(xué) 2000 六 (12分)】類似本題的另外敘述有：（1）試寫一算法判斷某二叉樹是否是完全二叉樹?！厩鄭u海洋大學(xué) 1999 六(15分)】（2）編程，判斷一棵二叉鏈表表示的二叉樹

50、是否是完全二叉樹?！灸暇┖娇蘸教齑髮W(xué)2001十(10分)】（3）編寫算法判斷一棵二叉樹BT是否是完全二叉樹。【北方交通大學(xué) 1997 八 (20分)】（4）假設(shè)二元樹用左右鏈表示，試編寫一算法，判別給定二元樹是否為完全二元樹？【哈爾濱工業(yè)大學(xué) 2000 十一 (14分)】（5）設(shè)二叉樹以二叉鏈表為存儲結(jié)構(gòu)，試給出判斷一棵二叉樹是否為滿二叉樹的算法，用類pascal語言寫為函數(shù)形式?！灸祥_大學(xué) 1997 四 (16分)】（6）試寫一算法判別某二叉樹是否是完全二叉樹?！颈本┼]電大學(xué) 1994 九 (20分)】7有n個結(jié)點的完全二叉樹存放在一維數(shù)組A1.n中，試據(jù)此建立一棵用二叉鏈表表示的二叉樹 ，

51、根由tree指向。 【南京理工大學(xué) 1998 七、1 （6分）】8設(shè)任意非空二叉樹中結(jié)點按層次順序依次編號為1,2,n(n0),其存儲結(jié)構(gòu)采用下圖所示形式，其中i表示結(jié)點的編號, L(i)的值是i的左兒子的編號，R(i)的值是i的右兒子的編號。若L(i),R(i)的值為0，表示結(jié)點i無左兒子或右兒子。試設(shè)計算法： （1）求出二叉樹的高度。 （2）求出每個結(jié)點的層號（根結(jié)點層號為1），并填入D(i)中。（可采用任何高級語言，但要注明你所采用的語言名稱）?！旧綎|大學(xué) 1992 三、 (13分)】9已知深度為h的二叉樹采用順序存儲結(jié)構(gòu)已存放于數(shù)組BT1:2h-1中，請寫一非遞歸算法，產(chǎn)生該二叉樹的二

52、叉鏈表結(jié)構(gòu)。設(shè)二叉鏈表中鏈結(jié)點的構(gòu)造為(lchild,data,rchild),根結(jié)點所在鏈結(jié)點的指針由T給出?！颈本┖娇蘸教齑髮W(xué) 1999 七、 (15分)】10. 二叉樹的動態(tài)二叉鏈表結(jié)構(gòu)中的每個結(jié)點有三個字段：data，lchild，rchild。其中指針lchild 下標datalchildrchild 1 A 2 6 2 B 3 4 3 C 0 0 4 D 5 0 5 E 0 0 6 F 0 7 7 G 0 0和rchild的類型為bitre。靜態(tài)二叉鏈表是用數(shù)組作為存儲空間，每個數(shù)組元素存儲二叉樹的一個結(jié)點，也有三個字段：data，lchild，rchild。所不同的是，lchil

53、d和rdhild 為integer型，分別用于存儲左右孩子的下標，如果沒有左右孩子，則相應(yīng)的值為0。例如，下面左圖所示的二叉樹的靜態(tài)二叉鏈表如右圖所示。編寫算法由二叉樹的動態(tài)二叉鏈表構(gòu)造出相應(yīng)的靜態(tài)二叉鏈表a1.n，并寫出其調(diào)用形式和有關(guān)的類型描述。其中n為一個確定的整數(shù)?！竞戏使I(yè)大學(xué) 2000 五、3 （8分）】11假設(shè)以雙親表示法作樹的存儲結(jié)構(gòu)，寫出雙親表示的類型說明，并編寫求給定的樹的深度的算法。（注:已知樹中結(jié)點數(shù)）【清華大學(xué) 1994 七、 (15分)】12試編寫算法求出二叉樹的深度。二叉樹的存儲結(jié)構(gòu)為如下說明的二叉鏈表: TYPE btre=bnode bnode=RECORD data:datatype; lch,rch:btre END; 【北京輕工業(yè)學(xué)院1997一(15分)】【南京航空航天大學(xué)1997十(10)】【北京理工大學(xué)2000四3(4）】13二叉樹采用二叉鏈表存儲：（1）編寫計算整個二叉樹高度的算法（二叉