數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及參考答案

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及參考答案中南大學(xué)現(xiàn)代遠(yuǎn)程教育課程考試復(fù)習(xí)題及參考答案

數(shù)據(jù)結(jié)構(gòu)

一、判斷題：

1．?dāng)?shù)組是一種繁雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的。[]2．鏈?zhǔn)酱鎯υ诓迦撕蛣h除時需要保持物理存儲空間的順序分派，不需要保持?jǐn)?shù)據(jù)元素之間的規(guī)律順序。[]3．在用循環(huán)單鏈表表示的鏈?zhǔn)疥犃兄?，可以不設(shè)隊頭指針，僅在鏈尾設(shè)置隊尾指針。[]4．尋常遞歸的算法簡單、易懂、簡單編寫，而且執(zhí)行的效率也高。[]5．一個廣義表的表尾總是一個廣義表。[]6．當(dāng)從一個小根堆（最小堆）中刪除一個元素時，需要把堆尾元素填補到堆頂位置，然后再

按條件把它逐層向下調(diào)整，直到調(diào)整到適合位置為止。[]7．對于一棵具有n個結(jié)點，其高度為h的二叉樹，進(jìn)行任一種次序遍歷的時間繁雜度為O（h）。[]8．存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。[]9．直接選擇排序是一種穩(wěn)定的排序方法。[]10．30、閉散列法尋常比開散列法時間效率更高。[]11．有n個結(jié)點的不同的二叉樹有n!棵。[]12．直接選擇排序是一種不穩(wěn)定的排序方法。[]13．在2048個互不一致的關(guān)鍵碼中選擇最小的5個關(guān)鍵碼，用堆排序比用錦標(biāo)賽排序更快。[]14．當(dāng)3階B_樹中有255個關(guān)鍵碼時,其最大高度(包括失敗結(jié)點層)不超過8。[]15．一棵3階B_樹是平衡的3路探尋樹,反之,一棵平衡的3路探尋樹是3階非B_樹。[]16．在用散列表存儲關(guān)鍵碼集合時，可以用雙散列法尋覓下一個空桶。在設(shè)計再散列函數(shù)時，

要求計算出的值與表的大小m互質(zhì)。[]17．在只有度為0和度為k的結(jié)點的k叉樹中，設(shè)度為0的結(jié)點有n0個，度為k的結(jié)點有nk個，則有n0=nk+1。[]18．折半探尋只適用于有序表，包括有序的順序表和有序的鏈表。[]19．假使兩個串含有一致的字符，則這兩個串相等。[]20．?dāng)?shù)組可以看成線性結(jié)構(gòu)的一種推廣，因此可以對它進(jìn)行插入、刪除等運算。[]21．在索引順序表上實現(xiàn)分塊查找，在等概率查找狀況下，其平均查找長度不僅與表中元素個數(shù)

有關(guān)，而且與每一塊中元素個數(shù)有關(guān)。[]22．在順序表中取出第i個元素所花費的時間與i成正比。[]23．在棧滿狀況下不能作進(jìn)棧運算，否則產(chǎn)生“上溢〞。[]24．二路歸并排序的核心操作是將兩個有序序列歸并為一個有序序列。[]25．對任意一個圖，從它的某個頂點出發(fā)，進(jìn)行一次深度優(yōu)先或廣度優(yōu)先探尋，即可訪問圖的

每個頂點.[]26．二叉排序樹或者是一棵空二叉樹，或者不是具有以下性質(zhì)的二叉樹：若它的左子樹非空，

則根結(jié)點的值大于其左孩子的值;若它的右子樹非空，則根結(jié)點的值小于其右孩子的值。[]27．在執(zhí)行某個排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動，則該算法

是不穩(wěn)定的。[]28．一個有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)一定相等。[]29．?dāng)?shù)據(jù)的基本單位是數(shù)據(jù)項。

