樹和二叉樹考研試題總結(jié)

本文格式為Word版，下載可任意編輯——樹和二叉樹考研試題總結(jié)第六章樹和二叉樹

一、選擇題

1．已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為()

A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE

2．算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（）

A．a(chǎn)b+cde/*B．a(chǎn)bcde/+*+C．a(chǎn)bcde/*++

D．a(chǎn)bcde*/++

3.設(shè)有一表示算術(shù)表達(dá)式的二叉樹（見下圖），它所表示的算術(shù)表達(dá)式是（）

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-G

4.設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1則T中的葉子數(shù)為（）

A．5B．6C．7D．85.在下述結(jié)論中，正確的是（）

①只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0;②二叉樹的度為2；③二叉樹的左右子樹可任意交換;

④深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度一致的滿二叉樹。A．①②③B．②③④C．②④D．①④6.設(shè)森林F對應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p,p的右子樹結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是（）

A．m-nB．m-n-1C．n+1D．條件不足，無法確定

7.樹是結(jié)點(diǎn)的有限集合，它（(1）)根結(jié)點(diǎn)，記為T。其余結(jié)點(diǎn)分成為m（m>0）個(gè)(（2）)的集合T1，T2，?，Ｔm，每個(gè)集合又都是樹，此時(shí)結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn)，Ti稱為T的子結(jié)點(diǎn)（1≤i≤m）。一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)稱為該結(jié)點(diǎn)的(（3）)。二叉樹與樹是兩個(gè)不同的概念，二叉樹也是結(jié)點(diǎn)的有限集合，它(（4）)根結(jié)點(diǎn)。可以把樹的根結(jié)點(diǎn)的層數(shù)定義為1，其他結(jié)點(diǎn)的層數(shù)等于其父結(jié)點(diǎn)所在層數(shù)加上1。令T是一棵二叉樹，Ki和Kj是T中子結(jié)點(diǎn)數(shù)小于2的結(jié)點(diǎn)中的任意兩個(gè)，它們所在的層數(shù)分別為λKi和λKj，當(dāng)關(guān)系式│λKi-λKj│≤1一定成立時(shí)，則稱T為一棵（(5)）。供選擇的答案：

（1）(4)A.有0個(gè)或1個(gè)B.有0個(gè)或多個(gè)C.有且只有一個(gè)D.有1個(gè)或1個(gè)以上（2）A.互不相交B.允許相交C.允許葉結(jié)點(diǎn)相交D.允許樹枝結(jié)點(diǎn)相交（3）A.權(quán)B.維數(shù)C.次數(shù)D.序

（5）A.飽滿樹B.查找樹C.平衡樹D.完全樹

8．若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（）A．9B．11C．15D．不確定

9．在一棵三元樹中度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為（）個(gè)

A．4B．5C．6D．7

10．設(shè)森林F中有三棵樹，第一，其次，第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2和M3。與森林F對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是（）。

A．M1B．M1+M2C．M3D．M2+M311．具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有（）個(gè)度為2的結(jié)點(diǎn)，

A．8B．9C．10D．ll

12．一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）

A．250B．500C．254D．505E．以上答案都不對

13.設(shè)給定權(quán)值總數(shù)有n個(gè)，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為()

A．不確定B．2nC．2n+1D．2n-114.有n個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（）。A．不確定B．2nC．2n+1D．2n-1

15．若度為m的哈夫曼樹中，其葉結(jié)點(diǎn)個(gè)數(shù)為n，則非葉結(jié)點(diǎn)的個(gè)數(shù)為（）。

A．n-1B．?n/m?-1C．?(n-1)/(m-1)?D．?n/(m-1)?-1E．?(n+1)/(m+1)?-1

16.有關(guān)二叉樹以下說法正確的是（）

A．二叉樹的度為2B．一棵二叉樹的度可以小于2

C．二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D．二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為217．二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為（）

II-1I-1I

A．2B．2-1C．2D．2-118.一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（）A．11B．10C．11至1025之間D．10至1024之間

19．一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹最少有()結(jié)點(diǎn)A．2hB．2h-1C．2h+1D．h+1

20．對于有n個(gè)結(jié)點(diǎn)的二叉樹,其高度為（）A．nlog2nB．log2nC．?log2n?|+1D．不確定21.一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹的樹高度（深度）是（）

A．?logn?+1B．logn+1C．?logn?D．logn-1

22．深度為h的滿m叉樹的第k層有（）個(gè)結(jié)點(diǎn)。(1=61．最優(yōu)二叉樹（哈夫曼樹）、最優(yōu)查找樹均為平均查找路徑長度最小的樹，其中對

最優(yōu)二叉樹，n表示（1），對最優(yōu)查找樹，n表示（2），構(gòu)造這兩種樹均（3）。

A．結(jié)點(diǎn)數(shù)B．葉結(jié)點(diǎn)數(shù)C．非葉結(jié)點(diǎn)數(shù)D．度為2的結(jié)點(diǎn)數(shù)E．需要一張n個(gè)關(guān)鍵字的有序表

F．需要對n個(gè)關(guān)鍵字進(jìn)行動(dòng)態(tài)插入G．需要n個(gè)關(guān)鍵字的查找概率表H．不需要任何前提

62．下述編碼中哪一個(gè)不是前綴碼（）。

A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001）

63．下面幾個(gè)符號串編碼集合中，不是前綴編碼的是（）。

A．{0,10,110,1111}B．{11,10,001,101,0001}C．{00,010,0110,1000}

D．{b,c,aa,ac,aba,abb,abc}

64.當(dāng)一棵有n個(gè)結(jié)點(diǎn)的二叉樹按層次從上到下，同層次從左到右將數(shù)據(jù)存放在一維數(shù)組A[l..n]中時(shí)，數(shù)組中第i個(gè)結(jié)點(diǎn)的左孩子為（）A．A[2i](2i==1)。31．必需把一般樹轉(zhuǎn)換成二叉樹后才能進(jìn)行存儲。32．完全二叉樹的存儲結(jié)構(gòu)尋常采用順序存儲結(jié)構(gòu)。

33．將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點(diǎn)沒有左子樹；34．在二叉樹中插入結(jié)點(diǎn)，則此二叉樹便不再是二叉樹了。

35．二叉樹是一般樹的特別情形。

36．樹與二叉樹是兩種不同的樹型結(jié)構(gòu)。37.非空的二叉樹一定滿足：某結(jié)點(diǎn)若有左孩子，則其中序前驅(qū)一定沒有右孩子

38．在任意一棵非空二叉排序樹，刪除某結(jié)點(diǎn)后又將其插入，則所得二叉排序樹與刪除前原二叉排序樹一致。39．度為二的樹就是二叉樹。

k-2

40．深度為k具有n個(gè)結(jié)點(diǎn)的完全二叉樹，其編號最小的結(jié)點(diǎn)序號為?2?+1。

41.下面二叉樹的定義只有一個(gè)是正確的，請?jiān)谡_的地方畫“√〞。

（1）它是由一個(gè)根和兩株互不相交的、稱為左子樹和右子樹的二叉樹組成。

i-1

（2）（a）在一株二叉樹的級i上，最大結(jié)點(diǎn)數(shù)是2（i≥1）

k-1

（b）在一棵深度為k的二叉樹中，最大結(jié)點(diǎn)數(shù)是2+1（k≥1）。（3）二叉樹是結(jié)點(diǎn)的集合，滿足如下條件：（a）它或者是空集；

（b）或者是由一個(gè)根和兩個(gè)互不相交的、稱為左子樹和右子樹的二叉樹組成。

42.在中序線索二叉樹中，每一非空的線索均指向其祖先結(jié)點(diǎn)。

