樹和二叉樹筆試題

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

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

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

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

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

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

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

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

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

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

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

12、998 四、 (10分)】34一棵非空的有向樹中恰有一個頂點入度為0, 其它頂點入度為1,但一個恰有一個頂點入度為0,其它頂點入度為1的有向圖卻不一定是一棵有向樹,請舉例說明?！局锌圃河嬎闼?1999 三、1 （5分）】35試給出下列有關并查集（mfsets）的操作序列的運算結果：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為根的樹的高度實現union(i,j),高度大者為高度小者的雙親； （5分)（3）按i和j為根的樹的結點個數實現union(i,j),結點個數大者為結點個數小者的雙親。（5分)【清華大學 2001 一、 (15分)】36證明：在任何一棵非空二叉樹中有下面的等式成立：葉結點的個數=二度結點的個數+1【天津大學 1999 四】37. 對于一個堆棧，若其入棧序列為1，2，3，n，不同的出入棧操作將產生不同的出棧序列。

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

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

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

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

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

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

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

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

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

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

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

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

26、 三、1 (6分)】（4）已知某二叉樹的后序遍歷和中序遍歷如下，構造出該二叉樹。后序遍歷序列： G D B E I H F C A 中序遍歷序列：D G B A E C H I F【廈門大學 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 試畫出此二分樹的結構。 【首都經貿大學 1998 二、1 （10分）】52假設一棵二叉樹的層次序列為ABCDEFGHIJ，中序序列DBGEHJACIF。請畫出這棵二叉樹?！疚錆h大學 2000 三、1】【東南大學 2000 一、1 （6

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

28、5用一維數組存放的一棵完全二叉樹；ABCDEFGHIJKL。請寫出后序遍歷該二叉樹的訪問結點序列。【西安電子科技大學1999計應用一、6 （5分）】56一棵二叉樹的先序、中序、后序序列如下，其中一部分未標出，請構造出該二叉樹。先序序列 ：_ _ C D E _ G H I _ K 中序序列 ：C B _ _ F A _ J K I G后序序列 ：_ E F D B _ J I H _ A 【廈門大學 2002 七、1 （6分)】類似本題的另外敘述有：（1）一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分為顯示出來。試求出空格處的內容，并畫出該二叉樹。先序序列: _ B F I C E H

29、 G中序序列：D K F I A E J C 后序序列： K F B H J G A 【西安電子科技大學2000計應用 五、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è)大學 2001 四、1 （5分)】（3）已知含有8個結點的一棵二叉樹，按先序、中序、后序進行遍歷后，有些結點序號不清楚如下圖示。要求構造出一棵符合條件的二叉樹。先根序遍歷 _ 2 3 _ 5 _ 7 8中根序遍歷

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

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

32、個結點的指針，是否可不用遞歸且不用棧來完成？請簡述原因?！疚鞅贝髮W 2001 三 6】63對于二叉樹T的兩個結點n1和n2，我們應該選擇樹T結點的前序、中序和后序中哪兩個序列來判斷結點n1必定是結點n2的祖先,并給出判斷的方法。不需證明判斷方法的正確性。【復旦大學 1999 五 (10分)】64設二叉樹的存儲結構如下(每題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為樹根結點的指針,LLINK、RLINK分別指向結點的左右子女,INFO為其數據域,請完成下列各題

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

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

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

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

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

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

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

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

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

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

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

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

45、叉樹來設計二進制的前綴編碼?！局猩酱髮W1999三、1 (3分)】83如果一棵huffman樹T有n0個葉子結點，那么，樹T有多少個結點，要求給出求解過程?！緩偷┐髮W 1999 四、 (10分)】84設T是一棵二叉樹，除葉子結點外，其它結點的度數皆為2，若 T中有6個葉結點，試問：（1）T樹的最大深度Kmax=?最小可能深度Kmin=?（2）T樹中共有多少非葉結點？(3) 若葉結點的權值分別為1,2,3,4,5,6。請構造一棵哈曼夫樹，并計算該哈曼夫樹的帶權路徑長度wpl?！颈本┼]電大學 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)結束條件top=0能否滿足？（2）若將IF top1改為IF top0是否正確？（3）若將結束條件改為top=1,其它不變，是否正確？（4）若僅將結束處條件改為(top=1)AND (stop=NIL),是否正確？（5）試找出二叉樹

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

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

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

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

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

52、叉鏈表結構。設二叉鏈表中鏈結點的構造為(lchild,data,rchild),根結點所在鏈結點的指針由T給出?！颈本┖娇蘸教齑髮W 1999 七、 (15分)】10. 二叉樹的動態(tài)二叉鏈表結構中的每個結點有三個字段：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)二叉鏈表是用數組作為存儲空間，每個數組元素存儲二叉樹的一個結點，也有三個字段：data，lchild，rchild。所不同的是，lchil

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