30．帶權(quán)的無向連通圖的最小生成樹是唯一的。[]31．?dāng)?shù)組元素之間的關(guān)系，既不是線性的，也不是樹形的。[]32．對于有n個對象的待排序序列進(jìn)行歸并排序，所需平均時間為O（nlog2n）。[]33．用鄰接矩陣法存儲一個圖所需的存儲單元數(shù)目與圖的邊數(shù)有關(guān)。[]34．在霍夫曼編碼中，當(dāng)兩個字符出現(xiàn)的頻率一致時，其編碼也一致，對于這種狀況應(yīng)當(dāng)特別

處理。[]35．線性表采用順序存儲表示時，必需占用一片連續(xù)的存儲單元。[]36．由樹轉(zhuǎn)化成二叉樹，其根的右子女指針總是空的。[]37．樹形選擇排序是一種不穩(wěn)定的排序方法。[]38．中序遍歷二叉樹是一個有序序列。[]

數(shù)據(jù)結(jié)構(gòu)第1頁

39．裝載因子是散列表的一個重要參數(shù)，它反映了散列表的裝滿程度。[]二、選擇題：

1.在一個長度為n的順序表的任一位置插入一個新元素的漸進(jìn)時間繁雜度為[]

2

A.O(n)B.O(n／2)C.O(1)D.O(n)

2.帶頭結(jié)點的單鏈表first為空的判定條件是：[]A.first==NULL

B.first一>1ink＝＝NULLC.first一>link==first

D.first!＝NUlL

3.當(dāng)利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為[]A.n-2B.n-lC.nD.n+1

4.在系統(tǒng)實現(xiàn)遞歸調(diào)用時需利用遞歸工作記錄保存實際參數(shù)的值。在傳值參數(shù)情形，需為對

應(yīng)形式參數(shù)分派空間，以存放實際參數(shù)的副本；在引用參數(shù)情形，需保存實際參數(shù)的[]在被調(diào)用程序中可直接操縱實際參數(shù)。

A.空間B.副本C.返回地址D.地址5.在一棵樹中，[]沒有前驅(qū)結(jié)點。

A.分支結(jié)點B.葉結(jié)點C.樹根結(jié)點D.空結(jié)點

6.在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加[]A.2B.1C.0D.-1

7.對于長度為9的有序順序表,若采用折半探尋，在等概率狀況下探尋成功的平均探尋長度為[]的值除以9。

A.20B.18C.25D.22

8.在有向圖中每個頂點的度等于該頂點的[]A.入度B.出度C.入度與出度之和D.入度與出度之差

9.在基于排序碼比較的排序算法中，[]算法的最壞狀況下的時間繁雜度不高于O(n1og2n)。A.起泡排序B.希爾排序C.歸并排序D.快速排序

10.當(dāng)α的值較小時，散列存儲尋常比其他存儲方式具有[]的查找速度。

A.較慢B.較快C.一致D.不明白

11.設(shè)有一個含200個表項的散列表，用線性探查法解決沖突，按關(guān)鍵碼查詢時找到一個表項

的平均探查次數(shù)不超過1.5，則散列表項應(yīng)能夠至少容納[]個表項。

(設(shè)探尋成功的平均探尋長度為ASL＝{1+l／(1一α)}／2，其中α為裝填因子)A.400B.526C.624D.67612.堆是一個鍵值序列{k1,k2,?..kn},對I=1,2,?.|_n/2_|,滿足[]

A.ki≤k2i≤k2i+1B.kinext==NULLC.head!=NULLD.head->next==head

16.引起循環(huán)隊列隊頭位置發(fā)生變化的操作是[]

A.出隊B.入隊C.取隊頭元素D.取隊尾元素

17.若進(jìn)棧序列為1，2，3，4，5，6,且進(jìn)棧和出?？梢源┎暹M(jìn)行,則不可能出現(xiàn)的出棧序列是[]

A.2，4，3，1，5，6B.3，2，4，1，6，5C.4，3，2，1，5，6D.2，3，5，1，6，4