43.線索二叉樹的優(yōu)點(diǎn)是便于是在中序下查找前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。44.二叉樹中序線索化后，不存在空指針域。45．霍夫曼樹的結(jié)點(diǎn)個(gè)數(shù)不能是偶數(shù)。46.一棵哈夫曼樹的帶權(quán)路徑長度等于其中所有分支結(jié)點(diǎn)的權(quán)值之和。

47.哈夫曼樹無左右子樹之分。

48．當(dāng)一棵具有n個(gè)葉子結(jié)點(diǎn)的二叉樹的WPL值為最小時(shí)，稱其樹為Huffman樹，且其二叉樹的形狀必是唯一的。

49．哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。

50.用鏈表（llink-rlink）存儲包含n個(gè)結(jié)點(diǎn)的二叉樹時(shí)，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)空指針。()

三、填空題

1．二叉樹由_(1)__，__(2)_，_(3)__三個(gè)基本單元組成。2．樹在計(jì)算機(jī)內(nèi)的表示方式有_(1)__，_(2)__，_(3)__。

3．在二叉樹中，指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是______。

4．中綴式a+b*3+4*（c-d）對應(yīng)的前綴式為__(1)_，若a=1，b=2，c=3，d=4，則后綴式db/cc*a-b*+的運(yùn)算結(jié)果為_(2)__。

5．二叉樹中某一結(jié)點(diǎn)左子樹的深度減去右子樹的深度稱為該結(jié)點(diǎn)的____。

6．具有256個(gè)結(jié)點(diǎn)的完全二叉樹的深度為______。

7．已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹有______個(gè)葉子結(jié)點(diǎn)。

8．深度為k的完全二叉樹至少有___(1)____個(gè)結(jié)點(diǎn)，至多有___(2)____個(gè)結(jié)點(diǎn)。

9．深度為H的完全二叉樹至少有_(1)__個(gè)結(jié)點(diǎn)；至多有_(2)__個(gè)結(jié)點(diǎn)；H和結(jié)點(diǎn)總數(shù)N之間的關(guān)系是(3)__。

10．在順序存儲的二叉樹中，編號為i和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是______。

11．在完全二叉樹中，編號為i和j的兩個(gè)結(jié)點(diǎn)處于同一層的條件是______。

12．一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹有__(1)_個(gè)度為1的結(jié)點(diǎn)、有__(2)_個(gè)分支（非終端）結(jié)點(diǎn)和__(3)_個(gè)葉子，該滿二叉樹的深度為_(4)__。14．在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為N0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為N2,則有N0=______15．設(shè)只含根結(jié)點(diǎn)的二叉樹的高度為0，則高度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為______,最小結(jié)點(diǎn)數(shù)為______。

16．設(shè)有N個(gè)結(jié)點(diǎn)的完全二叉樹順序存放在向量A[1:N]中，其下標(biāo)值最大的分支結(jié)點(diǎn)為

______。

17．高度為K的完全二叉樹至少有______個(gè)葉子結(jié)點(diǎn)。18．高度為8的完全二叉樹至少有______個(gè)葉子結(jié)點(diǎn)。19．已知二叉樹有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少是______。

20．一個(gè)有2023個(gè)結(jié)點(diǎn)的完全二叉樹的高度為______。21．設(shè)F是由T1,T2,T3三棵樹組成的森林,與F對應(yīng)的二叉樹為B,已知T1,T2,T3的結(jié)點(diǎn)數(shù)分別為n1,n2和n3則二叉樹B的左子樹中有__(1)_個(gè)結(jié)點(diǎn)，右子樹中有_(2)__個(gè)結(jié)點(diǎn)。

22．一個(gè)深度為k的，具有最少結(jié)點(diǎn)數(shù)的完全二叉樹按層次，（同層次從左到右）用自然數(shù)依此對結(jié)點(diǎn)編號，則編號最小的葉子的序號是__(1)_；編號是i的結(jié)點(diǎn)所在的層次號是_(2)__（根所在的層次號規(guī)定為1層）。

23．如某二叉樹有20個(gè)葉子結(jié)點(diǎn)，有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹的總結(jié)點(diǎn)數(shù)為______。

24．假使結(jié)點(diǎn)A有3個(gè)兄弟，而且B是A的雙親，則B的度是______。

25．高度為h的2-3樹中葉子結(jié)點(diǎn)的數(shù)目至多為______。

26．完全二叉樹中，結(jié)點(diǎn)個(gè)數(shù)為n，則編號最大的分支結(jié)點(diǎn)的編號為______。

27．設(shè)一棵完全二叉樹葉子結(jié)點(diǎn)數(shù)為k,最終一層結(jié)點(diǎn)數(shù)>2，則該二叉樹的高度為______。

28．對于一個(gè)具有n個(gè)結(jié)點(diǎn)的二元樹，當(dāng)它為一棵_(1)_二元樹時(shí)具有最小高度，當(dāng)它為一棵_(2)_時(shí)，具有最大高度。

29．具有N個(gè)結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲，共有______個(gè)空鏈域。30．8層完全二叉樹至少有______個(gè)結(jié)點(diǎn)，擁有100個(gè)結(jié)點(diǎn)的完全二叉樹的最大層數(shù)為______。

31．含4個(gè)度為2的結(jié)點(diǎn)和5個(gè)葉子結(jié)點(diǎn)的二叉樹，可有______個(gè)度為1的結(jié)點(diǎn)。

32．一棵樹T中，包括一個(gè)度為1的結(jié)點(diǎn)，兩個(gè)度為2的結(jié)點(diǎn)，三個(gè)度為3的結(jié)點(diǎn)，四個(gè)度為4的結(jié)點(diǎn)和若干葉子結(jié)點(diǎn)，則T的葉結(jié)點(diǎn)數(shù)為______。

33．n（n大于1）個(gè)結(jié)點(diǎn)的各棵樹中，其深度最小的那棵樹的深度是_(1)__。它共有_(2)__個(gè)葉子結(jié)點(diǎn)和_(3)__個(gè)非葉子結(jié)點(diǎn)，其中深度最大的那棵樹的深度是_(4)__，它共有_(5)__個(gè)葉子結(jié)點(diǎn)和_(6)__個(gè)非葉子結(jié)點(diǎn)。

34．每一棵樹都能唯一的轉(zhuǎn)換為它所對應(yīng)的二叉樹。若已知一棵二叉樹的前序序列是BEFCGDH，對稱序列是FEBGCHD，則它的后序序列是_(1)__。設(shè)上述二叉樹是由某棵樹轉(zhuǎn)換而成，則該樹的先根次序序列是_(2)__。35．先根次序周游樹林正好等同于按_(1)__周游對應(yīng)的二叉樹，后根次序周游樹林正好等同于按__(2)_周游對應(yīng)的二叉樹。

36．二叉樹結(jié)點(diǎn)的對稱序序列為A,B,C,D,E,F,G,后序序列為B,D,C,A,F,G,E,則該二叉樹結(jié)點(diǎn)的前序序列為_(1)__,則該二叉樹對應(yīng)的樹林包括_(2)__棵樹。37．二叉樹的先序序列和中序序列一致的條件是______。38．已知一棵二叉樹的前序序列為abdecfhg,中序序列為dbeahfcg，則該二叉樹的根為_(1)__，左子樹中有_(2)__，右子樹中有_(3)__。39．設(shè)二叉樹中每個(gè)結(jié)點(diǎn)均用一個(gè)字母表示，若一個(gè)結(jié)點(diǎn)的左子樹或右子樹為空，用．表示，現(xiàn)前序遍歷二叉樹，訪問的結(jié)點(diǎn)的序列為ABD.G...CE.H..F．．，則中序遍歷二叉樹時(shí)，訪問的結(jié)點(diǎn)序列為_(1)__;后序遍歷二叉樹時(shí)，訪問的結(jié)點(diǎn)序列為_(2)__。

