《數(shù)據(jù)結(jié)構(gòu)》期末復(fù)習(xí)題-答案

1.以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是（C）

C、哈希表

2.一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素的長度為2,則第5個(gè)元素的地址是（B）

B、108

3.假設(shè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針為head,則該鏈表為空的判定條件是（C）

C、head-）next==head

4.若進(jìn)棧序列為1,2,3,4,5,6,且進(jìn)棧和出棧可以穿插進(jìn)行，則不可能出現(xiàn)的出棧序列是（D）

D、2,3,5,1,6,4

5.下列關(guān)鍵字序列中，構(gòu)成小根堆的是（A）

A、｛12,21,49,33,81,56,69,41）

6.下列數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹的是（A）

A、B樹

7.用順序存儲(chǔ)的方法來存儲(chǔ)一棵二叉樹，存放在一維數(shù)組A[1..N]中,若結(jié)點(diǎn)A[i]有右孩子，則其右孩子是（C）。

C、A[2i+l]

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

D、8

9.有數(shù)據(jù)｛53,30,37,12,45,24,96）,從空二叉樹開始逐個(gè)插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，則應(yīng)選擇下

面哪個(gè)序列輸入（B）

B、37,24,12,30,53,45,96

10.對(duì)下面有向圖給出了四種可能的拓?fù)湫蛄?，其中錯(cuò)誤的是（C）

C、5,1,6,3,4,2

11.m階B-樹中所有非終端（除根之外）結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)必須大于或等于（B）

B、Lm/2]—1

12.散列文件也稱為（C）

B、索引文件

13.數(shù)據(jù)結(jié)構(gòu)是（D）

D、相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合

14.從邏輯關(guān)系來看,數(shù)據(jù)元素的直接前驅(qū)為0個(gè)或1個(gè)的數(shù)據(jù)結(jié)構(gòu)只能是（C）

C、線性結(jié)構(gòu)和樹型結(jié)構(gòu)

15.設(shè)p為指向雙向循環(huán)鏈表中某個(gè)結(jié)點(diǎn)的指針，p所指向的結(jié)點(diǎn)的兩個(gè)鏈域分別用p-llink和p-rlink表示，則同樣表示

P指針?biāo)赶蚪Y(jié)點(diǎn)的表達(dá)式是（D）

D、pfllinkfrlink

16.若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間top[i]代表第i個(gè)棧（i=1,2）棧頂，棧1的底在v[l],棧2

的底在V[m],則棧滿的條件是（B）

B、top[l]+l=top[2]

17.若一棵二叉樹有11個(gè)葉子結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)點(diǎn)個(gè)數(shù)是（A）

A、10

18.樹的先根序列等同于與該樹對(duì)應(yīng)的二叉樹的（A）

A、先序序列

19.下面關(guān)于哈希（Hash,雜湊）查找的說法正確的是（C）

C、不存在特別好與壞的哈希函數(shù),要視情況而定

20.下列序列中，（D）是執(zhí)行第一趟快速排序后所得的序列。

D、[68,11,69,23,18][93,73]

21.下列關(guān)鍵字序列中，構(gòu)成小根堆的是（D）

D、（15,28,46,37,84,58,62,41）

22.ISAM文件和VASM文件屬于（C）

C、索引順序文件

23.下面程序段的時(shí)間復(fù)雜度為（C）

for（i=0；i<m；i++）

for（j=0；j<n；j++）

A[i][j]=i*j;

C、O（m*n）

24.已知指針p和q分別指向某單鏈表中第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn).假設(shè)指針s指向另一個(gè)單鏈表中某個(gè)結(jié)點(diǎn),則在s所指結(jié)

點(diǎn)之后插入上述鏈表應(yīng)執(zhí)行的語句為（A）

A、q->next=s->next；s->next=p；

25.為便于判別有向圖中是否存在回路，可借助于（D）

D、拓?fù)渑判蛩惴?/p>

26.若以S和X分別表示進(jìn)棧和退棧操作，則對(duì)初始狀態(tài)為空的?？梢赃M(jìn)行的棧操作系列是（D）

D、SSSXXSXX

