數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)章節(jié)試題(附答案)

第一章概論自測(cè)題答案

一、填空題

1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系

和運(yùn)算等的學(xué)科。

2.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R）,其中D是數(shù)據(jù)元素的有限集合,R是D上的關(guān)系有限

集合。

3.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算這三個(gè)方面的內(nèi)容。

4.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

5.線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系,樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系,圖形結(jié)構(gòu)中元素之間存

在多對(duì)多關(guān)系。

6.在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)

沒(méi)有后續(xù)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。

7.在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn):葉子結(jié)點(diǎn)沒(méi)

有后續(xù)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。

8.在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。

9.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是順序、鏈?zhǔn)?、索引和散列?/p>

10.數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入、刪除、修改、查找、排序。

11.一個(gè)算法的效率可分為時(shí)間效率和空間效率。

二、單項(xiàng)選擇題

（B）1.非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種:

A）一對(duì)多關(guān)系B）多對(duì)多關(guān)系C）多對(duì)一關(guān)系D）一對(duì)一關(guān)系

（C）2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的結(jié)構(gòu)；

A）存儲(chǔ)B）物理C）邏輯D）物理和存儲(chǔ)

（C）3.算法分析的目的是：

A）找出數(shù)據(jù)結(jié)構(gòu)的合理性B）研究算法中的輸入和輸出的關(guān)系

C）分析算法的效率以求改進(jìn)D）分析算法的易懂性和文檔性

（A）4.算法分析的兩個(gè)主要方面是：

A）空間復(fù)雜性和時(shí)間復(fù)雜性B）正確性和簡(jiǎn)明性

C）可讀性和文檔性D）數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

（C）5.計(jì)算機(jī)算法指的是：

A）計(jì)算方法B）排序方法C）解決問(wèn)題的有限運(yùn)算序列D）調(diào)度方法

（B）6.計(jì)算機(jī)算法必須具備輸入、輸出和等5個(gè)特性。

A)可行性、可移植性和可擴(kuò)充性B)可行性、確定性和有窮性

C)確定性、有窮性和穩(wěn)定性D)易讀性、穩(wěn)定性和安全性

三、簡(jiǎn)答題

1.簡(jiǎn)述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。

答：線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對(duì)多的。

2.數(shù)據(jù)結(jié)構(gòu)的常見的四種存儲(chǔ)方式。

答：順序、鏈?zhǔn)?、索引和散列?/p>

3.數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)主要有哪兩大類，具體是什么？

答：主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，其中線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一的，非線性結(jié)構(gòu)反

映結(jié)點(diǎn)間的邏輯關(guān)系是多對(duì)多的。非線性結(jié)構(gòu)又包含樹結(jié)構(gòu)和圖結(jié)構(gòu)

四、分析下面各程序段的時(shí)間復(fù)雜度

1.for(i=0;i<n;i++)

2.s=0;

for(j=0;j<m;j++)

fori=0;i<n;i++)

A[i]|jJ=O；

for(j=0;j<n;j++)

答：0(m*n)

+=B[i]U];

sum=s;

答：0(i?)s

3.x=0;

for(i=l;i<n;i++)

for(j=1;j<=n-i;j++)

x++;

4.i=l;

解：因?yàn)閤++共執(zhí)行了n-l+n-2+....+1=

while(i<=n)

n(n-l)/2,

所以執(zhí)行時(shí)間為O(n?)i=i*3;

答：O(log?。)

f=lJ=?+l1=1L

五、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=(D,R),試按各小題所給條件畫出這些邏輯結(jié)構(gòu)的圖示，并確定相對(duì)于關(guān)系R,

哪些結(jié)點(diǎn)是開始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？

1.

D={dl,d2,d3,d4}R={(dl,d2),(d2,d3),(d3,d4)}

答:dl-d2fd3fd4dl一無(wú)直接前驅(qū)，是首結(jié)點(diǎn)d4一無(wú)直接后繼是尾結(jié)點(diǎn)

2oD={dl,d2,-,d9}

R={(dl,d2),(dl,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5),(d6,d7),(d8,d9)}

答：此圖為樹形結(jié)構(gòu)dl一無(wú)直接前驅(qū)，是根結(jié)點(diǎn)d2,d5,d7,d9一無(wú)直接后繼是葉子結(jié)點(diǎn)

3.D={dl,d2,d9}

R={(dl,d3),(dl,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9),(d5,d6),(d8,d9),(d9,d7),(d4,d7),

(d4,d6)}

答：此圖為圖形結(jié)構(gòu)dl,d2一無(wú)直接前驅(qū)，是開始結(jié)點(diǎn)d6,d7一無(wú)直接后繼是終端結(jié)點(diǎn)