40．已知二叉樹前序?yàn)锳BDEGCF，中序?yàn)镈BGEACF，則后序一定是____?！厩鄭u大學(xué)2000六、

3(2分）】

41．現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有_(1)__種不同的二叉樹可以得到這一遍歷結(jié)果，這些二叉樹分別是_(2)__。42．一個(gè)無序序列可以通過構(gòu)造一棵______樹而變成一個(gè)有序序列，構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程。43．利用樹的孩子兄弟表示法存儲，可以將一棵樹轉(zhuǎn)換為______。44．若一個(gè)二叉樹的葉子結(jié)點(diǎn)是某子樹的中序遍歷序列中的最終一個(gè)結(jié)點(diǎn)，則它必是該子樹的______序列中的最終一個(gè)結(jié)點(diǎn)。45．先根次序周游樹林正好等同于按______周游對應(yīng)的二叉樹；后根次序周游樹林正好等同于______周游對應(yīng)的二叉樹。46.在一棵存儲結(jié)構(gòu)為三叉鏈表的二叉樹中，若有一個(gè)結(jié)點(diǎn)是它的雙親的左子女，且它的雙親有右子女，則這個(gè)結(jié)點(diǎn)在后序遍歷中的后繼結(jié)點(diǎn)是______。

47．一棵左子樹為空的二叉樹在先序線索化后，其中的空鏈域的個(gè)數(shù)為：______。

48．具有n個(gè)結(jié)點(diǎn)的滿二叉樹，其葉結(jié)點(diǎn)的個(gè)數(shù)是______。

49．設(shè)一棵后序線索樹的高是50，結(jié)點(diǎn)x是樹中的一個(gè)結(jié)點(diǎn)，其雙親是結(jié)點(diǎn)y,y的右子樹高度是31，x是y的左孩子。則確定x的后繼最多需經(jīng)過______中間結(jié)點(diǎn)（不含后繼及x本身）

50．線索二元樹的左線索指向其______，右線索指向其______。

51．設(shè)y指向二叉線索樹的一葉子，x指向一待插入結(jié)點(diǎn)，現(xiàn)x作為y的左孩子插入，樹中標(biāo)志域?yàn)閘tag和rtag，并規(guī)定標(biāo)志為1是線索，則下面的一段算法將x插入并修改相應(yīng)的線索，試補(bǔ)充完整：(lchild,rchild分別代表左，右孩子)

x^.ltag:=(1)___;x^.lchild:=(2)___;y^.ltag:=(3)___;y^.lchild:=(4)___;x^.rtag:=(5)___;x^.rchild:=(6)___;

IF(x^.lchildNIL)AND(x^lchild^.rtag=1)THENx^.lchild^.rchild:=(7)___;52．哈夫曼樹是______。

53．若以{4，5，6，7，8}作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是______。

54．有數(shù)據(jù)WG={7，19，2，6，32，3，21，10}，則所建Huffman樹的樹高是_(1)__，帶權(quán)路徑長度WPL為_(2)__。55．有一份電文中共使用6個(gè)字符:a,b,c,d,e,f,它們的出現(xiàn)頻率依次為2,3,4,7,8,9，試構(gòu)造一棵哈夫曼樹，則其加權(quán)路徑長度WPL為_(1)__，字符c的編碼是_(2)__。

56．設(shè)n0為哈夫曼樹的葉子結(jié)點(diǎn)數(shù)目，則該哈夫曼樹共有______個(gè)結(jié)點(diǎn)。

57．①二叉樹用來表示表達(dá)式，因?yàn)樾枰４娓髯訕涞闹担薷亩鏄涞慕Y(jié)點(diǎn)結(jié)構(gòu)為(Lchild,Data,Val,Rchild)。其中Lchild,Rchild的意義同前，Val用來存放以該結(jié)點(diǎn)為根的子樹的值，值的類型依具體情況而定。為了簡便起見，算法假定所考慮的表達(dá)式只有+，-，*，/四種二目運(yùn)算，且已表示成相應(yīng)的二叉樹。算法所計(jì)算的表達(dá)式值放在根結(jié)點(diǎn)的Val域中。

PROCPostorder-eval(t:ptrType)BEGINIF(t!=NULL)

BEGIN(1)_______;(2)_______;

CASEt^.data:

‘+’:t^.Val:=t^.Lchild^.Val+t^.Rchild^.Val;BREAK;‘-’:t^.Val:=t^.Lchild^.Val-t^.Rchild^.Val;BREAK;‘*’:t^.Val:=t^.Lchild^.Val*t^.Rchild^.Val;BREAK;‘/’:t^.Val:=t^.Lchild^.Val/t^.Rchild^.Val;BREAK;otherwise:(3)___;BREAK;ENDCASEENDEND;

②PROCDelete(x:datatype,A:tree)BEGINtempA:=(4)___;

WHILE(tempA^.Item!=x)AND(tempA!=NULL)DO

IF(xrchild=(2)___;(3)___=q;

if(p->lchild)(4)___;if(p->rchild)(5)___;}

}}//

60．設(shè)t是給定的一棵二叉樹，下面的遞歸程序count(t)用于求得:二叉樹t中具有非空的左,右兩個(gè)兒子的結(jié)點(diǎn)個(gè)數(shù)N2;只有非空左兒子的個(gè)數(shù)NL;只有非空右兒子的結(jié)點(diǎn)個(gè)數(shù)NR和葉子結(jié)點(diǎn)個(gè)數(shù)N0。N2、NL、NR、N0都是全局量，且在調(diào)用count(t)之前都置為0.typedefstructnode

{intdata;structnode*lchild,*rchild;}node;intN2,NL,NR,N0;voidcount(node*t)

{if(t->lchild!=NULL)if(1)___N2++;elseNL++;elseif(2)___NR++;else(3)__;

if(t->lchild!=NULL)(4)____;if(t->rchild!=NULL)(5)____;}/*callform:if(t!=NULL)count(t);*/

61．下面是求二叉樹高度的類PASCAL（注：編者略）及類C寫的遞歸算法試補(bǔ)充完整[說明]（1）考生可根據(jù)自己的狀況任選一個(gè)做（都選不給分)

（2）二叉樹的兩指針域?yàn)閘child與rchild,算法中p為二叉樹的根，lh和rh

分別為以p為根的二叉樹的左子樹和右子樹的高，hi為以p為根的二叉樹的高，hi最終返回。

height(p)

{if((1)___)

{if(p->lchild==null)lh=(2)_______;elselh=(3)_______;

if(p->rchild==null)rh=(4)_______;elserh=(5)_______;if(lh>rh)hi=(6)__；elsehi=(7)_______;}

elsehi=(8)_______;returnhi;

}//

62．二叉樹以鏈方式存儲，有三個(gè)域，數(shù)據(jù)域data，左右孩子域lchild,rchild。樹根由

tree指向?，F(xiàn)要求按層次從上到下，同層次從左到右遍歷樹。下面算法中用到addx(p)，將指針p進(jìn)隊(duì)，delx()將隊(duì)頭元素返回并退隊(duì)，notempty在隊(duì)不空時(shí)返回true，否則為false，將算法補(bǔ)充完整:PROCprocessnode(p);

IF(1)_______THEN[write(p＾.data);(2)_______]ENDP;

PROCtrave(tree);

write(tree＾.data);(3)_______;WHILEnotempty()DO