27.設(shè)有一順序棧S,元素si,s2,s3,s4,s5,s6依次進(jìn)棧，如果6個(gè)元素出棧的順序是s2,s3,s4,s6,s5,sl,則棧的容量

至少應(yīng)該是（B）

B、3

28.假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素.已知隊(duì)列的長度為length,指針rear指向隊(duì)尾元素的下一個(gè)存儲(chǔ)位置,則隊(duì)頭元素

所在的存儲(chǔ)位置為（B）。

B、（rear-length+m）%m

29.在一個(gè)鏈隊(duì)列中，front和rear分別為頭指針和尾指針，則插入一個(gè)結(jié)點(diǎn)s的操作為（D）。

D、rear->next=s;rear=s;

30.對(duì)于哈希函數(shù)H（key）=key%13,被稱為同義詞的關(guān)鍵字是（D）

D、25和51

31.采用二叉鏈表存儲(chǔ)的n個(gè)結(jié)點(diǎn)的二叉樹，共有空指針（A）個(gè).

A、n+1

32.連通網(wǎng)的最小生成樹是其所有生成樹中（D）

D、邊的權(quán)值之和最小的生成樹

33.對(duì)記錄序列（314,298,508,123,486,145）依次按個(gè)位和十位進(jìn)行兩趟基數(shù)排序之后所得結(jié)果為（B）

B、508,314,123,145,486,298

34.任何一個(gè)無向連通圖的最小生成樹（C）。

C、一棵或多棵

35.無向圖的鄰接矩陣是一個(gè)（C）

C、對(duì)稱矩陣

36.設(shè)無向圖G—=（V,E）和G，二（『，E，），如G'為G的生成樹，則下列說法中不正確的是（B）.B、G'為G連通分量

37.以vl為起始結(jié)點(diǎn)對(duì)下圖進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是（D）

D、vl,v2,v5,v6,v7,v3,v4

38.下面幾個(gè)符號(hào)串編碼集合中，不是前綴編碼的是（B）

B、{0,1,00,11}

39.希爾排序的增量序列必須是（B）。

B、遞減的

40.采用起泡排序法對(duì)n個(gè)關(guān)鍵字進(jìn)行升序排序，若要使排序過程中比較關(guān)鍵字的次數(shù)最多，則初始時(shí)的序列應(yīng)滿足條件

（D）

D、關(guān)鍵字從大到小排列

41.在下列內(nèi)部排序中（A）是不穩(wěn)定的。

A、希爾排序

42.分別以下列序列構(gòu)造二叉排序樹，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的是(C)。

A、(100,80,90,60,120,110,130)

43.在查找過程中，沖突指的是(C)。

C、不同鍵值對(duì)應(yīng)相同的存儲(chǔ)地址

44.對(duì)有14個(gè)元素的有序表A[l。。14]作二分查找，查找元素A[4]時(shí)的被比較元素依次為(D)。

D、A[7],A[3],A[5],A[4]

45.以vl為起始結(jié)點(diǎn)對(duì)下圖進(jìn)行廣度度優(yōu)先遍歷，正確的遍歷序列是(A)

A、vl,v2,v3,v4,v5,v6,v7

二、填空題(本大題共10小題，每小題2分，若有兩個(gè)空格，每個(gè)空格1分，共20分)

1.數(shù)據(jù)的物理結(jié)構(gòu)包括數(shù)據(jù)元素的存儲(chǔ)和數(shù)據(jù)之間關(guān)系的存儲(chǔ)。

2.若一個(gè)算法中的語句頻度之和為T(n)=1921n+4nlogn,則算法的時(shí)間復(fù)雜度為皿n.

3.下面程序段的時(shí)間復(fù)雜度是_log3n_。

i=l;

while(i〈=n)i=i*3；

4.循環(huán)隊(duì)列用數(shù)組A[0oom-11存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列的元素個(gè)數(shù)是

(rear-front+m)%m

5.主要是使插入和刪除等操作統(tǒng)一

6.(n-1)12。

7.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是深度優(yōu)先.

8.線性表L=(al,a2,…，an)用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是

相同值關(guān)鍵字.

9.已知一無向圖G=(V,E),其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}現(xiàn)用某一種圖遍歷方法