18.字符串尋常采用的兩種存儲方式是[]

數(shù)據(jù)結(jié)構(gòu)第2頁

，A.散列存儲和索引存儲B.索引存儲和鏈?zhǔn)酱鎯.順序存儲和鏈?zhǔn)酱鎯.散列存儲和順序存儲

19.設(shè)主串長為n，模式串長為m(m≤n)，則在匹配失敗狀況下，簡樸匹配算法進(jìn)行的無效位移

次數(shù)為[]A.mB.n-mC.n-m+1D.n20.二維數(shù)組A［12］［18］采用列優(yōu)先的存儲方法，若每個元素各占3個存儲單元，且第1個

元素的地址為150，則元素A［9］［7］的地址為[]A.429B.432C.435D.438

21.對廣義表L=((a,b),(c,d),(e,f))執(zhí)行操作tail(tail(L))的結(jié)果是[]

A.(e,f)B.((e,f))C.(f)D.()

22.以下圖示的順序存儲結(jié)構(gòu)表示的二叉樹是[]

23.n個頂點的強連通圖中至少含有[]

A.n-1條有向邊B.n條有向邊C.n(n-1)/2條有向邊D.n(n-1)條有向邊

24.對關(guān)鍵字序列(56，23，78，92，88，67，19，34)進(jìn)行增量為3的一趟希爾排序的結(jié)果為[]

A.(19，23，56，34，78，67，88，92)B.23，56，78，66，88，92，19，34)C.(19，23，34，56，67，78，88，92)D.(19，23，67，56，34，78，92，88)

25.若在9階B-樹中插入關(guān)鍵字引起結(jié)點分裂，則該結(jié)點在插入前含有的關(guān)鍵字個數(shù)為[]

A.4B.5C.8D.9

26.由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹[]

A.其形態(tài)不一定一致，但平均查找長度一致

B.其形態(tài)不一定一致，平均查找長度也不一定一致C.其形態(tài)均一致，但平均查找長度不一定一致D.其形態(tài)均一致，平均查找長度也都一致27.ISAM文件和VSAM文件的區(qū)別之一是[]

A.前者是索引順序文件，后者是索引非順序文件B.前者只能進(jìn)行順序存取，后者只能進(jìn)行隨機存取C.前者建立靜態(tài)索引結(jié)構(gòu)，后者建立動態(tài)索引結(jié)構(gòu)D.前者的存儲介質(zhì)是磁盤，后者的存儲介質(zhì)不是磁盤

28.以下描述中正確的是[]

A.線性表的規(guī)律順序與存儲順序總是一致的

B.每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本運算：插入、刪除和查找C.數(shù)據(jù)結(jié)構(gòu)實質(zhì)上包括規(guī)律結(jié)構(gòu)和存儲結(jié)構(gòu)兩方面的內(nèi)容D.選擇適合的數(shù)據(jù)結(jié)構(gòu)是解決應(yīng)用問題的關(guān)鍵步驟

29.下面程序段的時間繁雜度是[]

I=s=0