[r:=delx();processnode(r＾.lchild);processnode((4)_______)]ENDP;63閱讀以下程序說明和程序，填充程序中的______本程序完成將二叉樹中左、右孩子交換的操作。交換的結(jié)果如下所示（編者略）。本程序采用非遞歸的方法，設(shè)立一個(gè)堆棧stack存放還沒有轉(zhuǎn)換過的結(jié)點(diǎn)，它的棧頂指針為tp。交換左、右子樹的算法為：（1）把根結(jié)點(diǎn)放入堆棧。

（2）當(dāng)堆棧不空時(shí)，取出棧頂元素，交換它的左、右子樹，并把它的左、右子樹分別入棧。

（3）重復(fù)（2）直到堆棧為空時(shí)為止。typedefstructnode*tree;

structnode{intdata;treelchild,rchild;}exchange(treet)

{treer,p;treestack[500];inttp=0;(1)_______while(tp>=0)

{(2)_______if((3)_______)

{r=p->lchild;p->lchild=p->rchild;p->rchild=r

stack[(4)_______]=p->lchild;stack[++tp]=p->rchild;}

}}

64．下面使用類pascal語言寫的對二叉樹進(jìn)行操作的算法，請細(xì)心閱讀

TYPEpointer=^tnodetp;

tnodetp=RECORDdata:char;llink,rlink:pointer；END;linkstack=^linknodet;

linknodet=RECORDdata:pointer；next;linkstack；END;PROCunknown(VARt:pointer);VARp,temp：pointer;BEGINp:=t;

IFpNILTHEN

[temp:=p^.llink；p^.llink:=p^.rlink;；p^.rlink:=temp;unknown(p^.llink);unknown(p^.rlink);]

END;

①指出該算法完成了什么功能

②用棧將以上算法改為非遞歸算法unknown1,其中有若干語句或條件空缺請?jiān)诳杖碧幪顚懮线m當(dāng)?shù)恼Z句或條件

PROCinistack(VARs:linkstack);(1)_______;s^.next:=NIL;ENDP;

FUNCempty(s:linkstack):boolean;

IF(2)_______THENempty:=trueELSEempty:=false;ENDF;

FUNCgettop(s:linkstack):pointer;gettop:=(3)_______;ENDF;

FUNCpop(VARs:linkstack)：pointer;VARp:linkstack;

pop:=s^.next^.data;p:=s^.next;(4)_______；(5)_______;ENDF;

PROCpush(VARs:linkstack;x:pointer);VARp:linkstack;

new(p);p^.data:=x;(6)_______;s^.next:=p;ENDP;

PROCunknown1(VARt:pointer);

VARp,temp:pointer;finish:boolean;BEGIN

inistack(s);finish:=false;p:=t;

REPEAT

WHILEpNILDO

[temp:=p^.llink;p^.llink:=p^.rlink;p^.rlink:=temp;(7)_______;p:=p^.llink;];

IF(8)____THEN[p:=gettop(s);temp;=pop(s);]ELSE(9)_______

UNTIL(10)___

ENDP;

65．具有n個(gè)結(jié)點(diǎn)的完全二叉樹，已經(jīng)順序存儲在一維數(shù)組A[1..n]中，下面算法是將A中順序存儲變?yōu)槎骀湵泶鎯Φ耐耆鏄?。請?zhí)钊脒m當(dāng)?shù)恼Z句在下面的_______上，完成上述算法。

TYPEar=ARRAY[1..n]OFdatatype;

pointer=RECORDdata:datatype;lchild,rchild:pointer;END;PROCEDUREbtree(VARa:ar;VARp:pointer);

VARi:integer;

PROCEDUREcreatetree(VARt:pointer;i:integer)BEGIN(1)_______;t^.data=a[i];

IF(2)_____THENcreattree((3)_______)ELSEt^.lchild:=NIL;IF(4)_____THENcreatetree((5)_______)ELSEt^.rchild:=NIL;END;BEGIN

j:=(6)__;createtree(p,j)

>ch;//從ins順序讀入一個(gè)字符

while(ch!=‘#’){//逐個(gè)字符處理，直到遇到‘#’為止switch(ch){

case‘(’:(1)___；k=1;break;case‘)’:pop(s);break;case’,’:(2)___；break;

default:p=newBinTreeNode;(3)____;p->leftChild=NULL;p->rightChild=NULL;

if(BT==NULL)(4)___；elseif(k==1)top(s)->leftChild=p;

elsetop(s)->rightChild=p;

}

(5)____;}}

67.判斷帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L是否對稱相等的算法如下所示，請?jiān)趧澗€處填上正確的語句

FUNCTIONequal(l:pointer):boolean;VARp,q:pointer;result:Boolean;

BEGINresult=true;p:=l^.link;q:=l^.pre;WHILE(pq)AND((1)_______)DO

IFp^.data=q^.dataTHENBEGIN(2)___;(3)____;END；ELSEresult=false;return(result);

END;

68．下列是先序遍歷二叉樹的非遞歸子程序，請閱讀子程序（C語言與PASCAL語言過程功

能完全相同，任選其一），填充空格，使其成為完整的算法。

C語言函數(shù)：voidexample(b)btree*b;{btree*stack[20],*p；inttop;if(b!=null){top=1;stack[top]=b;while(top>0){p=stack[top];top--;printf(“%d〞,p->data);if(p->rchild!=null){(1)___;(2)___;}if(p->lchild!=null)(3)___;(4)__;}}}}PASCAL語言過程PROCEDUREexample(b:btree);VARstack:ARRAY[1..20]OFbtree;top:integer;p:btree;BEGINIFbNILTHENBEGINtop:=1;stack[top]:=b;WHILEtop>0DOBEGINp:=stack[top];top:=top-1;write(p^.data);IFp^.rchildNILTHENBEGIN(1)__;(2)_;END;IFp^,lchildNILTHENBEGIN(3)__;4)__;ENDENDENDEND;

69．下述是一個(gè)由二叉樹的前序序列和中序序列構(gòu)造該二叉樹的算法，其中，數(shù)組A[1..n]存放前序序列，數(shù)組B[1..n]存放中序序列，s為根結(jié)點(diǎn)指針，i,j為樹s的前序序列在A[1..n]中的開始位置和終止位置，x,y為樹s的中序序列在B[1..n]中的開始位置和終止位置。所生成的二叉樹采用二叉鏈表存儲結(jié)構(gòu)，其結(jié)點(diǎn)的形式為（lchild,data,rchild）。請?jiān)谒惴ǖ目湛蛑刑钊脒m當(dāng)語句，使其成為一個(gè)完整的算法。

PROCEDUREcreatBT(i,j,x,y:integer;VARs:link);VARk,L:integer;

BEGINs:=NIL;IF(1)__THEN

BEGINnew(s);s^.data:=a[i];k:=x;WHILE(2)_______DOk:=k+1;L:=(3)____;IFk=xTHENs^.lchild:=NIL;ELSE(4)_______;IFk=yTHENs^.rchild:=NIL;ELSE(5)_______；END

END;

70．已知中序遍歷bt所指二叉樹算法如下，s為存儲二叉樹結(jié)點(diǎn)指針的工作棧，請?jiān)趧澗€處填入一條所缺語句。

PROCinorder(bt:bitreptr);inistack(s);(1)_______;WHILENOTempty(s)DO

[WHILEgettop(s)NILDOpush(s,gettop(s)↑.lchild);(2)_______;

IFNOTempty(s)THEN[visit(gettop(s)^);p:=pop(s);(3)_______]]

ENDP;{inorder}

71．以下程序是二叉鏈表樹中序遍歷的非遞歸算法，請?zhí)羁帐怪晟?。二叉樹鏈表的結(jié)點(diǎn)類型的定義如下：