從頂點(diǎn)a開始遍歷圖，得到的序列為abecd,則采用的是前移遍歷方法。

10.如果排序過程不改變時(shí)間復(fù)雜度之間的相對(duì)次序,則稱該排序方法是穩(wěn)定的。

11.從順序表中刪除一個(gè)元素時(shí)，表中所有在被刪元素之后的元素均需一個(gè)位置。

12.當(dāng)問題的規(guī)模n趨向無窮大時(shí)，算法執(zhí)行時(shí)間T(n)的數(shù)量級(jí)被稱為算法的100

13.若以鄰接矩陣表示有向圖，則鄰接矩陣上第i行中非零元素的個(gè)數(shù)即為頂點(diǎn)vi的sxssxxssxssxxx.

14.一棵含999個(gè)結(jié)點(diǎn)的完全二叉樹的深度為120

15.假設(shè)S和X分別表示進(jìn)棧和出棧操作，由輸入序列“ABC”得到輸出序列“BCA”的操作序列為SSXSXX,貝岫“a*b+c/d”

得到“ab*cd/+”的操作序列為。

16.o如圖所示的有向無環(huán)圖可以排出L—〉next?>next==L

17.邊種不同的拓?fù)湫蛄小?/p>

18.從空樹起，依次插入關(guān)鍵字11,27,35,48,52,66和73構(gòu)造所得的二叉排序樹，在等概率查找的假設(shè)下，查找成功時(shí)

的平均查找長度為384.

19.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是隊(duì)列。

20.求最小生成樹的克魯斯卡爾（Kruskal）算法耗用的時(shí)間與圖中邊稠密、邊稀疏的數(shù)目正相關(guān)。

21.已知一棵完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有5個(gè)葉子結(jié)點(diǎn)。

22.實(shí)現(xiàn)圖的廣度優(yōu)先搜索，除了一個(gè)標(biāo)志數(shù)組標(biāo)志已訪問的圖的結(jié)點(diǎn)外，還需要8、64存放被訪問的結(jié)點(diǎn)以實(shí)現(xiàn)遍歷.

23.Prim（普里姆）算法適用于求上匚_的網(wǎng)的最小生成樹；kruskal（克魯斯卡爾）算法適用于求上L的網(wǎng)的最小生成樹。

24.對(duì)長度為20的有序表進(jìn)行二分查找的判定樹的高度為n—1。

25.設(shè)一棵完全二叉樹有128個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為n,有個(gè)葉子結(jié)點(diǎn).

26.高度為h的完全二叉樹中最少有棧個(gè)結(jié)點(diǎn),最多有個(gè)結(jié)點(diǎn)。

27.設(shè)連通圖G中有n個(gè)頂點(diǎn)e條邊.則對(duì)應(yīng)的最小生成樹上有3條邊.

28.構(gòu)造n個(gè)結(jié)點(diǎn)的強(qiáng)連通圖，至少有0（I?）條弧。

29.表達(dá)式求值是（42,13,94,55,05,46,17）應(yīng)用的一個(gè)典型例子。

30.設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素eLe2,e3,e4,e5,e6依次通過棧S,一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若6個(gè)元素出

隊(duì)的序列是e2,e4,e3,e6,e5,el,則棧的容量至少應(yīng)該是。

31.快速排序算法在最差的情況下其時(shí)間復(fù)雜度是o

32.對(duì)序列｛55,46,13,05,94,17,42）進(jìn)行基數(shù)排序，第一趟排序后的結(jié)果是。

三、應(yīng)用題（本大題共5小題，每小題6分，共30分）

1.已知二叉樹的先序遍歷序列ABCDEFGH,中序遍歷序列為CBEDFAGH,畫出二叉樹。

答案：二叉樹形態(tài)

2.如圖請(qǐng)給出鄰接表、鄰接矩陣及逆鄰接表。

（1）鄰接表：（注意邊表中鄰接點(diǎn)域的值是頂點(diǎn)的序號(hào)，這里頂點(diǎn)的序號(hào)是頂點(diǎn)的下標(biāo)值一1）

vertexfirstedgenext

（2）逆鄰接表:

(3)

0101

0010

1000

0010