(2)(3)

第3章棧和隊(duì)列自測(cè)卷答案

一、填空題(每空1分，共15分)

1.【李春葆】向量、棧和隊(duì)列都是線性結(jié)構(gòu),可以在向量的任何位置插入和刪除元素;對(duì)

于棧只能在棧頂插入和刪除元素;對(duì)于隊(duì)列只能在隊(duì)尾插入和隊(duì)首刪除元素。

2.棧是一種特殊的線性表，允許插入和刪除運(yùn)算的--端稱為棧頂。不允許插入和刪除運(yùn)算的一端

稱為棧底。

3.隊(duì)列是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另?端進(jìn)行刪除運(yùn)算的線性表。

4.在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的前一個(gè)位置。

5.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有n-1個(gè)元素。

6.向棧中壓入元素的操作是先移動(dòng)棧頂指針，后存入元素。

7.從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先移動(dòng)隊(duì)首指針，后取出元素。

8.K00年統(tǒng)考題》帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長(zhǎng)度等于0。

解：

headIL=head|頭結(jié)點(diǎn)IR=heaJ-

二、判斷正誤(判斷下列概念的正確性，并作出簡(jiǎn)要的說(shuō)明。)(每小題1分，共10分)

(X)1.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。

錯(cuò)，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類型無(wú)關(guān)。

(X)2.在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。

錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊(duì)列。

(V)3.棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。

（J）4.對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。

正確，都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。

（X）5.棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。

錯(cuò)，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲(chǔ)結(jié)構(gòu)概念，二者不是同類項(xiàng)。

（X）6.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。

錯(cuò)，他們都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。

（V）7.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。

（V）8.兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底

分別設(shè)在這片內(nèi)存空間的兩端。

（X）9.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。

錯(cuò)，后半句不對(duì)。

（X）10.一個(gè)棧的輸入序列是12345,則棧的輸出序列不可能是12345。

錯(cuò),有可能。

三、單項(xiàng)選擇題（每小題1分，共20分）

（B）1.K00年元月統(tǒng)考題11棧中元素的進(jìn)出原則是

A.先進(jìn)先出B.后進(jìn)先出C.棧空則進(jìn)D.棧滿則出

（C）2.R李春葆】若已知一個(gè)棧的入棧序列是1,2,3,…，n,其輸出序列為pl,p2,p3,…，

pn,若pl=n,則pi為

A.iB.n=iC.n-i+1D.不確定

解釋：當(dāng)pl=n,即n是最先出棧的，根據(jù)棧的原理，n必定是最后入棧的（事實(shí)上題目已經(jīng)表明了），那

么輸入順序必定是1,2,3,…，n,則出棧的序列是n,…，3,2,1?

（若不要求順序出棧，則輸出序列不確定）

（B）3.K李春葆】判定一個(gè)棧ST（最多元素為m0）為空的條件是

A.ST->topoOB.ST->top=0C.ST->topomOD.ST->top=mO

（A）4.K李春葆1判定一個(gè)隊(duì)列QU（最多元素為mO）為滿隊(duì)列的條件是

A.QU->rear—QU->front==mOB.QU->rear—QU->front_1==mO

C.QU->front==QU->rearD.QU->front==QU->rear+l

解：隊(duì)滿條件是元素個(gè)數(shù)為mO。山于約定滿隊(duì)時(shí)隊(duì)首指針與隊(duì)尾指針相差1,所以不必再減1f,應(yīng)當(dāng)選

Ao當(dāng)然，更正確的答案應(yīng)該取模，即：QU->fronl==（QU->rear+1）%mO

（D）5.數(shù)組Q[n]用來(lái)表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素的前一位置，r為隊(duì)尾元素的

位置，假定隊(duì)列中元素的個(gè)數(shù)小于n,計(jì)算隊(duì)列中元素的公式為

(A)r—f;(B)(n+f—r)%n;(C)n+r—f;(D)(n+r—f)%n

6.198初程P71】從供選擇的答案中，選出應(yīng)填入下面敘述內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫

在答卷的對(duì)應(yīng)欄內(nèi)。

設(shè)有4個(gè)數(shù)據(jù)元素al、a2、a3和a4,對(duì)他們分別進(jìn)行棧操作或隊(duì)操作。在進(jìn)?；蜻M(jìn)隊(duì)操作時(shí)，按al、

a2、a3、a4次序每次進(jìn)入?個(gè)元素。假設(shè)?；蜿?duì)的初始狀態(tài)都是空。