typedefstructnode/*C語言/

{chardata;structnode*lchild,*rchild;}*bitree;

voidvst(bitreebt)/*bt為根結(jié)點(diǎn)的指針*/{bitreep;p=bt;initstack(s);/*初始化棧s為空棧*/

while(p||!empty(s))/*棧s不為空*/if(p){push(s,p);(1)___;}/*P入棧*/

else{p=pop(s);printf(“%c”,p->data);(2)____;}/*棧頂元素出棧*/}

72．二叉樹存儲結(jié)構(gòu)同上題，以下程序?yàn)榍蠖鏄渖疃鹊倪f歸算法，請?zhí)羁胀晟浦?/p>

intdepth(bitreebt)/*bt為根結(jié)點(diǎn)的指針*/{inthl,hr;

if(bt==NULL)return((1)___);

hl=depth(bt->lchild);hr=depth(bt->rchild);if((2)___)(3)_____；return(hr+1);

}

73．n個(gè)結(jié)點(diǎn)的完全二叉樹存儲在數(shù)組a中，下面為非遞歸的先序遍歷算法。PROCpreorder(a);BEGINtop:=0;t:=1;

WHILE(t0THENBEGINt:=s[top]*2+1;top:=(3)__;END;END;

END;

74．后序遍歷二叉樹的非遞歸算法，bt是二叉樹的根，S是一個(gè)棧，maxsize是棧的最大容量。

TYPEbitreptr=^bnodetp;

bnodetp=RECORDdata:datatype;lchild,rchild:bitreptrEND;

TYPEstacktyp=RECORDdata:ARRAY[1..maxsize]OFbitreptr；top：0..maxsize；END；

PROCEDUREposterorder（bt：bitreptr）；BEGINS.top:=0；p:=bt；REPEAT

WHILEpNILDOBEGINS.top:=S.top+1;IFS.top>maxsizeTHENstackfull

ELSEBEGINS.data[S.top]:=p；(1)__;

END

END;

IFS.data[S.top]^.rchildNILTHEN(2)__

ELSEBEGINREPEATwrite(S.data[S.top]^.data);S.top=S.top-1;UNTILS.top=0ORS.data[S.top]^.rchildS.data[S.top+1];IFS.data[S.top]^.rchildS.data[S.top+1]THEN(3)__;

END；

UNTIL(4)___;

END；75．由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹，下面程序的作用是實(shí)現(xiàn)由已知某二叉樹的前序遍歷和中序遍歷序列，生成一棵用二叉鏈表表示的二叉樹并打印出后序遍歷序列，請寫出程序所缺的語句。#defineMAX100typedefstructNode

{charinfo;structNode*llink,*rlink;}TNODE;charpred[MAX],inod[MAX];main(intargc,int**argv){TNODE*root;

if(argcinfo=(1)_______;

for((2)_______;rposllink=restore(ppos+1,(4)_______,k);

ptr->rlink=restore((5)_______+k,rpos+1,n-1-k);returnptr;}

postorder(TNODE*ptr){if(ptr=NULL)return;postorder(ptr->llink);postorder(ptr->rlink);printf(“%c〞,ptr->info);

}76．已給如下關(guān)于二叉樹的類型說明：

TYPEtree=^node;

node=RECORDdata:integer;left,right:treeEND;以下過程實(shí)現(xiàn)對二叉樹t前序遍歷的非遞歸算法：

PROCEDUREpreorder(t:tree);

VARstack:ARRAY[1..100]OFtree;nd:tree;top:integer;BEGINtop:=1;stack[top]:=t;WHILE(1)___DO

BEGINnd:=stack[top];top:=top-1;write(nd^.data);

IF(nd^.rightNIL)THENBEGINtop:=top+1;(2)___END;

IF(3)___THENBEGIN(4)；stack[top]:=nd^.left；ENDEND

END;

77．下面是中序線索樹的遍歷算法，樹有頭結(jié)點(diǎn)且由指針thr指向。樹的結(jié)點(diǎn)有五個(gè)域，分

別為數(shù)據(jù)域data，左、右孩子域lchild、rchild和左、右標(biāo)志域ltag,rtag。規(guī)定，標(biāo)志域?yàn)?是線索，O是指向孩子的指針。inordethread(thr){p=thr->lchild;while((1)______)

{while((2)_____)p=(3)___;

printf(p->data);

while((4)_________){p=(5)___；printf(p->data);}p=(6)_;}

}78．下面的算法在中序線索樹中找由指針?biāo)附Y(jié)點(diǎn)的后繼并由指針指向該后繼結(jié)點(diǎn)，試補(bǔ)充完整（線索樹的結(jié)點(diǎn)有五個(gè)域data,lchild,rchild,左、右標(biāo)志域ltag、rtag，并規(guī)定標(biāo)志0指向孩子，1指向線索。

PROCinorder_next(p);(1)__;

IFp＾.rtag=0THENWHILE(2)____DOq:=(3)___；return(q)ENDP;

79．線索二叉樹有數(shù)據(jù)域data，左右孩子域lchild和rchild，左右標(biāo)志ltag及rtag，規(guī)定標(biāo)志為1對應(yīng)的孩子域是線索，0則為指向孩子的指針。規(guī)定在儲存線索二叉樹時(shí)，完成下面中序線索化過程。（存儲線索二叉樹，不增加頭結(jié)點(diǎn)，只在原有的由tree指向的二叉樹中增加線索，此處也不考慮c語言的具體語法與約定，線索化前所有的標(biāo)志tag都是0）。/*pre是同tree類型一致的指針，初值是null*/thread_inorder(tree)

{if(tree!=null)

{thread_inorder((1)____);

if(tree->lchild==(2)______){tree->ltag=1;tree->lchild=pre;}if((3)___==null){(4)_______;(5)_______;}

pre=p;thread-inorder((6)_______);}

}

80．如下的算法分別是后序線索二叉樹求給定結(jié)點(diǎn)node的前驅(qū)結(jié)點(diǎn)與后繼結(jié)點(diǎn)的算法，請?jiān)谒惴崭裉幪钌险_的語句。設(shè)線索二叉樹的結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)為(lflag,left,data,right,rflag)，其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驅(qū)；rflag=0，right指向其右孩子，rflag=1，right指向其后繼。prior(node,x)

{if(node!=null)

if((1)_____)*x=node->right;else*x=node->left;}

next(bt,node,x)/*bt是二叉樹的樹根*/{(2)_____;

if(node!=bt(4)_______;while(*x==node);*x=t;}}

四、應(yīng)用題

1．從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。

2．樹和二叉樹之間有什么樣的區(qū)別與聯(lián)系？

3．請分析線性表、樹、廣義表的主要結(jié)構(gòu)特點(diǎn)，以及相互的差異與關(guān)聯(lián)。

4.設(shè)有一棵算術(shù)表達(dá)式樹，用什么方法可以對該樹所表示的表達(dá)式求值？5．將算術(shù)表達(dá)式（（a+b）+c*(d+e)+f）*(g+h)轉(zhuǎn)化為二叉樹。

6.一棵有n(n>0)個(gè)結(jié)點(diǎn)的d度樹,若用多重鏈表表示,樹中每個(gè)結(jié)點(diǎn)都有d個(gè)鏈域,則在表示該樹的多重鏈表中有多少個(gè)空鏈域?為什么?7.一棵二叉樹中的結(jié)點(diǎn)的度或?yàn)?或?yàn)?，則二叉樹的枝數(shù)為2(n0-1)，其中n0是度為0的結(jié)點(diǎn)的個(gè)數(shù)。

類似此題的另外表達(dá)有：

（1）若二叉樹中度為1的結(jié)點(diǎn)數(shù)為0，則該二叉樹的總分支數(shù)為2（n0-1），其中n0為葉結(jié)點(diǎn)數(shù)。