While(srear==Q->frontB.(Q->rear+1)%maxsize==Q->frontC.Q->rear==0D.Q->front==0

35.設(shè)s3=\。則strcmp(s3,s4)=[]

A.0B.小于0C.大于0D.不確定

36.一維數(shù)組的元素起始地址loc[6]=1000，元素長度為4，則loc[8]為[]

A.1000B.1004C.1008D.837.廣義表（（a,b）,c,d）的表尾是[]

A．a(chǎn)B.bC.(a,b)D.(c,d)

38.對于二叉樹來說，第I層上至多有____個節(jié)點[]

A.2iB.2i-1C.2i-1D.2i-1

-1

39.某二叉樹的前序遍歷序列為ABDGCEFH,中序遍歷序列為DGBAECHF，則后序遍歷序列為[]

A.BDGCEFHAB.GDBECFHAC.BDGAECHFD.GDBEHFCA

40.M叉樹中，度為0的節(jié)點數(shù)稱為[]

A.根B.葉C.祖先D.子孫41.已知一個圖如下所示，若從頂點a出發(fā)按寬度探尋法進(jìn)行遍歷，則可能得到的一種頂點序列為[]

42.堆的形狀是一棵[]

A.二叉排序樹B.滿二叉樹C.完全二義樹D.平衡二叉樹

43.排序方法中，從未排序序列中挑揀元素，并將其依次放入已排序序列（初始時為空）的一

端的方法，稱為[]A.希爾排序B.歸并排序C.插入排序D.選擇排序

44.采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為[]

A.nB.n/2C.(n+1)/2D.(n-1)/2

45.散列查找是由鍵值______確定散列表中的位置，進(jìn)行存儲或查找[]

A.散列函數(shù)值B.本身C.平方D.相反數(shù)

46.順序文件的缺點是[]

A.不利于修改B.讀取速度慢C.只能寫不能讀D.寫文件慢

47.索引文件的檢索方式是直接存取或按_____存取[]

數(shù)據(jù)結(jié)構(gòu)第4頁

A.隨機存取B.關(guān)鍵字C.間接D.散列

48.若需要利用形參直接訪問實參，則應(yīng)把形參變量參數(shù)說明為[]

A.指針B.引用C.傳值D.常值

49.以下說法錯誤的是[]A.抽象數(shù)據(jù)類型具有封裝性D.抽象數(shù)據(jù)類型具有信息隱蔽性

C.使用抽象數(shù)據(jù)類型的用戶可以自己定義對抽象數(shù)據(jù)類型中數(shù)據(jù)的各種操作D.抽象數(shù)據(jù)類型的一個特點是使用與實現(xiàn)分開

50.設(shè)有一個n×n的對稱矩陣A，將其上三角部分按行存放在一個一維數(shù)組B中，A[0][0]存

放于B[0]中，那么第i行的對角元素A[I][i]存放于B中()處。[]A.(i+3)*i／2D.(i+1)*i／2

C.(2n—i+1)*i／2D.n(2n—i一1)*i／2

51.已知單鏈表A長度為m，單鏈表B長度為n，若將B聯(lián)接在A的末尾，其時間繁雜度應(yīng)為[]A．O(1)B．O(m)C．O(n)D．O(m+n)

52.假定一個鏈?zhǔn)疥犃械年狀^和隊尾指針分別為front和rear，則判斷隊空的條件為[]A．front==rearB，front!=NULLC．rear!=NULLD．front＝＝NULL53.設(shè)有一個遞歸算法如下intfact(intn){／／n大于等于0if(n

參考答案

一、判斷題：

1.√2.×3.√4.×5.√6.√7.×8.×9.×10.×11.×12.√13.×14.√15.×16.√17.×18.×19.×20.×21.√22.×23.√24.√25.×26.×27.×28.√29.×30.×31.√32.√33.×34.×35.√36.√37.√38.×39.√二、單項選擇題：

1.A2.B3.B4.D5.C6.A7.C8.C9.C10.B11.A12.C13.B14.D15.A16.A17.D18.C19.C20.A21.B22.A23.B24.D25.C26.B27.C28.D29.B30.A31.A32.B33.D34.A35.C36.C37.D38.C39.D40.A41.B42.C43.D44.C45.A46.A47.B48.B49.C50.C51.B52.D53.B54.D55.C56.B57.C58.D59.D60.B61.A62.C63.B64.C65.A66.C67.C68.B69.D70.A71.B72.C73.D74.D三、填空題：

1.鏈?zhǔn)酱鎯Y(jié)構(gòu)

2.前驅(qū)結(jié)點，后繼結(jié)點

3.由一個或多個空格字符組成的串，其包含的空格個數(shù)4.鄰接矩陣，鄰接表5.O（n），O(log2n)6.1044

7.入棧（插入），出棧（刪除）8.前驅(qū)結(jié)點，后繼結(jié)點9.中序序列

10.順序存儲結(jié)構(gòu)，有序的11.n，n-1

12.最大語句頻度:n(n+1)/2，時間繁雜度：O(n2

)13.三元組表，十字鏈表

14.規(guī)律結(jié)構(gòu)和物理結(jié)構(gòu)數(shù)據(jù)元素的集合數(shù)據(jù)元素之間關(guān)系的集合

15.順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)16.p->next=p->next->next