3.由字符集｛s,t,a,e,1｝及其在電文中出現(xiàn)的頻度構(gòu)建的哈夫曼樹如圖所示。已知某段電文的哈夫曼編碼為111000010100,

請(qǐng)根據(jù)該哈夫曼樹進(jìn)行譯碼，寫出原來的電文。

答案:原來的電文為：eatst

4.請(qǐng)畫出下圖所示的樹所對(duì)應(yīng)的二叉樹，并寫出對(duì)應(yīng)二叉樹的先序遍歷和中序遍歷。

答案:

先序遍歷為：12345687中序遍歷為：34867521

5.設(shè)散列表為HT[13],散列函數(shù)為H(key)=key%13。用閉散列法解決沖突，對(duì)下列關(guān)鍵碼序列12,23,45,57,

20,03,78,31,15,36造表。采用線性探查法尋找下一個(gè)空位，畫出相應(yīng)的散列表，并計(jì)算等概率下搜索成功的平均搜

索長度。

答案：

使用散列函數(shù)H(key)=keymod13,有

H(12)=12,H(23)=10,H(45)=6,H(57)=5,

H(20)=7,H(03)=3,H(78)=0,H(31)=5,

H(15)=2,H(36)=10o

利用線性探查法造表：

0123456789101112

78150357452031233612

(1)(1)(1)(1)(1)(1)(4)(1)(2)(1)

搜索成功的平均搜索長度為

114

ASLsucc=----(1+1+1+1+1+1+4+1+2+1)=-----

1010

6.已知帶權(quán)圖G如圖所示，畫出圖G的一棵最小生成樹.

7.假設(shè)用于通信的電文由字符集｛a,b,c,d,e,f,g,h｝中的字母構(gòu)成，這8個(gè)字母在電文中出現(xiàn)的概率分別為｛0。07,

0.19,0.02,0o06,0.32,0.03,0.21,0.10),請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。

1.00

0

O-4X0.60

^0^28?0.32

0.210.19o

V17'X11

少@Qo.05

0.100.070.06（/Al

??

哈夫曼編內(nèi)樹0.030.02

哈夫曼編碼為：a：1001b：01c：10111d：1010e:llf：10110g:00h：1000

注意：答案不唯一

8.試用權(quán)集合｛12,4,5,6,1,2｝構(gòu)造哈夫曼樹，并計(jì)算哈夫曼樹的帶權(quán)路徑長度。

h

300CD

WPL=12*1+(4+5+6)*3+(1+2)*4=12+，45+12=69

9.畫出與如圖所示森林對(duì)應(yīng)的二叉樹。

吟

））??

答:

10.已知一個(gè)散列表如下圖所示:

0123456789101112