現(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時(shí)，第一次出棧得到的元素是—A

,第二次出棧得到的元素是是；類似地，考慮對(duì)這四個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩次，出

隊(duì)一次，再進(jìn)隊(duì)兩次，出隊(duì)一次；這時(shí)，第一次出隊(duì)得到的元素是C,第二次出隊(duì)得到的元素是D

。經(jīng)操作后，最后在棧中或隊(duì)中的元素還有一個(gè)。

供選擇的答案:

A-D：①al②a2③a3④a4

E：①1②2③3④0

答：ABCDE=21AA2

7.194初程P75】從供選擇的答案中，選出應(yīng)填入下面敘述？?jī)?nèi)的最確切的解答,把相應(yīng)編號(hào)寫

在答卷的對(duì)應(yīng)欄內(nèi)。

棧是一種線性表，它的特點(diǎn)是上。設(shè)用一維數(shù)組A”,…,n］來(lái)表示一個(gè)棧，A［n］為棧底，用整型變

量T指示當(dāng)前棧頂位置，A［T］為棧頂元素。往棧中推入（PUSH）一個(gè)新元素時(shí)，變量T的值_；從棧

中彈出（POP）一個(gè)元素時(shí)，變量T的值C。設(shè)?？諘r(shí)，有輸入序列a,b,c,經(jīng)過(guò)PUSH,POP,PUSH,

PUSH,POP操作后，從棧中彈出的元素的序列是_，變量T的值是）

供選擇的答案:

A：①先進(jìn)先出②后進(jìn)先出③進(jìn)優(yōu)于出④出優(yōu)于進(jìn)⑤隨機(jī)進(jìn)出

B,C：①加1②減1③不變④清0⑤加2⑥減2

D：①a,b②b,c③c,a@b,a⑤c,b@a,c

E：①n+1②n+2③n④n-1⑤n-2

答案：ABCDE=2,2.1,6,4

注意，向地址的高端生長(zhǎng)，稱為向上生成堆棧；向地址低端生長(zhǎng)叫向下生成堆棧，本題中底部為n,向地

址的低端遞減生成，稱為向F生成堆棧。

8.191初程P77】從供選擇的答案中，選出應(yīng)填入下面敘述內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫

在答卷的對(duì)應(yīng)欄內(nèi)。

在做進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否A；在做退棧運(yùn)算時(shí)，應(yīng)先判別棧是否」。當(dāng)棧中元素為

n個(gè)，做進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明該棧的最大容量為C

為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的D

分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng)E時(shí),才產(chǎn)生上溢。

供選擇的答案:

A,B：①空②滿③上溢④下溢

C：①n-1②n③n+1④n/2

D：①長(zhǎng)度②深度③棧頂④棧底

E：①兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn)②其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn)

③兩個(gè)棧的棧頂在達(dá)?？臻g的某一位置相遇④兩個(gè)棧均不空，且個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底

答案：ABCDE^2,1,2,4,3

四、簡(jiǎn)答題（每小題4分，共20分）

1.【嚴(yán)題集3.2①和3.11①】說(shuō)明線性表、棧與隊(duì)的異同點(diǎn)。

劉答：相同點(diǎn)：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特

殊的線性表，即受限的線性表，只是對(duì)插入、刪除運(yùn)算加以限制。

不同點(diǎn)：①運(yùn)算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入、刪除運(yùn)算，因而是后進(jìn)先

出表LIFO；隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。

②用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng)，隊(duì)列用于多道作業(yè)處理、指令寄存及其他運(yùn)算等等。

2.【統(tǒng)考書P604-11,難于嚴(yán)題集3.1①】設(shè)有編號(hào)為1,2,3,4的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的

車站，具體寫出這四輛列車開出車站的所有可能的順序。

劉答：至少有14種。

①全進(jìn)之后再出情況，只有1種：4,3,2,1

②進(jìn)3個(gè)之后再出的情況，有3種，3,4,213,2,4,13,2,1,4

③進(jìn)2個(gè)之后再出的情況，有5利24,3,12,3,4,12,1,3,42,1,4,32,1,3,4

④進(jìn)1個(gè)之后再出的情況，有5種，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,3

3.【劉自編】假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba'和'abcba'是回文，'abcde'

和＜ababab,則不是回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請(qǐng)分析用線性表、堆棧和隊(duì)列等方式正確輸出

其回文的可能性？

答：線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)變量（j-）從表尾開始打印輸出；

堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；

隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。

哪種方式最好，要具體情況具體分析。若正文在機(jī)內(nèi)已是順序存儲(chǔ)，則直接用線性表從后往前讀取即

可，或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用POP動(dòng)作實(shí)現(xiàn)。（但堆棧是先減后壓還是……）

若正文是單鏈表形式存儲(chǔ)，則等同于隊(duì)列，需開輔助空間，可以從鏈?zhǔn)组_始入棧，全部壓入后再依次