8．一個(gè)深度為L的滿K叉樹有以下性質(zhì)：第L層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有K棵非空子樹，假使按層次順序從1開始對全部結(jié)點(diǎn)進(jìn)行編號，求：

1）各層的結(jié)點(diǎn)的數(shù)目是多少？2）編號為n的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號是多少？

3）編號為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)（若存在）的編號是多少？

4）編號為n的結(jié)點(diǎn)有右兄弟的條件是什么？假使有，其右兄弟的編號是多少？請給出計(jì)算和推導(dǎo)過程。類似此題的另外表達(dá)有：

（1）一棵高度為h的滿k叉樹有如下性質(zhì)：根據(jù)結(jié)點(diǎn)所在層次為0；第h層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)；其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹，假使按層次自頂向下，同一層自左向右,順序從1開始對全部結(jié)點(diǎn)進(jìn)行編號，試問：

1)各層的結(jié)點(diǎn)個(gè)數(shù)是多少?(3分)2)編號為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號是多少?(3分)

3)編號為i的結(jié)點(diǎn)的第m個(gè)孩子結(jié)點(diǎn)（若存在）的編號是多少？（3分）

4)編號為i的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟結(jié)點(diǎn)的編號是多少？（3分)9．證明任一結(jié)點(diǎn)個(gè)數(shù)為n的二叉樹的高度至少為O(logn).10．有n個(gè)結(jié)點(diǎn)并且其高度為n的二叉樹的數(shù)目是多少?

11．已知完全二叉樹的第七層有10個(gè)葉子結(jié)點(diǎn)，則整個(gè)二叉樹的結(jié)點(diǎn)數(shù)最多是多少？

12．高度為10的二叉樹，其結(jié)點(diǎn)最多可能為多少？

13．任意一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹，已知它有m個(gè)葉子結(jié)點(diǎn)，試證明非葉子結(jié)點(diǎn)有（m-1）個(gè)度為2，其余度為1。

14.已知A[1..N]是一棵順序存儲的完全二叉樹，如何求出A[i]和A[j]的最近的共同祖先？

15．給定K(K>=1),對一棵含有N個(gè)結(jié)點(diǎn)的K叉樹（N＞０）、請?zhí)接懫淇赡艿淖畲蟾叨群妥钚「叨取?/p>

16．已知一棵滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)為20到40之間的素?cái)?shù)，此二叉樹的葉子結(jié)點(diǎn)有多少個(gè)？17．一棵共有n個(gè)結(jié)點(diǎn)的樹，其中所有分支結(jié)點(diǎn)的度均為K，求該樹中葉子結(jié)點(diǎn)的個(gè)數(shù)。

18．如在內(nèi)存中存放一個(gè)完全二叉樹，在樹上只進(jìn)行下面兩個(gè)操作：（1）尋覓某個(gè)結(jié)點(diǎn)雙親（2）尋覓某個(gè)結(jié)點(diǎn)的兒子；

請問應(yīng)當(dāng)用何種結(jié)構(gòu)來存儲該二叉樹？

19．求含有n個(gè)結(jié)點(diǎn)、采用順序存儲結(jié)構(gòu)的完全二叉樹中的序號最小的葉子結(jié)點(diǎn)的下標(biāo)。要求寫出簡要步驟。

20．設(shè)二叉樹T中有n個(gè)頂點(diǎn)，其編號為1，2，3，?,n,若編號滿足如下性質(zhì)：（1）T中任一頂點(diǎn)v的編號等于左子樹中最我號減1；

（2）對T中任一頂點(diǎn)v,其右子樹中最我號等于其左子樹中的最大編號加1。試說明對二叉樹中頂點(diǎn)編號的規(guī)則（按何種順序編號）。

21．若一棵樹中有度數(shù)為1至m的各種結(jié)點(diǎn)數(shù)為n1,n2,?,nm(nm表示度數(shù)為m的結(jié)點(diǎn)個(gè)數(shù))請推導(dǎo)出該樹中共有多少個(gè)葉子結(jié)點(diǎn)n0的公式。

22．若一棵完全二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)為n,且最底層結(jié)點(diǎn)數(shù)≧2，則此二叉樹的深度H=？

23．已知完全二叉樹有30個(gè)結(jié)點(diǎn)，則整個(gè)二叉樹有多少個(gè)度為0的結(jié)點(diǎn)？

24．在一棵表示有序集S的二叉探尋樹(binarysearchtree)中,任意一條從根到葉結(jié)點(diǎn)的路徑將S分為3部分：在該路徑左邊結(jié)點(diǎn)中的元素組成的集合Sl；在該路徑上的結(jié)點(diǎn)中的元素組成的集合S2；在該路徑右邊結(jié)點(diǎn)中的元素組成的集合S3。S=S1∪S2∪S3。若對于任意的a∈Sl,b∈S2，c∈S3是否總有a≤b≤c?為什么?25．試證明,在具有n(n>=1)個(gè)結(jié)點(diǎn)的m次樹中,有n(m-1)+1個(gè)指針是空的。

26．對于任何一棵非空的二叉樹,假設(shè)葉子結(jié)點(diǎn)的個(gè)數(shù)為n0,而次數(shù)為2的結(jié)點(diǎn)個(gè)數(shù)為n2,請給出n0和n2之間所滿足的關(guān)系式n0=f(n2).要求給出推導(dǎo)過程。27．對于任意一棵非空的二叉樹T，我們用n0表示T中葉子結(jié)點(diǎn)的個(gè)數(shù)，用n2表示T中有兩棵非空子樹的結(jié)點(diǎn)的個(gè)數(shù)。（1）給出n0和n2所滿足的關(guān)系式。（2）證明你在（1）中給出的關(guān)系式成立。

28．試求有n個(gè)葉結(jié)點(diǎn)的非滿的完全二叉樹的高度;29．對于具有n個(gè)葉子結(jié)點(diǎn)，且所有非葉子結(jié)點(diǎn)都有左右孩子的二叉樹，(1)試問這種二叉樹的結(jié)點(diǎn)總數(shù)是多少？（5分）

(2)試證明=1。其中:li表示第i個(gè)葉子結(jié)點(diǎn)所在的層號(設(shè)根結(jié)點(diǎn)所在層號為1)。

(10分)

30．假設(shè)高度為H的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，問此類二叉樹中的結(jié)點(diǎn)數(shù)可能達(dá)到的最大值和最小值各為多少？

31．一棵滿k叉樹，按層次遍歷存儲在一維數(shù)組中，試計(jì)算結(jié)點(diǎn)下標(biāo)的u的結(jié)點(diǎn)的第i個(gè)孩子的下標(biāo)以及結(jié)點(diǎn)下標(biāo)為v的結(jié)點(diǎn)的父母結(jié)點(diǎn)的下標(biāo)。

32．二叉樹有n個(gè)頂點(diǎn)，編號為1，2，3，?，n，設(shè)：*T中任一頂點(diǎn)V的編號等于左子樹中最我號減1；

*T中任一頂點(diǎn)V的右子樹中的最我號等于其左子樹中的最大編號加1；試描繪該二叉樹。

33．設(shè)T是具有n個(gè)內(nèi)結(jié)點(diǎn)的擴(kuò)展二叉樹，I是它的內(nèi)路徑長度，E是它的外路徑長度。（1）試?yán)脷w納法證明E=I+2n,n>=0.（5分)

（2）利用（1）的結(jié)果試說明：成功查找的平均比較次數(shù)s與不成功查找的平均比較次數(shù)u之間的關(guān)系可用公式表示s=(1+1/n)u-1,n>=1。