17.Head->next=Head->next->nextHead=Head->next18.O(n)、O(m*n)19.行號、列號、元素值20.二叉探尋樹、理想平衡樹21.2

22.向上、堆頂23.遞推，回歸24.根結(jié)點25.鏈?zhǔn)酱鎯?6.隊首，隊尾

27.0，2k-1

28.深度，廣度

29.沒有、1、沒有、1

30.前驅(qū)、1、后續(xù)、任意多個31.任意多個

32.一對一、一對多、多對多

33.有窮性、確定性、可行性、輸入、輸出34.s,p35.q->next,q

數(shù)據(jù)結(jié)構(gòu)第16頁

36.兩個串的長度相等且對應(yīng)位置的字符一致37.200+（6*20+12）=326

38.1000+((18-10)*6+(9-5))*4=120839.(1).(b)(2).(d)40.n-141.10

42.求矩陣第i列非零元素之和43.將矩陣第i行全部置為零44.n45.9

22

46.對每個頂點查找其鄰接點的過程；O（n）；O（n）；遍歷圖的順序不同；DFS采用棧存儲訪問過的結(jié)

點，BFS采用隊列存儲訪問過的結(jié)點。

47.（n+1）/2、((n+1)*log2(n+1))/n-1、1+?（?為裝填因子）48.哈希表查找法

49.順序存儲結(jié)構(gòu)、有序的

50.1、2、4、8、5、3.7（依題意，構(gòu)造一棵有序二叉樹，共20個結(jié)點，第一層1個結(jié)點，其次層

2個結(jié)點，第三層4個結(jié)點，第四層8個結(jié)點，依次下去）51.O（n）、O(log2n)52.2、4、3

53.結(jié)點個數(shù)n、生成過程54.二叉排序樹

55.2.2;4;（23，38，15）

56.堆排序、快速排序、歸并排序、歸并排序、快速排序、堆排序57.實例

58.基類派生(或于類)59.16

60.鏈接指針

61.p一>Link=toptop=p62.重數(shù)

h

63.264.32

65.3x2.45／6－*＋66.(3h-1)/267.51868.小于大于69.向上堆頂

70.鄰接距陣鄰接表邊集數(shù)組（無次序先后）

2

71.O(n)O(e)72.1373.13O(n)74.同一層75．2(n-1)

2

76．O(n)77．844678．稀疏

數(shù)據(jù)結(jié)構(gòu)第17頁

四、計算與算法應(yīng)用題：1.［解答］

平均長度為4。

2.遍歷得到的DFS生成森林和BFS生成森林如下：（各4分，共8分）

3.解：畫圖（略）

深度優(yōu)先探尋序列：a，b，f，h，c，d，g，e

廣度優(yōu)先探尋序列：a，b，c，f，d，e，h，g4.解：

高度：4

度為2的結(jié)點數(shù)：3

數(shù)據(jù)結(jié)構(gòu)第18頁

度為l的結(jié)點數(shù)：3度為0的結(jié)點數(shù)：45.解：計算機關(guān)鍵碼得到的散列地址關(guān)鍵碼散列地址

在散列表中散列結(jié)果

0123456789101112

6.對n個關(guān)鍵自序列進(jìn)行一趟快速排序，要進(jìn)行n-1次比較，也就是基準(zhǔn)和其他n-1個關(guān)鍵字比較。

這里要求10次，而7-1+2*(3-1)=10，這就要求2趟快速排序后，算法終止。所以，列舉出來的序列，要求在做partition的時候，正好將序列平分(1)4132657