輸出。

4.【統(tǒng)考書P604-13］順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿?

答：一般的一維數(shù)組隊(duì)列的尾指針己經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，

這就叫“假溢出

采用循環(huán)隊(duì)列是解決假溢出的途徑。

另外，解決隊(duì)滿隊(duì)空的辦法有三：

①設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空；

②浪費(fèi)一個(gè)元素的空間，用于區(qū)別隊(duì)滿還是隊(duì)空。

③使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長(zhǎng)度）。

我們常采用法②，即隊(duì)頭指針、隊(duì)尾指針中有一個(gè)指向?qū)嵲?，而另一個(gè)指向空閑元素。

判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是：f=rear隊(duì)滿標(biāo)志是：f=（r+l）%N

5.【統(tǒng)考書P604-14］設(shè)循環(huán)隊(duì)列的容量為40（序號(hào)從0到39）,現(xiàn)經(jīng)過(guò)一系列的入隊(duì)和出隊(duì)運(yùn)算后，有

①front=ll,rear=19;②front=19,rear=ll；問(wèn)在這兩種情況下，循環(huán)隊(duì)列中各有元素多少個(gè)？

答：用隊(duì)列長(zhǎng)度計(jì)算公式：（N+r—f）%N

①L=（40+19-11）%40=8②L=（40+11-19）%40=32

五、閱讀理解（每小題5分，共20分。至少要寫出思路）

1.【嚴(yán)題集3.7①】按照四則運(yùn)算加、減、乘、除和幕運(yùn)算（t）優(yōu)先關(guān)系的慣例，并仿照教材例3-2的

格式，畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過(guò)程：

A-BXC/D+EtF

當(dāng)前字符備注

序號(hào)OPTR棧OPND棧

A—B?C/D+E■FU（操作）

1U*push(OPND,'A')

2nA?pushCOPTR/-*)

3A?push(OPND,'B')

4#一AB?push(OPTR,***)

5#—?AB?push(OPND.rC)

6#—?ABC*歸約.令Ti=B*C

7#一AT.*push(OPTRZ/*)

8#一AT.*push(OPND/iy)

9#-/ATjD*歸約.令TLT/D

10#一/AT：*歸約.令T嚴(yán)A-T;

11nT,?push(OPTR/+r)

12#+T,?push(OPND/Er)

13廿十T,E*push(OPTR/f#)

14TjE?push(OPND/F)

15#4-tTjEF*歸約.令T,=E+F

*

16#+T,T4歸約.令Ts=T,+T.

f17#T*return(Ts)

答：-----s

2.1嚴(yán)題集3.3@］寫出下列程序段的輸出結(jié)果(棧的元素類型SElemType為char)。

voidmain(){

StackS;

Charx,y;

InitStack(S);

X='c';y='k';

Push(S,x);Push(S/a,);Push(S,y);

Pop(S,x);Push(S,'l');Push(S,x);

Pop(S,x);Push(S,'s');

while(!StackEmpty(S)){Pop(S,y);printf(y);};

Printf(x);

)

答：輸出為“stack”。

2.【嚴(yán)題集3.12②】寫出下列程序段的輸出結(jié)果(隊(duì)列中的元素類型QElemType為char)。

voidmain(){

QueueQ;InitQueue(Q);

Charx=,e,;y=,c,;

EnQueue(Q,'h')；EnQueue(Q,'r‘)；EnQueue(Q,y);

DeQueue(Q,x);EnQueue(Q,x);

DeQueue(Q,x)；EnQueue(Q,'a')；

while(!QueueEmpty(Q)){DeQueue(Q,y)；printf(y);};

Printf(x);

)

答:輸出為“char”。

3.【嚴(yán)題集3.13@]簡(jiǎn)述以下算法的功能(棧和隊(duì)列的元素類型均為int)o

voidalgo3(Queue&Q){

StackS;intd;

InitStack(S);

while(IQueueEmpty(Q)){

DeQueue(Q,d);Push(S,d)；

)；

while(!StackEmpty(S)){

Pop(S,d);EnQueue(Q,d);

)

)

答：該算法的功能是：利用堆棧做輔助，將隊(duì)列中的數(shù)據(jù)元素進(jìn)行逆置。

六、算法設(shè)計(jì)(每小題5分，共15分。至少要寫出思路)

1.【李春葆及嚴(yán)題集3.19@]假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧三種類型的括弧，編

寫一個(gè)判別表達(dá)式中括弧是否正確配對(duì)的函數(shù)correct(exp,tag)；其中：exp為字符串類型的變量(可理

解為每個(gè)字符占用一個(gè)數(shù)組元素)，表示被判別的表達(dá)式，tag為布爾型變量。