34．一棵非空的有向樹中恰有一個(gè)頂點(diǎn)入度為0,其它頂點(diǎn)入度為1,但一個(gè)恰有一個(gè)頂點(diǎn)入度為0,其它頂點(diǎn)入度為1的有向圖卻不一定是一棵有向樹,請舉例說明。

35．試給出以下有關(guān)并查集（mfsets）的操作序列的運(yùn)算結(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,16),union(1,3),union(1,14).

(union是合并運(yùn)算，在以前的書中命名為merge)

要求

（1）對于union(i,j),以i作為j的雙親；（5分)（2）按i和j為根的樹的高度實(shí)現(xiàn)union(i,j),高度大者為高度小者的雙親；（5分)（3）按i和j為根的樹的結(jié)點(diǎn)個(gè)數(shù)實(shí)現(xiàn)union(i,j),結(jié)點(diǎn)個(gè)數(shù)大者為結(jié)點(diǎn)個(gè)數(shù)小者的雙親。（5分)

36．證明：在任何一棵非空二叉樹中有下面的等式成立：葉結(jié)點(diǎn)的個(gè)數(shù)=二度結(jié)點(diǎn)的個(gè)數(shù)+1

37.對于一個(gè)堆棧，若其入棧序列為1，2，3，?，n，不同的出入棧操作將產(chǎn)生不同的出棧序列。其出棧序列的個(gè)數(shù)正好等于結(jié)點(diǎn)個(gè)數(shù)為n的二叉樹的個(gè)數(shù)，且與不同形態(tài)的二叉樹一一對應(yīng)。請簡要表達(dá)一種從堆棧輸入（固定為1，2，3??n）/輸出序列對應(yīng)一種二叉樹形態(tài)的方法，并以入棧序列1，2，3（即n=3）為例加以說明。

38.假使給出了一個(gè)二叉樹結(jié)點(diǎn)的前序序列和對稱序序列，能否構(gòu)造出此二叉樹?若能，請證明之。若不能，請給出反例。假使給出了一個(gè)二叉樹結(jié)點(diǎn)的前序序列和后序序列，能否構(gòu)造出此二叉樹?若能，請證明之。若不能，請給出反例。類似此題的另外表達(dá)有：（1）二叉樹的中序與后序序列能唯一地定義一棵二叉樹嗎?這里所指序列中的符號代表樹結(jié)點(diǎn)中的標(biāo)識符嗎？二叉樹的前序與后序序列能唯一地定義一棵二叉樹嗎?為什么?

39．試證明:同一棵二叉樹的所有葉子結(jié)點(diǎn)，在前序序列。對稱序序列以及后序序列中都按一致的相對位置出現(xiàn)（即先后順序一致），例如前序abc,后序bca對稱序bac。

40.由二叉樹的中序序列及前序序列能唯一的建立二叉樹，試問中序序列及后序序列是否也能唯一的建立二叉樹，不能則說明理由，若能對中序序列DBEAFGC和后序序列DEBGFCA構(gòu)造二叉樹。

41.證明，由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。設(shè)一棵二叉樹的前序序列為ABDGECFH，中序序列為：DGBEAFHC。試畫出該二叉樹。

類似此題的另外表達(dá)有：

(1)證明：由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。

（2）證明：由二叉樹的中序遍歷序列和后序遍歷序列可唯一地確定出該二叉樹。

（3）二叉樹已知其中序掃描序列和后序掃描序列如何確定這一棵二叉樹,并舉例說明.

42．試證明：僅僅已知一棵二叉樹的后序遍歷序列和先序遍歷序列，不能唯一地確定這棵二叉樹。

類似此題的另外表達(dá)有：

(1)由二叉樹的前序遍歷和后序遍歷結(jié)果能否唯一確定一棵二叉樹？解釋你的論斷。

(2)假定某二叉樹的前序遍歷序列為ABCDEFGHIJ,后序遍歷序列為CEFDBJIHGA,據(jù)此兩個(gè)序列能否唯一確定此二叉樹?若不能,試畫出兩樣具有同樣上述遍歷序列的二叉樹.

43.①試找出滿足以下條件的二叉樹

1）先序序列與后序序列一致2）中序序列與后序序列一致

3）先序序列與中序序列一致4）中序序列與層次遍歷序列一致②已知一棵二叉樹的中序序列和后序序列分別為DBEAFIHCG和DEBHIFGCA，畫出這棵二叉樹。

類似此題的另外表達(dá)有：

（1）試畫出在先根次序和中根次序下結(jié)點(diǎn)排列順序皆一致的所有類型的二叉樹形。

試畫出在先根次序和后根次序下結(jié)點(diǎn)排列順序皆一致的所有類型的二叉樹形。

（2）找出所有的二叉樹，其結(jié)點(diǎn)在以下兩種遍歷下恰好都有同樣的遍歷序列。

1）先序遍歷和中序遍歷2）先序遍歷和后序遍歷（3）找出所有的二叉樹，其結(jié)點(diǎn)在以下兩種遍歷下，恰好都是以同樣的順序出現(xiàn)：

1）前序遍歷和中序遍歷。2）前序遍歷和后序遍歷。

（4）試找出分別滿足以下條件的所有二叉樹。

1）先序序列和中序序列一致2）中序序列和后序序列一致3）先序序列和后序序列一致（5）找出所有滿足以下條件的二叉樹：

1）它們在先序遍歷和中序遍歷時(shí)，得到的結(jié)點(diǎn)訪問序列一致；2）它們在后序遍歷和中序遍歷時(shí)，得到的結(jié)點(diǎn)訪問序列一致；3）它們在先序遍歷和后序遍歷時(shí)，得到的結(jié)點(diǎn)訪問序列一致；

44．將以下由三棵樹組成的森林轉(zhuǎn)換為二叉樹。（只要求給出轉(zhuǎn)換結(jié)果）

45.閱讀以下說明和流程圖，回復(fù)問題（1）和問題（2）。

說明：流程圖是用來實(shí)現(xiàn)中序遍歷，二叉樹存放在數(shù)組tree中，每個(gè)數(shù)組元素存放樹中一個(gè)結(jié)點(diǎn)，每個(gè)

結(jié)點(diǎn)的形式為（值，左指針，右指針），分別用tree[i].v，tree[i].l，tree[i].r來表示第i個(gè)結(jié)點(diǎn)的值，左指針，右指針，其中左，右指針的值為所指結(jié)點(diǎn)在數(shù)組中的下標(biāo)，若指針的值為0，表示它指向空樹，圖中指針root用以指向二叉樹的根結(jié)點(diǎn)。問題：（1）填充流程圖中的①、②、③，使其按中序遍歷二叉樹。

（2）把流程圖中的（A）框移至哪個(gè)位置（圖中Ⅰ～Ⅸ）使流程圖的算法從中序遍歷變成后序遍歷。

46．設(shè)一棵二叉樹的先序、中序遍歷序列分別為

先序遍歷序列：ABDFCEGH中序遍歷序列：BFDAGEHC（1）畫出這棵二叉樹。

（2）畫出這棵二叉樹的后序線索樹。（3）將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹（或森林）。47．已知一棵二叉樹的對稱序和后序序列如下：對稱序：GLDHBEIACJFK后序：LGHDIEBJKFCA(1)（2分)給出這棵二叉樹：(2)（2分)轉(zhuǎn)換為對應(yīng)的森林：

(3)（4分)畫出該森林的帶右鏈的先根次序表示法：

Itag=

(4)(4分)畫出該森林帶度數(shù)的后根次序表示法：

(5)(4分)在帶度數(shù)的后根次序表示法中，不包含指針，但仍能完全反映樹的結(jié)構(gòu)。寫出以結(jié)點(diǎn)x為根的子樹在后根次序序列中的前驅(qū)的求法。（用語言表達(dá)，不用寫算法）