或4137652或4537612或4135627(2)按自己序列完成012345Jan(1)6789(5)10111213AprAugDecFeb(1)(2)(1)(1)

(2)探尋成功的平均探尋長度為

l／12*(1+2+l+l+l+l+2+4+5+2+5+6)：3l／127.解：

頂點：0123456

路徑長度：01610142521318.答案：(1)djbaechif(2)abdjcefhi(3)jdbeihfca

9.（3，4）5，（0，1）8，（4，5）9，（4，7）10，（2，4）14，（1，3）15，（4，6）3110.在這個AVL樹中刪除根結(jié)點時有兩種方案:

在根的左子樹中沿右鏈走終究,用5遞補根結(jié)點中原來的6,再刪除5所在的結(jié)點.在根的右子樹中沿左鏈走終究,用7遞補根結(jié)點中原來的6,再刪除7所在的結(jié)點.11.劃分次序第一次其次次第三次第四次第五次第六次劃分結(jié)果[382440]46[56809579]24[3840]46[56809579]24384046[56809579]2438404656[809579]243840465679[8095]2438404656798095數(shù)據(jù)結(jié)構(gòu)第19頁

MarMayJuneJulySepOctNov(1)(2)(4)(2)(5)(6)1401682719208423196141231001168320784627112.012345678910111278150357452031233612查找成功的平均查找長度：ASLSUCC=14/10=1.413.此二叉樹的后序遍歷結(jié)果是：EDCBIHJGFA14.13／71l／7

15．2l25[343840]46[795657]8012.

16.(A)深度遍歷：1，2，3，8，4，5，7，6或1，2，3，8，5，7，4，

(B)廣度遍歷：1，2，4，6，3，5，7，8(C)拓?fù)湫蛄校?，2，4，6，5，3，7，8(D)最短路徑：1，2，5，7，8(E)關(guān)鍵路徑：1，6，5，3，817.

ASLsucc=（1+2X2+3X4+4X3）/10=2.9

18.源點終點最短路徑路徑長度121，3，21931，31541，3，2，42951，3，52961，3，2，4，64419.先根：a,b,e,c,f,h,i,g,d;

后根：e,b,h,i,f,g,c,d,a:按層：a,b,c,d,e,f,g,h,i20.最小生成樹的權(quán)：3421.112

22.（40，34，25，38，46，80，56，79）23.插入如下

數(shù)據(jù)結(jié)構(gòu)第20頁7878535353

65

2309170917091717175378655378658753786587537865458781537865458781數(shù)據(jù)結(jié)構(gòu)第21頁

24.已知要存儲的記錄數(shù)為n=150，查找成功的平均查找長度為ASLsucc≤2，

則有ASLsucc=

≤2,解得a≤又有a==≤,則m≥225。

25.初始狀態(tài)：（d=n/2=4）86，75，50，40，90，33，15，42

一趟排序后：86，33，15，40，90，75，50，4226．（答案不唯一，下邊僅是參考答案）(1)哈夫曼樹

6040100010101

0101

(2)編碼：

2000006000110001121113000017001019103201(3)WPL=2×5+3×5+6×4+7×4+10×4+32×2+19×2+21×2=261

27．(1)每個頂點的出入度：

23511172832192101671001

頂點入度出度130222312413521623數(shù)據(jù)結(jié)構(gòu)第22頁

(2)鄰接矩陣：123456100000021001003010001400101151000006110010

(3)鄰接表：

V1V2V3V4V5V6

五、算法設(shè)計題：

1.二叉樹采取順序結(jié)構(gòu)存儲，是按完全二叉樹格式存儲的。對非完全二叉樹要補上“虛結(jié)點〞。由于不是完全二叉樹，在順序結(jié)構(gòu)存儲中對葉子結(jié)點的判定是根據(jù)其左右子女為0。葉子和雙親結(jié)點下標(biāo)間的關(guān)系滿足完全二叉樹的性質(zhì)。