答：用堆棧st進(jìn)行判定，將目、或卬入棧，當(dāng)遇到5、[±\或H時(shí)，檢查當(dāng)前棧頂元素是否是對(duì)

應(yīng)的口、匚口或E，若是則退棧，否則返回表示不配對(duì)。當(dāng)整個(gè)算術(shù)表達(dá)式檢查完畢時(shí)，若棧為空表示括

號(hào)正確配對(duì)，否則不配對(duì)。

編程后的整個(gè)函數(shù)如下(李書P31—32)

#definemO100/*m0為算術(shù)表達(dá)式中最多字符個(gè)數(shù)*/

correct(exp,tag)

charexp[m0];

inttag;

{charst[mO];

inttop=0,i=l;

tag=l;

while(i<=m0&&tag)

{if(exp[i]==<(<llexp[i]==>[1lexp[i]=/*遇到'『或則將其入棧*/

{top++;

st[top]=explij;

)

if(exp[i]==9?)/*遇到)，若棧頂是中,則繼續(xù)處理,否則以不配對(duì)返回*/

if(st[top]=='(')top";

elsetag=0;

if(exp[i]==33/*遇到']'，若棧頂是'['，則繼續(xù)處理，否則以不配對(duì)返回*/

if(st[top]=='[']top—;

elsetag=0;

if(exp[i]==7)信遇到，}',若棧頂是則繼續(xù)處理,否則以不配對(duì)返回*/

if(st[top]==4{4top—;

elsetag=0;

i++；

)

if(top>0)tag=0;/*若棧不空，則不配對(duì)*/

)

嚴(yán)題集對(duì)應(yīng)答案：

3.19

StatusAllBrackets_Test(char*str)〃判別表達(dá)式中三種括號(hào)是否匹配

(

InitStack(s);

for(p=str;*p;p++)

(

if(*p==?(,ll*p==,[,ll*p==,{')push(s,*p);

elseif(*p==》[*p==TII*p=丁)

(

if(StackEmpty(s))returnERROR;

pop(s,c);

if(*p==')'&&c!=,(,)returnERROR;

if(*p==T&&c!='「)returnERROR;

if(*p==T&&c!±{)returnERROR;〃必須與當(dāng)前棧頂括號(hào)匹配

)

)//for

if(!StackEmpty(s))returnERROR;

returnOK;

}//AllBrackets_Test

2001級(jí)通信6班張沐同學(xué)答案(已上機(jī)通過(guò))

#include<stdio.h>

#include<stdlib.h>

voidpush(charx);

voidpop();

voidcorrect(enumBoolean&tag);

〃原來(lái)的定義是voidcorrect(structStack*head,enumBoolean&tag);

typedefstructStack

(

chardata;

structStack*next;

)；

structStack*head,*p;

enumBoolean{FALSE,TRUEJtag;

voidmain()

(

head=(structStack*)malloc(sizeof(structStack));

head->data=,S,;

head->next=NULL;

//head'sdatahasnotbeeninitialized!!

correct(tag);

if(tag)

printf(MRight!M);

else

printf("Wrong!u);

voidpush(charx)

p=(structStack*)malloc(sizeof(structStack));

if(!p)

printfC'There'snospace.\nn);

else

(

p->data=x;

p->next=head;

head=p;

)

)

IIifyoudefinethe"Correct"functionlikethat

//DebugwillshowthatthePushactiondoesn'ttakeeffection

voidpop()

(

if(head->next==NULL)

printf(nThestackisempty.\nn);

else

(

p=head;

head=head->next;

free(p);

//voidcorrect(structStack*head,enumBoolean&tag)

voidcorrect(enumBoolean&tag)

(

inti;

chary;

printf("Pleaseenterabds:n);

for(i=0;y!=\n';i++)

scanf("％c”,&y);

if((y==y&&head->data==,(,)ll(y=='],&&head->data==,[,)ll(y==,},&&head->data=='{'))

pop();

elseif((y=='(')ll(y=='[')H(y=='{'))

push(y);

/*調(diào)試程序顯示，y并沒(méi)有被推入堆棧中。即head->data的值在Push中顯示為y的值，但是出Push函數(shù)。

馬上變成Null。*/

else

continue;

}

if(head->next==NULL)〃原來(lái)的程序是if(head==NULL)tag=TRUE;

tag=TRUE;

else

tag=FALSE;

)

/*總結(jié)：由于head為全局變量，所以不應(yīng)該將其再次作為函數(shù)的變量。因?yàn)镃語(yǔ)言的函數(shù)變量是傳值機(jī)

制，所以在函數(shù)中對(duì)參數(shù)進(jìn)行了拷貝復(fù)本，所以不能改變head的數(shù)值。*/

2.【統(tǒng)考書P604-15]假設(shè)一個(gè)數(shù)組squ[m]存放循環(huán)隊(duì)列的元素。若要使這m個(gè)分量都得到利用，則需

另一個(gè)標(biāo)志tag,以tag為0或1來(lái)區(qū)分尾指針和頭指針值相同時(shí)隊(duì)列的狀態(tài)是“空"還是“滿二試編寫

相應(yīng)的入隊(duì)和出隊(duì)的算法。

解：這就是解決隊(duì)滿隊(duì)空的三種辦法之①設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空(其他兩種見筒答題)；

思路：一開始隊(duì)空，設(shè)tag=O,若從rear端加到與front指針相同時(shí)，發(fā)示入隊(duì)已滿，則令tag=l；

若從front一端加到與rear指針相同時(shí)，則令tag=0,表示出隊(duì)己空。

3.【嚴(yán)題集3.31③】試寫一個(gè)算法判別讀入的一個(gè)以'@'為結(jié)束符的字符序列是否是“回文

答：編程如下：

intPalindrome_Test()〃判別輸入的字符串是否回文序列，是則返回1,否則返回0

(

InitStack(S);InitQueue(Q);

while((c=getchar())!='@')

(

Push(S,c);EnQueue(Q,c)；〃同時(shí)使用棧和隊(duì)列兩種結(jié)構(gòu)

)

while(!StackEmpty(S))

Pop(S,a);DeQueue(Q,b));

if(a!=b)returnERROR;

returnOK;

}//Palindrome_Test

第6章樹和二叉樹自測(cè)卷解答

一、下面是有關(guān)二叉樹的敘述，請(qǐng)判斷正誤（每小題1分，共10分）

（7）1.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有曰個(gè)非空指針域。

（X）2.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于1。

（V）3.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。

（X）4.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。

（X）5.二叉樹中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于

其右非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。（應(yīng)當(dāng)是二叉排序樹的特點(diǎn)）

（X）6.二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是2kL1,其中k是樹的深度。（應(yīng)2」）

（X）7.二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。

（X）8.對(duì)于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有要一1個(gè)結(jié)點(diǎn)。（應(yīng)2"）

（J）9用二叉鏈表法Qink-rlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為

空指針。

（正確。用二叉鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)共有2n個(gè)鏈域。由于二叉樹中，除根結(jié)點(diǎn)外，每

一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，所以只有n-1個(gè)結(jié)點(diǎn)的鏈域存放指向非空子女結(jié)點(diǎn)的指針，還有n+1個(gè)空指

針。）即有后繼鏈接的指針僅n-1個(gè)。

（V）10.K01年計(jì)算機(jī)系研題》具有12個(gè)結(jié)點(diǎn)的完全二叉樹有5個(gè)度為2的結(jié)點(diǎn)。

最快方法：用葉子數(shù)=fn/2]=6,再求n2=n（＞-l=5

二、填空（每空1分，共15分）

1.由3個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有_匚種形態(tài)。

2.【計(jì)算機(jī)研2000】一棵深度為6的滿二叉樹有n!+n2=0+n2=111rl=31個(gè)分支結(jié)點(diǎn)和2.=32個(gè)葉

子。

注：滿二叉樹沒(méi)有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。

3.一棵具有257個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為9。

（注：用Llog2（n）」+l=L8.xx」+1=9

4.【全國(guó)專升本統(tǒng)考題】設(shè)一棵完全二叉樹有700個(gè)結(jié)點(diǎn)，則共有350個(gè)葉子結(jié)點(diǎn)。

答：最快方法：用葉子數(shù)=皿2]=350

5.設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有500個(gè)葉子結(jié)點(diǎn),有499個(gè)度為2的結(jié)

點(diǎn)，有個(gè)結(jié)點(diǎn)只有非空左子樹，有0個(gè)結(jié)點(diǎn)只有非空右子樹。

答：最快方法：用葉子數(shù)=[n⑵=500,n2=n0-l=499o另外，最后一結(jié)點(diǎn)為2i屬于左葉子，右葉子是空

的，所以有1個(gè)非空左子樹。完全二叉樹的特點(diǎn)決定不可能有左空右不空的情況，所以非空右子樹數(shù)=0.

6.【嚴(yán)題集6.7③】一棵含有n個(gè)結(jié)點(diǎn)的k叉樹，可能達(dá)到的最大深度為口,最小深度為2。

答：當(dāng)k=l（單叉樹）時(shí)應(yīng)該最深，深度=n（層）；當(dāng)k=n-l（n-1叉樹）時(shí)應(yīng)該最淺，深度=2（層），但不

包括n=0或1時(shí)的特例情況。教材答案是“完全k叉樹"，未定量。）

7.196程試題1】二叉樹的基本組成部分是：根（N）、左子樹（L）和右子樹（R）。因而二叉樹的遍

歷次序有六種。最常用的是三種：前序法（即按NLR次序），后序法（即按LRN次序）和中序

法（也稱對(duì)稱序法，即按LNR次序）。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹的前序序列是

BEFCGDH,中序序列是FEBGCHD,則它的后序序列必是FEG

HDCB<,

解：法1：先由已知條件畫圖，再后序遍歷得到結(jié)果；

法2：不畫圖也能快速得出后序序列，只要找到根的位置特征。由前

序先確定root,由中序先確定左子樹。例如，前序遍歷BEFCGDH中，

根結(jié)點(diǎn)在最前面，是B；則后序遍歷中B一定在最后面。

法3：遞歸計(jì)算。如B在前序序列中第一，中序中在中間（可知左

右子樹上有哪些元素），則在后序中必為最后。如法對(duì)B的左右子樹同樣處理，則問(wèn)題得解。

8.【全國(guó)專升本統(tǒng)考題】中序遍歷的遞歸算法平均空間復(fù)雜度為0（n）。

答：即遞歸最大嵌套層數(shù)，即棧的占用單元數(shù)。精確值應(yīng)為樹的深度k+1,包括葉子的空域也遞歸了一次。

9.1計(jì)算機(jī)研2001）用5個(gè)權(quán)值｛3,2,4,5,1｝構(gòu)造的哈夫曼（Huffman）樹的帶權(quán)路徑長(zhǎng)度是33。

解：先構(gòu)造哈夫曼樹，得到各葉子的路徑長(zhǎng)度之后便可求出WPL=（4+5+3）X2+（1+2）X3=33

（注：兩個(gè)合并值先后不同會(huì)導(dǎo)致編碼不同，即哈夫曼編碼不唯一）

（注：合并值應(yīng)排在葉子值之后）

（注：原題為選擇題：A.32B.33C.34D.15）

三、單項(xiàng)選擇題（每小題1分，共11分）

（C）1.不含任何結(jié)點(diǎn)的空樹

（A）是一棵樹；（B）是一棵二叉樹；

（C）是一棵樹也是一棵二叉樹；（D）既不是樹也不是二叉樹

答：以前的標(biāo)答是B,因?yàn)槟菚r(shí)樹的定義是n2l

（C）2.二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以

(A)它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)；(B)它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)；

(C)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)；(D)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使

用

(C)3.K01年計(jì)算機(jī)研題X具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為。

(A)Flog2(n)l(B)Llog2(n)J(C)Llog2(n)J+l(D)riog2(n)+ll

注1：「xl表示不小于x的最小整數(shù)：Lx」表示不大于x的最大整數(shù)，它們與口含義不同！

注2：選(A)是錯(cuò)誤的。例如當(dāng)n為2的整數(shù)基時(shí)就會(huì)少算一層。似乎11。826)+1」是對(duì)的？

(A)4.把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是。

(A)唯一的(B)有多種

(C)有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子(D)有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子

5.194程PU】從供選擇的答案中，選出應(yīng)填入下面敘述？?jī)?nèi)的最確切的解答,把相應(yīng)編號(hào)寫在

答卷的對(duì)應(yīng)欄內(nèi)。

樹是結(jié)點(diǎn)的有限集合，它在根結(jié)點(diǎn)，記為T。其余的結(jié)點(diǎn)分成為m(m20)個(gè)」

的集合Tl,T2,…，Tm,每個(gè)集合又都是樹，此時(shí)結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn)，「稱為T的子結(jié)點(diǎn)(IWiWm)。

一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的」

供選擇的答案

A：①有。個(gè)或1個(gè)②有0個(gè)或多個(gè)③有且只有1個(gè)④有1個(gè)或1個(gè)以上

B:①互不相交②允許相交③允許葉結(jié)點(diǎn)相交④允許樹枝結(jié)點(diǎn)相交

C：①權(quán)②維數(shù)③次數(shù)(或度)④序

答案：ABC=1,1,3

6.195程P13］從供選擇的答案中，選出應(yīng)填入下面敘述?內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在

答卷的對(duì)應(yīng)欄內(nèi)。

二叉樹Ao在完全的二叉樹中，若一個(gè)結(jié)點(diǎn)沒(méi)有B,則它必定是葉結(jié)點(diǎn)。每棵樹都能惟一地轉(zhuǎn)

換成與它對(duì)應(yīng)的二叉樹。由樹轉(zhuǎn)換成的二叉樹里，一個(gè)結(jié)點(diǎn)N的左子女是N在原樹里對(duì)應(yīng)結(jié)點(diǎn)的_^，

而N的右子女是它在原樹里對(duì)應(yīng)結(jié)點(diǎn)的o

供選擇的答案

A：①是特殊的樹②不是樹的特殊形式③是兩棵樹的總稱④有是只有二個(gè)根結(jié)點(diǎn)的樹形結(jié)構(gòu)

B:①左子結(jié)點(diǎn)②右子結(jié)點(diǎn)③左子結(jié)點(diǎn)或者沒(méi)有右子結(jié)點(diǎn)④兄弟

C-D：①最左子結(jié)點(diǎn)②最右子結(jié)點(diǎn)③最鄰近的右兄弟④最鄰近的左兄弟

⑤最左的兄弟⑥最右的兄弟

答案：A=B=C=D=

答案：ABCDE=2,1,1,3

四、簡(jiǎn)答題(每小題4分，共20分)

1.【嚴(yán)題集6.2①】一棵度為2的樹與一棵二叉樹有何區(qū)別？

答：度為2的樹從形式上看與二叉樹很相似，但它的子樹是無(wú)序的，而二叉樹是有序的。即，在一般樹中

若某結(jié)點(diǎn)只有一個(gè)孩子，就無(wú)需區(qū)分其左右次序，而在二叉樹中即使是個(gè)孩子也有左右之分。

2.R01年計(jì)算機(jī)研題》設(shè)如下圖所示的二叉樹B的存儲(chǔ)結(jié)構(gòu)為二叉

鏈表，root為根指針，結(jié)點(diǎn)結(jié)構(gòu)為：(lchild,data,rchild)。其中Ichild,C的結(jié)點(diǎn)類型定義如下：

rchild分別為指向左右孩子的指針，data為字符型，root為根指針，structnode

{chardata;

試回答下列問(wèn)題：structnode*lchild,rchild;

)；

1.對(duì)下列二叉樹B,執(zhí)行下列算法traversal(root),試指出其輸出結(jié)

果；C算法如下：

voidtraversal(structnode*root)

2.假定二叉樹B共有n個(gè)結(jié)點(diǎn)，試分析算法traversal(root)的時(shí)間復(fù){if(root)

{printf("%c”,root->data);

雜度。(共8分)traversal(root->lchild);

printf("%c”,root->data);

Atraversal(root->rchild);

B/\D

C/F/、G

\E

二叉樹B

解：這是“先根再左再根再右”，比前序遍歷多打印各結(jié)點(diǎn)一次，輸

出結(jié)果為：ABCCEEBADFFDGG

特點(diǎn)：①每個(gè)結(jié)點(diǎn)肯定都會(huì)被打印兩次；②但出現(xiàn)的順序不同，其規(guī)律是：凡是有左子樹的結(jié)點(diǎn)，必間隔

左子樹的全部結(jié)點(diǎn)后再重復(fù)出現(xiàn)；如A,B,D等結(jié)點(diǎn)。反之馬上就會(huì)重復(fù)出現(xiàn)。如C,E,F,G等結(jié)點(diǎn)。

時(shí)間復(fù)雜度以訪問(wèn)結(jié)點(diǎn)的次數(shù)為主，精確值為2*n,時(shí)間漸近度為O(n).

3.KOI年計(jì)算機(jī)研題』【嚴(yán)題集6.27③】給定二叉樹的兩種遍歷序列，分別是：

前序遍歷序列：D,A,C,E,B,H,F,G,I；中序遍歷序列：D,C,B,E,H,A,G,I,F,

試畫出二叉樹B,并簡(jiǎn)述山任意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹B的思想方法。

解：方法是：由前序先確定root,由中序可確定root的左、右子樹。然后由其左子樹的元素集合和右子

樹的集合對(duì)應(yīng)前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root,不

斷遞歸，則所有元素都將被唯一確定，問(wèn)題得解。

H

4.1計(jì)算機(jī)研2000】給定如圖所示二叉樹T,請(qǐng)畫出與其對(duì)應(yīng)的中序線索二叉樹。

解：要遵循中序遍歷的軌跡來(lái)畫出每個(gè)前驅(qū)和后繼。

25/73

中序遍歷序列：55402560280833544(70szz34

5V

28

25餐33

4411AAA

A40-二62：。83S4i

A-

55

五、閱讀分析題（每題5分，共20分）

1.（P604-26）試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。

答:DLR：ABDFJGKCEHILM

LDR:BFJDGKACHELIM

LRD：JFKGDBHLMIECA

2.（P604-27）把如圖所示的樹轉(zhuǎn)化成二叉樹。

答：注意全部兄弟之間都要連線（包括度為2