48．設(shè)某二叉樹的前序遍歷序列為:ABCDEFGGI，中序遍歷序列為:BCAEDGHFI：（1）試畫出該二叉樹；

（2）寫出由給定的二叉樹的前序遍歷序列和中序遍歷序列構(gòu)造出該二叉樹的算法。

（3）設(shè)具有四個(gè)結(jié)點(diǎn)的二叉樹的前序遍歷序列為ａｂｃｄ；Ｓ為長度等于四的由ａ，ｂ，ｃ，ｄ排列構(gòu)成的字符序列，若任?。幼鳛樯鲜鏊惴ǖ闹行虮闅v序列，試問是否一定能構(gòu)造出相應(yīng)的二叉樹，為什么？試列出具有四個(gè)結(jié)點(diǎn)二叉樹的全部形態(tài)及相應(yīng)的中序遍歷序列。類似此題的另外表達(dá)有：

（1）已知二叉樹的先序序列:CBHEGAF,中序序列:HBGEACF,試構(gòu)造該二叉樹

（2）已知二叉樹按中序排列為BFDAEGC，按前序排列為ABDFCEG，要求畫出該二叉樹。

（3）已知一棵二叉樹的前序序列A,B,D,C,E,F，中序序列B,D,A,E,F,C.畫出這棵二叉樹。

（4）已知一棵二叉樹的前序遍歷結(jié)果是：ABCDEFGHIJ,中序遍歷的結(jié)果是：BCEDAGHJIF,試畫出這棵二叉樹。

（5）已知二叉樹BT各結(jié)點(diǎn)的先序、中序遍歷序列分別為ABCDEGF和CBAEDF，試畫出該二叉樹。

49.假設(shè)一棵二叉樹的前序序列為ABCD,它的中序序列可能是DABC嗎?

類似此題的另外表達(dá)有：

（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，試畫出該二叉樹。

50．一棵非空的二叉樹其先序序列和后序序列正好相反，畫出這棵二叉樹的形狀。

51．已知一棵二叉樹的后序遍歷序列為EICBGAHDF，同時(shí)知道該二叉樹的中序遍歷序列為CEIFGBADH，試畫出該二叉樹。

類似此題的另外表達(dá)有：

（1）已知二叉樹ＢＴ各結(jié)點(diǎn)的中序和后序序列分別為ＤＦＢＡＣＥＧ和ＦＤＢＧＥＣＡ，試構(gòu)造出該二叉樹ＢＴ，并作簡要說明。

（2）已知二叉樹的中序遍歷序列為GFBEANHM，后序遍歷的結(jié)點(diǎn)序列為GEBFHNMA，畫出此二叉樹的形態(tài)。

（3）已知二叉樹的后序序列為ABCDEFG和中序序列為ACBGEDF，構(gòu)造出該二叉樹。

（4）已知某二叉樹的后序遍歷和中序遍歷如下，構(gòu)造出該二叉樹。

后序遍歷序列：GDBEIHFCA中序遍歷序列：DGBAECHIF

（5）已知一個(gè)二分樹的中序序列和后序序列如下：

中序：ABCDEFGHIJ后序：ACDBHJIGFE試畫出此二分樹的結(jié)構(gòu)。

52．假設(shè)一棵二叉樹的層次序列為ABCDEFGHIJ，中序序列DBGEHJACIF。請畫出這棵二叉樹。

類似此題的另外表達(dá)有：

（1）假設(shè)一棵二叉樹的層次次序（按層次遞增順序排列，同一層次自左向右）為ABECFGDHI,中序序列為BCDAFEHIG。請畫出該二叉樹，并將其轉(zhuǎn)換為對應(yīng)的森林。

53.已知一個(gè)森林的先序序列和后序序列如下，請構(gòu)造出該森林。先序序列：ABCDEFGHIJKLMNO

后序序列：CDEBFHIJGAMLONK54．畫出同時(shí)滿足以下兩條件的兩棵不同的二叉樹。(1)按先根序遍歷二叉樹順序?yàn)锳BCDE。(2)高度為5其對應(yīng)的樹（森林）的高度最大為4。

55．用一維數(shù)組存放的一棵完全二叉樹；ABCDEFGHIJKL。請寫出后序遍歷該二叉樹的訪問結(jié)點(diǎn)序列。

56．一棵二叉樹的先序、中序、后序序列如下，其中一部分未標(biāo)出，請構(gòu)造出該二叉樹。先序序列：__CDE_GHI_K中序序列：CB__FA_JKIG

后序序列：_EFDB_JIH_A類似此題的另外表達(dá)有：

（1）一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分為顯示出來。試求出空格處的內(nèi)容，并畫出該二叉樹。先序序列:_BFICEHG中序序列：DKFIAEJC后序序列：KFBHJGA（2）已知一棵二叉樹的先序中序和后序序列如下，其中空缺了部分，請畫出該二叉樹。先序：_BC_EFG_IJK_中序：CBED_GAJ_H_L

后序：_E_FD_J_L_HA

（3）已知含有8個(gè)結(jié)點(diǎn)的一棵二叉樹，按先序、中序、后序進(jìn)行遍歷后，有些結(jié)點(diǎn)序號不明白如下圖示。要求構(gòu)造出一棵符合條件的二叉樹。先根序遍歷_23_5_78中根序遍歷3_41_786

后根序遍歷_42__651

57．M叉樹的前序和后序遍歷分別與由它轉(zhuǎn)換成的二叉樹的哪種遍歷相對應(yīng)？

58．證明：在二叉樹的三種遍歷序列中，所有葉子結(jié)點(diǎn)間的先后關(guān)系都是一致的。要求每步論斷都指出根據(jù)。

59.下表中M﹑N分別是一棵二叉樹中的兩個(gè)結(jié)點(diǎn)，表中行號i=1，2，3，4分別表示四種M﹑N的相對關(guān)系，列號j=1，2，3分別表示在前序、中序、后序遍歷中M,N之間的先后次序關(guān)系。要求在i，j所表示的關(guān)系能夠發(fā)生的方格內(nèi)打上對號。例如：假使你認(rèn)為n是m的祖先，并且在中序遍歷中n能比m先被訪問，則在（3，2）格內(nèi)打上對號先根遍歷時(shí)n先被訪問中根遍歷時(shí)n先被訪問后根遍歷時(shí)n先被訪問N在M的左邊N在M的右邊N是M的祖先N是M的子孫

60．用一維數(shù)組存放的一棵完全二叉樹如下圖所示：ABCDEFGHIJKL寫出后序遍歷該二叉樹時(shí)訪問結(jié)點(diǎn)的順序。

61．設(shè)樹形T在后根次序下的結(jié)點(diǎn)排列和各結(jié)點(diǎn)相應(yīng)的次數(shù)如下：后根次序：ＢＤＥＦＣＧＪＫＩＬＨＡ次數(shù)：００００３０００２０２４

請畫出Ｔ的樹形結(jié)構(gòu)圖。62．已知二叉樹采用二叉鏈表方式存放，要求返回二叉樹T的后序序列中的第一個(gè)結(jié)點(diǎn)的指針，是否可不用遞歸且不用棧來完成？請簡述原因。

63．對于二叉樹T的兩個(gè)結(jié)點(diǎn)n1和n2，我們應(yīng)選中擇樹T結(jié)點(diǎn)的前序、中序和后序中哪兩個(gè)序列來判斷結(jié)點(diǎn)n1必定是結(jié)點(diǎn)n2的祖先,并給出判斷的方法。不需證明判斷方法的正確性。

64．設(shè)二叉樹的存儲結(jié)構(gòu)如下(每題5分,共15分)