intLeaves(inth)//求深度為h以順序結(jié)構(gòu)存儲的二叉樹的葉子結(jié)點數(shù){intBT[];intlen=2-1,count=0;//BT是二叉樹結(jié)點值一維數(shù)組，容量為2for(i=1;ilen)count++;//第i個結(jié)點沒子女，確定是葉子

elseif(BT[2*i]==0//無左右子女的結(jié)點是葉子

return(count)}//終止Leaves2.

boolFind（BtreeNode*BST，ElernType＆item）

數(shù)據(jù)結(jié)構(gòu)第23頁

h

h

^V5^V1V2V5^V1V2V4^V6^V3V5V6{

while（BST！=NULL）{

if（item==BST->data）{item=BST->data；returntrue;}elseif（item＜BST->data＝BST＝BST->left;

elseBST=BST->right；

}

returnfalse;}

3.intCount(BTreeNode*BT)／／統(tǒng)計出二叉樹中所有葉子結(jié)點數(shù){if(BT==NULL)returnO；

elseif(BT->left==NULL

while(inext;q=b->next;c->next=NULL;while(pp->next=c->next;c->next=p;p=pn;}else{

qn=q->next;q->next=c->next;c->next=q;q=qn;}

數(shù)據(jù)結(jié)構(gòu)第24頁

while(p){pn=p->next;p->next=c->next;c->next=p;p=pn;}while(q){qn=q->next;q->next=c->next;c->next=q;q=qn;}free(b);}//MergeList

6.StatusDel-subtree(Bitreebt){//刪除bt所指二叉樹，并釋放相應(yīng)的空間if(bt){

Del-subtree(bt->lchild);Del-subtree(bt->rchild);free(bt);}

returnOK;}//Del-subtree

StatusSearch-del(Bitreebt,TelemTypex){

//在bt所指的二叉樹中，查找所有元素值為x的結(jié)點，并刪除以它為根的子樹if(bt){

if(bt->data=x)Del-subtree(bt);else{

Search-Del(bt->lchild,x);Search-Del(bt->rchild,x);}}

returnOK;}//Search-Del

7.TelemTypeMaxv(BitreeT){

//返回二叉排序樹T中所有結(jié)點的最大值for(p=T;p->rchild;p=p->rchild);returnp->data;}//Maxv

TelemTypeMinv(BitreeT){

//返回二叉排序樹T中所有結(jié)點的最小值for(p=T;p->lchild;p=p->lchild);returnp->data;}//Minv

StatusIsBST(BitreeT){//判別T是否為二叉排序樹if(!T)returnOK;

elseif((!T->lchild)||((T->lchild)

}//IsBST

8.voidLink::Delnode(){NodeType*p=Head->next,*q,*r=p;

數(shù)據(jù)結(jié)構(gòu)第25頁

while(p!=NULLp=p->next;

}q=p;

while(q!=NULLr->next=q->next;r=p->next;while(r!=q){deletep;

p=r;r=r->next;}

deleteq;}//delpro

9.ElemTypeFindMax(BtreeNode*BST){

if(BST==NULL){

cerrleft!=NULL)t=t->left;returnt->data;}

10.voidInsert(ABTListBST,constElemTypep->data=item;p->left=p-right=NULL;BST=p;}

elseif(itemdata,item)

Insert(BST->left,item);elseInsert(BST->right,item);}

11.intBTFeeEqual(BinTreeNOde*T1，BinTreeNOde*T2)

{

數(shù)據(jù)結(jié)構(gòu)第26頁

／／若兩棵樹均為空則返回1表示相等if(T1==NULL／／若一棵為空一棵不為空則返回。表示不等elseif(TI==NULL‖T2==NULL)return0；

／／若根結(jié)點值相等并且左、右子樹對應(yīng)相等則兩棵樹相等

elseif(T1->data==T2->data

／／若一棵為空一棵不為空則返回。表示不等if(T1==NULL