其散列函數(shù)為h(key尸key%13,處理沖突的方法為雙重散列法，探查序列為:

hi=(h(key)+1*hl(key))%m1=0,1,…，m-1

其中：hl(key)=key%ll+l

回答下列問題:

(1)對(duì)表中關(guān)鍵字35,20,33和48進(jìn)行查找時(shí)，所需進(jìn)行的比較次數(shù)各為多少？

(2)該散列表在等概率查找時(shí)查找成功的平均查找長度為多少？

答:

(1)對(duì)關(guān)鍵字35、20、33和48進(jìn)行查找的比較次數(shù)為3、2、1、1；

…3+2+1+1+29

(2)平均查找長度ASL=--------------=-

55

11.請(qǐng)畫出與下列二叉樹對(duì)應(yīng)的森林。

答:

12.對(duì)于給定結(jié)點(diǎn)的關(guān)鍵字集合K={5,7,3,1,9,6,4,8,2,10),

(1)試構(gòu)造一棵二叉排序樹;

(2)求等概率情況下的平均查找長度ASL.

答:

5

(2)ASL=(1*1+2*2+3*4+4*3)/10=2.9

13.給出下圖對(duì)應(yīng)的鄰接矩陣,并給出A,B,C三個(gè)頂點(diǎn)的出度與入度

答案：鄰接矩陣為：

ABCDEF

AFO00100

B101000

C000111

D000000

E110100

FLO10010

其中頂點(diǎn)A的入度為2,出度為1；

其中頂點(diǎn)B的入度為2,出度為2;

其中頂點(diǎn)C的入度為1,出度為3；

14.已知圖5.32如下所示，求從頂點(diǎn)a到其余各頂點(diǎn)的最短路徑。（給出求解過程）

5

答:

終點(diǎn)最短路徑求解過程

b6(a,b)5(a,c,b)

C3(a,c)

doo6(a,c,d)6(a,c,d)

eoo7(a,c,e)7(a,c,e)7(a,c,e)

fooooco9(a,c,d,f)9(a,c,d,f)

vjcbdef

S{a,c}{a,c,b}{a,c,d}{a,c,e}{a,c,d,f)

15.閱讀下列算法，并回答問題：

(1)假設(shè)串由合法的英文字母和空格組成，并以'\0作結(jié)束符。設(shè)串s="LJLIIIJamLJaLJLJLJstudent”(口表示空格符)，寫出f30

(s)的返回值；

(2)簡述算法f30的功能.

intf30(char*s)

答案：

(1)4

(2)算法功能：統(tǒng)計(jì)單詞的個(gè)數(shù)。

16.閱讀下列函數(shù)，并回答問題：

(1)假設(shè)隊(duì)列q中的元素為(a,b,c,d,e),其中“a”為隊(duì)頭元素。寫出執(zhí)行函數(shù)調(diào)用Conv(&q)后的隊(duì)列q；

(2)簡述算法Conv的功能。

答案：

(1)e,d,c,b,a

(2)將隊(duì)列里的值反轉(zhuǎn)

17.閱讀下列函數(shù)，并回答問題：

已知整形數(shù)組L[1。.8]中的元素依次為(19,18,15,17,16,13,12,10),閱讀下列函數(shù)，并寫出執(zhí)行函數(shù)調(diào)用sort(L,

8)時(shí)，對(duì)L進(jìn)行的頭兩趟(pass分別為0和1)處理結(jié)果。

答案:

(1)第一趟(pass=0)1915181617121310

(2)第二趟(pass=1)1915161812171013

18.已知帶頭結(jié)點(diǎn)的單鏈表中的關(guān)鍵字為整數(shù)，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設(shè)散列表的

長度為m,散列函數(shù)為Hash(key尸key%m。鏈表的結(jié)點(diǎn)結(jié)構(gòu)為：.請(qǐng)?jiān)诳杖碧幪钊脒m當(dāng)內(nèi)容，使其成為一個(gè)完整算法。

keynext

答案：

(1)NULL(2)p—>next=H[j]p=q

19.下列函數(shù)的功能是,對(duì)以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)的兩個(gè)遞增有序表(表中不存在值相同的數(shù)據(jù)元素)進(jìn)行如下操

作：將所有在Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La中，其中La和Lb分別為兩個(gè)鏈表的頭指針。請(qǐng)?jiān)诳杖碧幪?/p>

入合適內(nèi)容，使其成為一個(gè)完整的算法。

答案：

(1)pre-〉next=pb(2)pre->next=pa(3)pre-〉next=pb

20.閱讀算法f30,并回答問題：下列算法為有向圖拓?fù)渑判颍?qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。

答案：

(l)top=-1(2)top=graph[j].count(3)graph[k].count==0

21.閱讀算法131,并回答問題：下列算法功能為在數(shù)組a的前n(n>=l)個(gè)元素中找出第k(l〈=k<=n)小的值.這里假設(shè)數(shù)組

a中各元素的值都不相同。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。

答案：

(1)(i==k)return;(2)i+l(3)i—1

22.閱讀算法f33,并回答問題:下列算法功能為奇偶交換排序，思路如下：第一趟對(duì)所有奇數(shù)的i,將aLi]和a[i+l]進(jìn)行

比較,第二趟對(duì)所有偶數(shù)的i,將a[i]和a[i+l]進(jìn)行比較,每次比較時(shí)若a[i]〉a[i+1],將二者交換；以后重復(fù)上述二

趟過程，直至整個(gè)數(shù)組有序。請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容，使其成為一個(gè)完整的算法。

答案：

(l)a[i]=t(2)(i=2；i<=n;i+=2)(3)flag

四、算法設(shè)計(jì)題(本大題共2小題，每小題10分，共20分)

1.已知單鏈表的結(jié)點(diǎn)類型為Lnode,包含next和data成員。編寫算法，實(shí)現(xiàn)帶頭結(jié)點(diǎn)單鏈表的逆置算法。

參考答案:

voidinvent(Lnode*head)

(

Lnode*p,*q；

if(!head—〉next)returnERROR；

p=head—〉next；q=p->next;p->next=NULL;

while(q)

{p=q;q=q-)next；p->next=head->next;head—>next=p;}

)

2.編寫一個(gè)函數(shù)，要求借助一個(gè)棧把一個(gè)數(shù)組中的數(shù)據(jù)元素逆置。

其中，棧類型為SeqStack,可以直接使用InitStack(SeqStack**)、

Push(SeqStack*,ElemType)、Pop(SeqStack*,ElemType*)函數(shù)。

參考答案：

voidInverse(ElemTypearr[],intn)

(

SeqStack*s；

inti;

InitStack(&s);

for(i=0；i〈n；i++)〃數(shù)組元素依次入棧

Push(s,arr[i])；

for(i=0;i<n;i++)〃棧中元素依次出棧，存入數(shù)組，是數(shù)組逆序

Pop(s,&arr[i])；

}

3.二叉樹采用鏈接存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)類型為Btree,包括left、right和data三個(gè)成員，試設(shè)計(jì)一個(gè)算法計(jì)算一棵給定二叉樹的度

為2的結(jié)點(diǎn)的個(gè)數(shù)。

參考答案：

inttwochild(Btree*b)

{intnuml,num2;

if(b==NULL)return0；

else

{numl=twochild1(b一〉left)；

num2=twochildl(b—>right)；

if(b—>left!=NULL&&b—〉right!=NULL)return(numl+num2+l)；

elsereturn(numl+num2);

}

4.假設(shè)以帶雙親指針的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，其結(jié)點(diǎn)結(jié)構(gòu)的類型說明如下所示：

typedefcharDataType；

typedefstructnode{

DataTypedata;

structnode*lchild,^rchild；//左右孩子指針

structnode*parent；〃指向雙親的指針

}BinTNode;

typedefBinTNode*BinTree;

若px為指向非空二叉樹中某個(gè)結(jié)點(diǎn)的指針，可借助該結(jié)構(gòu)求得px所指結(jié)點(diǎn)在二叉樹的中序序列中的后繼.

(1)就后繼的不同情況，簡要敘述實(shí)現(xiàn)求后繼操作的方法；

參考答案：

(1)分兩種情況討論

①當(dāng)*px的右子樹不為空時(shí)，則從*px的右孩子開始，沿其左孩子往下查找，直到找到一個(gè)沒有左孩子的節(jié)點(diǎn)為止，則該

結(jié)點(diǎn)為*px在中序序列中的后繼；

②當(dāng)*px的右孩子為空時(shí)，則沿*px的雙親指針鏈向上查找，直至找到其左子樹中包含*px的最年輕祖先，則該祖先結(jié)

點(diǎn)為*px在中序序列中的后繼.

(2)編寫算法求px所指結(jié)點(diǎn)的中序序列后繼,并在算法語句中加注注釋.

(2)BinTreef34(BinTreepx)

|

BinTreeq=px->rchild；

if(q!=NULL){〃沿左孩子往下查找

px=q；

while(px-)lchild!=NULL)

px=px->lchild；

}

else{〃沿雙親指針鏈向上查找

while(px!=NULL&&px—>rchild==q){

q=px；

px=px——>parent;

}

}

returnpx;〃返回所找到的中序序列后繼結(jié)點(diǎn)的指針

〃或者無后繼結(jié)點(diǎn)時(shí)返回空指針

5.已有鄰接表表示的有向圖，請(qǐng)編程判斷從第u頂點(diǎn)至第v頂點(diǎn)是否有簡單路徑，若有則印出該路徑上的頂點(diǎn)。

參考答案：

voidAllSPdfs(AdjListg,vertypeu,vertypev)

{〃求有向圖g中頂點(diǎn)u到頂點(diǎn)v的所有簡單路徑，初始調(diào)用形式：AllSPdfs(