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

1

對數(shù)據(jù)結(jié)構(gòu)，下列結(jié)論不正確的是

A.相同的邏輯結(jié)構(gòu)，對應(yīng)的存儲結(jié)構(gòu)也必相同

B.數(shù)據(jù)結(jié)構(gòu)由邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和基本操作3個方面組成

C.數(shù)據(jù)存儲結(jié)構(gòu)就是數(shù)據(jù)邏輯結(jié)構(gòu)的機內(nèi)的實現(xiàn)

D.對數(shù)據(jù)基本操作的實現(xiàn)與存儲結(jié)構(gòu)有關(guān)

正確答案是：【A】

解析：

選項A錯誤的原因是相同的邏輯結(jié)構(gòu)可以由不同的存儲結(jié)構(gòu)來實現(xiàn)，例如線性

表可以用順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)來實現(xiàn)。數(shù)據(jù)結(jié)構(gòu)的操作在不同存儲結(jié)構(gòu)

下有不同的實現(xiàn)。

2

以下屬于邏輯結(jié)構(gòu)的是

A.順序表

B.散列表

C.有序表

D.單鏈表

正確答案是：【C】

解析：

選項A、B、D都屬于存儲結(jié)構(gòu)。其中選項C有序表是線性表的特例，要求每個

元素的值按其邏輯順序非降序排列，它是邏輯結(jié)構(gòu)。

3

若一個問題既可以用迭代方式也可以用遞歸方式求解，則（）的方法具有最高

的時空效率。

’A.迭代

「B.遞歸

「C.先遞歸后迭代

「D.先迭代后遞歸

正確答案是：【A】

解析:

遞歸函數(shù)在執(zhí)行過程中會多次重復(fù)已做過的計算，還會引起一系列的函數(shù)調(diào)用和

返回，需要較多的時間開銷和空間開銷。因此，實現(xiàn)相同功能，迭代算法比遞歸

算法更高效。

4

一個遞歸算法必須包括

「A.迭代部分

B.遞歸部分

C.終止條件和迭代部分

D.終止條件和遞歸部分

正確答案是：【D】

解析：

遞歸算法一般有兩部分：一是遞歸部分，它把復(fù)雜化簡，把規(guī)模較大的問題化為

規(guī)模相對較小的問題求解；另一部分為遞歸終止條件，即把規(guī)模減小到可以直接

求解的時候，就通過直接處理的語句給出遞歸終止的條件。

5

下面算法的時間復(fù)雜度是()。

inti=l,k=100;

while(i<n)){

k++;i+=2;

)

'A.O(n)

rB.O(n-)-

「C.O(l)

r口54)

正確答案是：【A】

解析：

設(shè)while循環(huán)語句執(zhí)行的次數(shù)為m,i從1開始每次遞增2,最后取值為l+2m,

有：i=l+2m<n,即m<(n-l)/2=0(n),所以算法的時間復(fù)雜度為0(n)

6

下面算法的時間復(fù)雜度是()。

inti=Ofs=O;

while(s<n){

i++;s+=i;

)

A.O(n)

fB.O(n-)-

「C.O(l)

rD5分)

正確答案是：【D】

解析：

設(shè)while循環(huán)語句執(zhí)行的次數(shù)為m,i從0開始每次遞增1,直到m-1為止，有:

s=0+l+2+...+m-l=m(m-l)/2,并滿足s=m(m-l)/2<n,則有mW—所以

算法的時間復(fù)雜度為。(石，)。

7

下面算法的時間復(fù)雜度是()。

y=o；

while(n>=(y+l)*(y+l)){

y++;

)

rA.O(n)

「B.O(吟

rC.O(l)

「D占,

正確答案是：【D】

解析:

程序每次循環(huán)將y的值增加1,然后比較n與(y+l)2大小，所以總共要進行分，

次比較。所以算法的時間復(fù)雜度為。(五______________________________

8

設(shè)n為偶數(shù)，分析下面程序段中算法的時間復(fù)雜度是()。

inti,j,m=O;

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

for(j=2*i;j<=n;j++)

m++;

(A.O(n)

'B.O(n:)-

rC.O(l)

rD°(石)

正確答案是：【B】

解析:

算法的基本操作是m++,由于內(nèi)循環(huán)從2*i~n,即i的最大值滿足：2isn,isn/2,

所以該語句的頻度是

nilnn/2nil”“2

T(n)=-EzW”+=2￡

z=lJ=2ii=l2Z=124

設(shè)n為正整數(shù)，分析下面程序段中加下劃線的語句的執(zhí)行次數(shù)是()。

intijfk,x=0,y=0;

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

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

for(k=l;k<=j;k++)

x=x+y;

B屋

〃(〃+l)(〃+2)

6

c.

〃(〃+l)(2〃+l)

6

D.

正確答案是：【C】

解析：

程序段中加下劃線的語句的執(zhí)行次數(shù)是:

nijnin

均+1)l<-2

一二52

Z=1J=1%=11=1J=11=12

1??(??+1)(2/?+1)1〃(〃+l)_〃(〃+l)(〃+2)

-x--------------------H—x-----------=-------------------

26226

io

下面說法錯誤的是()。

(1)算法原地工作的含義是指不需要任何額外的輔助空間

(2)在相同的規(guī)模n下，復(fù)雜度0(n)的算法在時間上總是優(yōu)于復(fù)雜度0(2n)

的算法

(3)所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界

(4)同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低

「A.⑴

「B.(l),⑵

「C.⑴,(4)

「D.⑶

正確答案是：【A】

解析：

算法原地工作的含義指空間復(fù)雜度0(1)

重點回顧

1.結(jié)構(gòu)的分類

注：數(shù)據(jù)結(jié)構(gòu)分為數(shù)據(jù)結(jié)構(gòu)，邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。

2.算法的衡量

注：(1)一般情況下，算法中基本運算次數(shù)T(n)是問題規(guī)模n(輸入量的多

少,

稱之為問題規(guī)模)的某個函數(shù)f(n),記作：T(n)=0(f(n))

注意：有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集

不同而不同。

常見的漸進時間復(fù)雜度有：

O(l)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<0(n!)<

O(nn)o

(2)以下算法的時間復(fù)雜度是(A)。

voidf(intn){

intx=l;

x=2*x;

)

A.O(log2n)B.0(n)C.O(nlog2n)D.0(n2)

分析：基本運算是語句x=2*x,設(shè)其執(zhí)行時間為T(n),則有2T(n)sn,

1

棧和隊列的相同之處是

「A.元素的進出滿足先進后出

「B.元素的進出滿足先進先出

「C.只允許在端點進行插入和刪除操作

「D.無共同點

正確答案是：【C】

解析：

棧和隊列都是特殊的線性表。棧和隊列中的數(shù)據(jù)元素之間的邏輯關(guān)系與線性表中

的數(shù)據(jù)元素之間的邏輯關(guān)系完全相同，但它們的運算時不同的。棧將插入和刪除

操作限制在表的一端進行，而隊列將插入和刪除操作分別限制在表的兩端進行。

它們的共同點是只允許在表的端點處進行插入和刪除操作。

2

某棧的輸入序列為1,2,3,4,下面的四個序列中不可能是它的輸出序列為

A.1,3,2,4

B.2,3,4,1

C.4,3,1,2

D.3,4,2,1

正確答案是：【C】

解析：

若某棧的輸入序列為1，2,3,4,按照出棧操作的原則，不可能得到出棧序列

4,3,1,2。這是由于出棧序列的第一個元素為4,則必須首先一次將1,2,

3,4進棧，然后將此時的棧頂元素4出棧，此時新的棧頂元素為3,繼續(xù)將3

出棧（注意，此時的出棧序列為4,3）,按照題目的要求，出棧序列的下一個

元素應(yīng)該是L而此時新的棧頂元素為2,而不是1,因此，得不到元素1,導(dǎo)

致不能夠得到序列4,3,1,2。

3

設(shè)棧的初始狀態(tài)為空，當字符序列nl_作為棧的輸入時，輸出長度為3的且可

用作C語言標識符的序列的數(shù)目是

「A.3

「B.4

C.5

D.6

正確答案是：【A】

解析：

本題主要考查的內(nèi)容有兩個：（:語言關(guān)于標識符的規(guī)定和棧的先進后出的特性。

標識符的第一個字符必須是大小寫英文字符或者下劃線，而不能是數(shù)字。

按照上述規(guī)定nl_三個字符符合規(guī)定的標識符有nl_,n_L」n,四種形

式。字符按照nl_的順序進棧，根據(jù)棧的先進后出的特性，輸出的順序只能出現(xiàn)

前三種形式：

第一種輸出nl_的實現(xiàn)：n進棧再出棧，1進棧再出棧，一進棧再出棧；

第二種輸出n_1的實現(xiàn)：n進棧再出棧，1進棧一進棧，一出棧1出棧；

第三種輸出_ln的實現(xiàn)：n進棧1進棧一進棧，一出棧1出棧n出棧。

而輸出_nl的情況不可能實現(xiàn)。

4

若某棧的輸入序列是1,2,3,…，n,輸出序列的第1個元素為i,則第j個

輸出元素為

rA.j-i

「B.n-j

「C.j-i+1

「D.不確定

正確答案是：【D】

解析:

當i第一個出棧時，1,2,...?i-1都壓在棧內(nèi)，之后還可能有i之后的元素進棧,

究竟第j個出棧元素是哪一個是不確定的。

5

設(shè)棧的輸入序列為pl,p2,p3,…，pn,輸出序列為1,2,3，…，n,若

存在p3=3,則當pl為

「A.一定是2

「B.可能是2

「C.不可能是1

「D.一定是1

正確答案是：【B】

解析：

當p3=3時，輸入序列為pLp2,3,p4,…，因為輸出的第3個元素是3,

則有多種可能：當pl=l,p2=2時，允許的進棧、出棧的順序是pl進棧pl

出棧p2進棧p2出棧。當pl=2,p2=l時，允許的進棧、出棧的順序是pl進

棧p2進棧p2出棧pl出棧。如果pl、p2、3進棧不出，當p4=2,p5=l時,

允許的進棧、出棧的順序是p4進棧p5進棧p5出棧p4出棧。因此可以斷定

pl=l或pl=2是可能的選擇，但不是一定的選擇。

6

若進棧序列為a,b,c,則通過出棧操作可能得到的a,b,c的不同排列的數(shù)

目為

「A.3

B.4

1C.5

rD.6

正確答案是：【C】

解析：

這里需要注意的是：a,b,c這3個字母不一定要全部進棧以后再出棧，為此就

有了多種排列的可能。本題如果按照正向思維來解的話，我們要考慮各種進棧出

棧的可能性，這樣很同意漏解，而且思維比較亂。我們可以逆向的解此題，3個

字母最多的排列個數(shù)也就是3*2*1=6種可能性，然后這6種可能情況一一考慮

是否符合進棧出棧的場景，這樣比較清晰地得到答案。

(1)出棧序列為a,b,c：a進棧，a出棧，b進棧，b出棧，c進棧，c出棧。

(2)出棧序列為a,c,b：a進棧，a出棧，b進棧，c進棧，c出棧，b出棧。

(3)出棧序列為b,c,a：a進棧，b進棧，b出棧，c進棧，c出棧，a出棧，。

(4)出棧序列為b,a,c：a進棧，b進棧，b出棧，a出棧，c進棧，c出棧。

(5)出棧序列為c,a,b：不可能出現(xiàn)該順序。

(6)出棧序列為c,b,a：a進棧，b進棧，c進棧，c出棧，b出棧，a出棧，。

7

若元素a,b,c,d,e,f依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三

次進行退棧操作，則不可能得到的出棧序列是

'A.d,c,e,b,f,a

'B.c,b,d,a,e,f

,,C.b,c,a,e,f,d

D.a,f,e,d,c,b

正確答案是：【D】

解析：

本題考查棧的基本概念，是一種常見的考查方式。4個選項所給序列的進、出棧

操作序列分別為：

選項A.Push,Push,Push,Push,Pop,Pop,Push,Pop,Pop,Push,Pop,Pop;

選項B.Push,Push,Push,Pop,Pop,Push,Pop,Pop,Push,Pop,Push,Pop;

選項C.Push,Push,Pop,Push,Pop,Pop,Push,Push,Pop,Push,Pop,Pop;

選項D.Push,Pop,Push,Push,Push,Push,Push,Pop,Pop,Pop,Pop,Pop.

按照題目要求，選項D所給序列為不可能得到的出棧順序。

8

若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間top由代表第i個棧

(i=l,2)的棧頂，棧1的底在棧2的底在V[m],則棧滿的條件是

(A.top[2]-top[l]==0

「B.top[l]+1==top[2]

rC.top[l]+top[2]==m

rD.top[l]==top[2]

正確答案是：【B】

解析：

兩個棧共享一個空間的時候，由于棧底是固定的且有兩個，所以棧底一定的是該

空間的兩端，然后數(shù)據(jù)存放在中間。所以棧滿的條件是兩個棧頂相鄰，也就是

top[l]+l==top[2]o

9

最不適合用作鏈棧的鏈表是

「A.只有表頭指針沒有表尾指針的循環(huán)雙鏈表

rB.只有表尾指針沒有表頭指針的循環(huán)雙鏈表

「C.只有表尾指針沒有表頭指針的循環(huán)單鏈表

「D.只有表頭指針沒有表尾指針的循環(huán)單鏈表

正確答案是：【D】

解析：

鏈棧一般不帶頭結(jié)點，進棧和出棧操作均在表頭進行。

對于選項A只有表頭指針沒有表尾指針的循環(huán)雙鏈表，在表頭插入和刪除一個

結(jié)點的時間復(fù)雜度為0(1)和0(1)。

對于選項B只有表尾指針沒有表頭指針的循環(huán)雙鏈表，在表頭插入和刪除一個

結(jié)點的時間復(fù)雜度為0(1)和0(1)o

對于選項C只有表尾指針沒有表頭指針的循環(huán)單鏈表，在表頭插入和刪除一個

結(jié)點的時間復(fù)雜度為0(1)和O(l)o

對于選項D只有表頭指針沒有表尾指針的循環(huán)單鏈表，在表頭插入和刪除一個

結(jié)點的時間復(fù)雜度為0(n)和0(n)(在表頭插入和刪除一個結(jié)點仍需將其變?yōu)橐?/p>

個循環(huán)單鏈表，這時通過查找到尾結(jié)點,再將其next域置為第一個結(jié)點來實現(xiàn))。

注意：若所有鏈表帶頭結(jié)點，則其結(jié)果完全相同。

10

當執(zhí)行函數(shù)時，其局部變量的存儲一般采用下列哪個結(jié)構(gòu)進行存儲

「A.樹

「B.靜態(tài)鏈表

C.棧

D.隊列

正確答案是：【C】

解析：

調(diào)用函數(shù)時，系統(tǒng)將會為調(diào)用者構(gòu)造一個由參數(shù)表和返回地址組成的活動記錄,

并將記錄壓入系統(tǒng)提供的棧中，若被調(diào)用函數(shù)有局部變量，也要壓入棧中。

11

表達式a*(b+c)-d的后綴表達式是

「A.abcd*+-

rB.abc+*d-

rC.abc*+d-

'D.-+*abcd

正確答案是：【B】

解析：

答案顯然是B?？忌枋煜ぶ芯Y表達式轉(zhuǎn)變?yōu)楹缶Y表達式的算法，這是一種?？?/p>

題型，也可以出程序題。其基本思想是：采用運算符棧是為了比較運算符的優(yōu)先

級，所有運算符必須進棧。只將大于棧頂元素優(yōu)先級的運算符直接進棧，否則需

要退棧棧頂運算符(先出棧的運算符先計算，同優(yōu)先級的運算符在棧中的先計

算)。

表達式a*(b+c)-d產(chǎn)生后綴表達式的過程如下表所示：

當前字符運算符棧內(nèi)容后級表達式

aa

*?

(*(

b*(ab

+*(+ab

c*(+abe

)?abc+左括號及其

--abc+*出拔，"-

d-abc+*d

abc+*d-全部出戰(zhàn)

但是對于選擇題，也可以將后綴表達式轉(zhuǎn)變?yōu)橹芯Y表達式，以abc+*d-為例,

將其轉(zhuǎn)換成中綴表達式的過程如下：從左向右掃描，遇到的第一個操作符是+,

前面最靠近的操作數(shù)是be,應(yīng)該是b+c；此刻將b+c作為一個操作數(shù)，繼續(xù)掃

描得到操作符是*,前面最靠近的操作數(shù)是a和(b+c),則得到a*(b+c)；

此時a*(b+c)是一個操作數(shù)，繼續(xù)掃描得到前面操作數(shù)為a*(b+c)和d,

最終得到a*(b+c)-d。

12

解決Hanoi塔問題的遞歸算法，其時間復(fù)雜度是

「A.O(n)

rB°(哈

「C.O(2n)

rD.O(n!)

正確答案是：【C】

解析:

本題主要考查遞歸函數(shù)時間復(fù)雜度的計算。Hanoi算法的時間復(fù)雜度的遞推關(guān)系

式是T(n)=2T(n-l)+l,解此關(guān)系式得到T(n)=2口-1,因此時間復(fù)雜度為0(29

13

若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0

和3,當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別

為

A.1和5

B.2和4

C.4和2

D.5和1

正確答案是：【B】

解析:

本題主要考查循環(huán)隊列的基本操作，刪除一個元素后，front+1；加入兩個元素

后，rear+2

14

循環(huán)隊列用數(shù)組存放其元素值，已知其隊頭指針front指向隊頭元

素，隊尾指針rear指向隊尾元素，則當前隊列的元素的個數(shù)是

!A.(rear-front+m)MODm

1B.rear-front+1

rC.(rear-front+m+1)MODm

D.(rear-front+m-1)MODm

正確答案是：【C】

解析：

注意本題需注意，隊尾指針rear指向隊尾元素，并非指向隊尾元素的下一個位

置。當rear>front時，隊列的元素個數(shù)是rear-front+1；當rear<front時，

隊列的元素個數(shù)是rear-front+m+lo所以綜合上述兩種情況選項C是正確的。

15

最不適合用作鏈隊列的鏈表是

「A.只帶隊首指針的非循環(huán)雙鏈表

rB.只帶隊首指針的循環(huán)雙鏈表

rC.只帶隊尾指針的循環(huán)雙鏈表

「D.只帶隊尾指針的循環(huán)單鏈表

正確答案是：【A】

解析：

鏈隊列的隊頭和隊尾分別在前后端，對于選項A的鏈表，在末尾插入一個結(jié)點

(入隊)的時間復(fù)雜度為0(n),其他選項的鏈表完成同樣的操作的時間復(fù)雜度

均為0(1)。

16

用鏈接方式存儲的隊列，在進行刪除運算時

rA僅修改頭指針

rB.僅修改尾指針

「C.頭、尾指針都要修改

D.頭、尾指針可能都要修改

正確答案是：【D】

解析：

本題主要考查隊列的刪除操作。在有頭結(jié)點的鏈隊列的出隊操作中，一般只需要

修改隊頭指針，但當原隊列中只有一個結(jié)點時，該結(jié)點既是隊頭也是隊尾，故刪

去此結(jié)點時也需要修改尾指針，使其指向頭結(jié)點，且刪去此結(jié)點后隊列變空。

17

已知輸入序列為abed,經(jīng)過輸出受限的雙端隊列后，能得到的輸出序列是

rA.dacb

B.cadb

C.dbca

D.以上答案都不對

正確答案是：【B】

解析：

輸出受限的雙端隊列是指刪除限制在一端進行，而插入允許在兩端進行的隊列。

分析選項A,輸入序列為abed,輸出序列為dacb。先在輸出端輸入a,然后在

非輸出端輸入b,因d未出，此時只能進隊，c怎么進都不可能在a、b之間。

選項A為錯誤答案。另外，已知輸入序列為abed,經(jīng)過輸出受限的雙端隊列后,

以da開頭的輸出序列只有dabco

分析選項B,輸入序列為abed,輸出序列為cadb,其輸入輸出順序為：先在輸

出端輸入a,然后在非輸出端輸入b,這時隊列中的序列為ba,再在輸出端輸

入c,這時隊列中的序列為bac；輸出c,再輸出a；再在輸出端輸入d,這時

隊列中的序列為bd；輸出d,再輸出b。最后得到輸出序列為cadb。

分析選項C,輸入序列為abed,輸出序列為dbea,先在非輸出端輸入a,然后

在輸出端輸入b,因d未出，此時只能進隊，c怎么進都不可能在a、b之間。

選項C為錯誤答案。另外，已知輸入序列為abed,經(jīng)過輸出受限的雙端隊列后,

以db開頭的輸出序列只有dbaco

18

已知二維數(shù)組A[1..4,1..6]采用行序為主序方式存儲，每個元素占用3個存儲

單元,并且Au的存儲地址為1200,元素A24的存儲地址是

rA.1221

「B.1227

「C.1239

「D.1257

正確答案是：【B】

解析:

數(shù)組具有隨機存取特性。對于二維數(shù)組Amn,由地址計算公式LOC(Aij)

LOC(Au)+((i-l)*n+j-l)*d可以得到

19

C語言中定義的整數(shù)一維數(shù)組a[50]和二維數(shù)組b[10][5]具有相同的首元素地

址，即&(a[0])=&(b[0][0]),在以列序為主序時，a口8]的地址和下列哪個數(shù)

組的地址相同

「A.b[l][7]

rB.b[l][8]

Cb[8][l]

D.b[7][l]

正確答案是：【C】

解析：

a[18]為第19個元素,由于19=1*10+9,所以答案為

20

對一些特殊矩陣采用壓縮存儲的目的主要是為了

rA.表達變得簡單

rB.對矩陣元素的存取變得簡單

「C.去掉矩陣中的多余元素

「D.減少不必要的存儲空間開銷

正確答案是：【D】

解析：

對于特殊矩陣采用壓縮存儲方法的目的主要是為了節(jié)省存儲空間，減少不必要的

存儲空間的開銷。

21

將一個nxn的對稱矩陣A的下三角部分按行存放在一個一維數(shù)組B中,A[0][0]

存放在B[0]中，那么第i行的元素在B中的存放位置是

「A.(i+3)i/2

「B.(i+l)i/2

rC.(2n-i+l)i/2

D.(2n-i-l)i/2

正確答案是：【C】

解析:

第i行前面存有i行，元素個數(shù)有n+(n-l)+...+n-i+l=(2n-i+l)i/2,第i行中第

i列前有0個元素，則在B中的存放位置是(2n-i+l)i/2。

22

試證明：若借助棧由輸入序列L2,...,n得到輸出序列為P1,P2，…,Pn(它是輸入序

列的一個排列)，則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i<j<k,使

Pj<Pk<Pio

參考答案是:

如果i<j,則對于Pi<pj情況，說明Pi在Pj入棧前先出棧。而對于p>pj的情況,

則說明要將pj壓到pi之上，也就是在向出棧之后pi才能出棧。這就說明，對

于i<j<k,不可能出現(xiàn)pj<pk<pi的輸出序列。換句話說，對于輸入序列1,2,

3,不可能出現(xiàn)3,1,2的輸出序歹U。

解析:

無

23

設(shè)計一個算法，判斷一個算術(shù)表達式中的括號是否配對。算術(shù)表達式保存在帶頭

結(jié)點的單循環(huán)鏈表中，每個結(jié)點有兩個域：ch和next,其中ch域為字符類型。

設(shè)棧已定義：InitStack(S),Push(S,e),StackEmpty(S),Gettop(S,e),Pop(S,e)

分別為棧初始化，入棧，判斷?？?，獲得棧頂元素，出棧等操作。

參考答案是:

23.【分析】表達式中的括號有以下三對：‘(‘、‘)‘、‘['、']'、'{'、

,算法使用棧，當為左括號時入棧，右括號時，若棧頂是其對應(yīng)的左括號,

則退棧，若不是其對應(yīng)的左括號，則結(jié)論為括號不配對。當表達式結(jié)束，若棧為

空，則結(jié)論表達式括號配對，否則，結(jié)論表達式括號不配對。

【解答】用C語言算法描述如下：

intMatch(LinkListla){

〃算術(shù)表達式存儲在以la為頭結(jié)點的單循環(huán)鏈表中，本算法判斷括號是否正確

配對

p=la->next;//p為工作指針，指向待處理結(jié)點

InitStack(s);〃初始化棧s

while(p!=la){〃循環(huán)到頭結(jié)點為止

switch(p->ch){

case'(':push(s,p->ch);

break;

case*)*:if(StackEmpty(s)||GetTop(s)!='('){

printf("括號不配對\n");

return0;

)

elsepop(s);

break;

case:push(s,p->ch);

break;

caseT:if(StackEmpty(s)||GetTop(s)!=T){

printf("括號不配對\n");

return0;

)

elsepop(s);

break;

case'{':push(s,p->ch);

break;

case}:if(StackEmpty(s)||GetTop(s)!=，{'){

printf("括號不配對\n");

return0;

)

elsepop(s);

break;

)

p=p->next;//后移指針

)

if(StackEmpty(s)){

printf("括號配對\n");

return1;

)

else{

printf（"括號不配對\n"）;

return0;

）

）

算法中對非括號的字符未加討論。遇到右括號時，若棧空或棧頂元素不是其對應(yīng)

的左圓（方、花）括號，則結(jié)論括號不配對，退出運行。最后，若棧不空，仍結(jié)

論括號不配對。

解析：

無

重點回顧

1.棧的存儲實現(xiàn)和運算實現(xiàn)

注：（1）棧的動態(tài)分配順序存儲結(jié)構(gòu)如下:

#defineSTACK_INIT_SIZE100〃存儲空間的初始分配量

#defineSTACKINCREMENT10〃存儲空間的分配增量

typedefstruct{

SEIemType*base;〃在棧構(gòu)造之前和銷毀之后,

base的值

為NULL

SEIemType*top;〃棧頂指針

intstacksize;〃當前已分配的存儲空間

}SqStack;

需要注意，在棧的動態(tài)分配順序存儲結(jié)構(gòu)中，base始終指向棧

底

元素，非空棧中的top始終在棧頂元素的下一個位置。

(2)順序棧上常用的基本操作的實現(xiàn)

i)入棧：若棧不滿，則將e插入棧頂。

intPush(SqStack&S,SEIemTypee){

if(S.top-S.base>=S.stacksize)

{……}〃棧滿，追加存儲空間

*S.top++=e;〃top始終在棧頂元素的下一

個位置

returnOK;

)

ii)出棧：若棧不空，則刪除S的棧頂元素，用e返回其值，并返

回0K,否則返回ERROR。

intPop(SqStack&S,SEIemType&e){

if(S.top==S.base)returnERROR;

e=*--S.top;

returnOK;

)

2.隊列隊列的存儲實現(xiàn)及運算實現(xiàn)

注：(1)順序隊列：循環(huán)隊列的類型定義如下：

#defineMAXQSIZE100〃最大隊列長度

typedefstruct{

QEIemType*base;〃動態(tài)分配存儲空間

intfront;〃頭指針，若隊列不空，指向隊列頭

元素

intrear;〃尾指針，若隊列不空，指向隊列尾元

素的

下一個位置

}SqQueue;

循環(huán)隊列上基本操作的實現(xiàn)如下：

i)入隊：intEnQueue(SqQueue&Q,Q曰emTypee)

ii)出隊：intDeQueue(SqQueue&Q,QEIemType&e)

iii)求循環(huán)隊列元素個數(shù)：intQueueLength(SqQueueQ)

(2)鏈隊列：鏈式存儲的隊列稱為鏈隊列，鏈隊列的形式描述如下：

typedefstructQNode{//結(jié)點類型

QEIemTypedata;

structQNode*next;

}QNode,*QueuePtr;

typedefstruct{〃鏈隊列類型

QueuePtrfront;〃隊頭指針

QueuePtrrear;〃隊尾指針

}LinkQueue;

定義一個指向鏈隊列的指針：LinkQueueQ;

下面是鏈隊列的基本運算的實現(xiàn)：

i)入隊：intEnQueue(LinkQueue&Q,QEIemTypee)

ii)出對：intDeQueue(LinkQueue&Q,QEIemType&e)

3.特殊矩陣的壓縮存儲

注：(1)數(shù)組：設(shè)有mxn二維數(shù)組Amn,下面我們看按元素的下標求其地址

的計算：

以"以行為主序”的分配為例：設(shè)數(shù)組的基址為LOC(all),每

個數(shù)組

元素占據(jù)d個地址單元，那么aij的物理地址可用一線性尋址函

數(shù)計算：

LOC(aij)=LOC(all)+((i-l)*n+j-l)*d

這是因為數(shù)組元素aij的前面有i-1行，每一行的元素個數(shù)為n,

在第i行

中它的前面還有j-1個數(shù)組元素。

(2)特殊矩陣：對稱矩陣，三角矩陣和對角矩陣。

下列敘述中，樹形結(jié)構(gòu)最適合用來描述

?rA.有序的數(shù)據(jù)元素

?「B.無序的數(shù)據(jù)元素

?1C.數(shù)據(jù)元素之間具有層次關(guān)系的數(shù)據(jù)

?'D.數(shù)據(jù)元素之間沒有關(guān)系的數(shù)據(jù)

?您的答案是：【未答】

?正確答案是：【C】

解析：

樹形結(jié)構(gòu)是一種層次結(jié)構(gòu)，最適合用來數(shù)據(jù)元素之間具有層次關(guān)系的數(shù)據(jù)。

對一棵具有n個結(jié)點的樹，其中所有度之和等于

A.n

B.n-1

C.n-2

D.n+1

您的答案是：【未答】

正確答案是：【B】

解析：

在一棵樹中，度之和=分支數(shù)，而分支數(shù)=結(jié)點數(shù)-1。

3

按照二叉樹的定義,具有3個結(jié)點的二叉樹有幾種形態(tài)？不考慮數(shù)據(jù)信息的組合

情況）

A.2

'B.3

rC.4

rD.5

您的答案是：【未答】

正確答案是：【D】

解析：

如果不考慮結(jié)點數(shù)據(jù)信息的組合情況，具有3個結(jié)點的二叉樹有5種形態(tài)。其中，

只有一棵二叉樹具有度為2的結(jié)點（即為一顆都為2的二叉樹），其余4棵二叉

樹的度均為k

4

以下說法中正確的是

「A.完全二叉樹中，葉子結(jié)點的雙親的左兄弟（如果存在）一定不是葉

子結(jié)點

rB.任何一棵二叉樹，葉子結(jié)點數(shù)為度為2的結(jié)點數(shù)減1

「C.二叉樹不適合用順序結(jié)構(gòu)存儲

「D.結(jié)點按層序編號的二叉樹，第i個結(jié)點的左孩子（如果存在）的編

號為2i

您的答案是：【未答】

*正確答案是：【A】

解析：

本題主要考查二叉樹的性質(zhì)以及完全二叉樹的定義。其中選項A正確；選項B

中葉子結(jié)點數(shù)應(yīng)為度為2的結(jié)點數(shù)加1；選項C二叉樹可以用順序結(jié)構(gòu)存儲；選

項D成立的前提是二叉樹是完全二叉樹。_____________________________________

5

設(shè)二叉樹中有n2個度為2的結(jié)點，有nl個度為1的結(jié)點，有nO個度為0的結(jié)

點，則該二叉樹中空指針的數(shù)目為

「A.n2+nl+n0

'B.n2+nl+2n0

C.2n2+nl

D.nl+2n0

您的答案是：【未答】

正確答案是：【D】

解析：

每個度為1的結(jié)點有1個空指針，每個度為0的結(jié)點有2個空指針，度為2的結(jié)

點矍有空指針。所以結(jié)果為nl+2no

6

若一棵度為7的樹有8個度為1的結(jié)點，有7個度為2的結(jié)點，有6個度為3

的結(jié)點，有5個度為4的結(jié)點，有4個度為5的結(jié)點，有3個度為6的結(jié)點，

有2個度為7的結(jié)點，該樹一共擁有的葉子結(jié)點的數(shù)目是

「A.35

B.28

C.77

D.78

您的答案是：【未答】

正確答案是：【D】

解析：

度為7的樹應(yīng)該有l(wèi)+n2+2n3+3n4+4n5+5n6+6n7個葉結(jié)點（與度為1的結(jié)

點的個數(shù)無關(guān)）。因此，如nO表示葉結(jié)點的個數(shù)，則應(yīng)該有n0=l+

7+2X6+3X5+4X4+5X3+6X2=78。（ni表示度為i的結(jié)點數(shù)目）

7

有n(n>0)個結(jié)點的二叉樹的深度的最小值是

「A.[logzL

rB.1l°g2(n+D_

r「「log2(n+l)

「D.「log2n

您的答案是：【未答】

正確答案是：【C】

解析：

【答案解析】設(shè)二叉樹的深度為k,則有29加，即Qlog?(n+1),所匕

【歸納總結(jié)】求有n(n>0)仝結(jié)點的二叉樹的深度的最小值，這棵二叉

與n仝結(jié)點的完全二叉樹的深度相同。

根據(jù)二叉樹的性質(zhì)，具有n合結(jié)點的完全二叉樹的深度k為[logzn」+

8

若某完全二叉樹的深度為h,則該完全二叉樹中至少擁有的結(jié)點數(shù)目是

「A.2h

「B.2h-I

rh

c.2+1

您的答案是：【未答】

正確答案是：【D】

解析：

若某完全二叉樹的深度為h,則前h—l層一定有21-1個結(jié)點，由于第h層至

少有一個結(jié)點，加上前h—1層的結(jié)點總數(shù)，得到(2門—1)+1=2一個結(jié)點，

即深度為h的完全二叉樹中至少有21個結(jié)點。

9

已知完全二叉樹的第7層有10個葉子結(jié)點，則整個二叉樹的結(jié)點數(shù)最多是

?「A.73

?「B.127

?1C.235

?rD.255

?您的答案是：【未答】

?正確答案是：【口

解析：

本題沒說明完全二叉樹的高度，但根據(jù)題意，求二叉樹的結(jié)點數(shù)最多的情況，因

此此二叉樹只能是8層。第7層共有*'=64個結(jié)點，已知有10葉子結(jié)點，其余

54個結(jié)點均為分支結(jié)點。它在第8層上有108個葉子結(jié)點。所以該二叉樹的結(jié)

點數(shù)最多可達(2-1+108)=235。

10

將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度

是

?1A.4

?rB.5

?「C.6

?rD.7

?您的答案是：【未答】

?正確答案是：【C】

解析：

由」上有n個人結(jié)人點上的田…完全人二叉樹的一圖度為L1°J2，之〃」+1=L.los,244」+1=6

11

若用一維數(shù)組保存一個深度為5、結(jié)點個數(shù)10的二叉樹，數(shù)組的長度至少為

?1A.10

?1B.16

C.31

D.63

您的答案是：【未答】

正確答案是：【C】

解析：

本題主要考查二叉樹的性質(zhì)和二叉樹的順序存儲方法。由于二叉樹的順序存儲是

按完全二叉樹來存儲，根據(jù)二叉樹的性質(zhì)：深度為k的二叉樹最多有211個結(jié)

點，深度為5的二叉樹最多有31個結(jié)點，所以存儲這些結(jié)點需要數(shù)組的長度至

少為31,答案應(yīng)為C

12

具有n個結(jié)點的二叉樹采用二叉鏈表存儲結(jié)構(gòu)，鏈表中空的指針域的數(shù)目是

(A.n-1

「B.n

「C.n+l

rD.2n

您的答案是：【未答】

正確答案是：【C】

解析：

具有n個結(jié)點的二叉樹采用二叉鏈表存儲結(jié)構(gòu)，則該鏈表中共有2n個指針域，

其中，有n—10指針域存放指向孩子結(jié)息的地址，剩余的n+l個指針域為空。

13

某二叉樹T有n個結(jié)點，設(shè)按某種順序?qū)中的每個結(jié)點進行編號，編號為1,

2,…，n,具有如下性質(zhì)：要求每個結(jié)點的編號大于其左右孩子的編號，同一

結(jié)點的左右孩子中。其左孩子的編號小于其右孩子的編號，可采用的遍歷形式

是

A.中序遍歷序列

B.先序遍歷序列

C.后序遍歷序列

D.層次遍歷

您的答案是：【未答】

正確答案是：【C】

解析：

對照后序遍歷的先后關(guān)系（左右子樹的大小關(guān)系，雙親和孩子結(jié)點的相對關(guān)系），

可以很容易判斷出邃編號是后序遍歷。

14

若非空二叉樹的先序序列與后序序列的次序正好相反，則該二叉樹一定是

「A.空或僅有一個結(jié)點

「B.其分支結(jié)點無左子樹

rC.其分支結(jié)點無右子樹

rD.其分支結(jié)點的度都為1

您的答案是：【未答】

正確答案是：【I）】

解析：

先序遍歷序列是“根左右”，后序遍歷序列是“左右根”，若要兩個序列相反，

只有當二叉樹中分支結(jié)點的度都為1時，即任一分支結(jié)點只有左孩子或是只有右

孩子，先序遍歷與后序遍歷的次序正好相反。本題的選項A、B、C都符合要求但

都程整。

15

若非空二叉樹的先序序列與中序序列的次序正好相反，則該二叉樹一定是

「A.左子樹為空

B.其中任一結(jié)點無左孩子

C.右子樹為空

D.其中任一結(jié)點無右孩子

您的答案是：【未答】

正確答案是：【D】

解析：

先序遍歷序列是“根左右”，中序遍歷序列是“左根右”，若要兩個序列相反,

說明對于任何分支結(jié)點都沒有右子樹，即其中任一結(jié)點無右孩子。

16

若非空二叉樹的中序序列與后序序列的次序正好相同，則該二叉樹一定是

「A.左子樹為空

B.其中任一結(jié)點無左孩子

C.右子樹為空

D.其中任一結(jié)點無右孩子

您的答案是：【未答】

正確答案是：【D】

解析：

中序遍歷序列是“左根右”，后序遍歷序列是“左右根”，若要兩個序列相同,

說明對于任何分支結(jié)點都沒有右子樹,省其中任一結(jié)點無右孩子。

17

任何一棵非空二叉樹中的葉子結(jié)點在先序遍歷、中序遍歷與后序遍歷中的相對

位置

A.都會發(fā)生改變

B.不會發(fā)生改變

C.有可能會發(fā)生改變

D.部分會發(fā)生改變

您的答案是：【未答】

正確答案是：【B】

解析：

無論是先序遍歷（DLR）還是中序遍歷（LDR）,或是后序遍歷（LRD）,對于葉

子結(jié)點而言，被訪問的先后次序都是先左后右，因此，葉子結(jié)點在先序遍歷、中

序遍歷與后序遍歷中的相對位置都不會發(fā)生改變,

18

已知某完全二叉樹采用順序存儲結(jié)構(gòu)，結(jié)點數(shù)據(jù)信息的存放順序依次為A、B、C、

D、E、F、G、H、I、J,該完全二叉樹的后序遍歷序列為

A.HIDJEBFGCA

B.HIJDEFGBCA

C.IHDJEBGFCA

D.IHDJEFGBCA

您的答案是：【未答】

正確答案是：【A】

解析：

先根據(jù)二叉樹的順序存儲結(jié)構(gòu)將二叉樹恢復(fù)，然后對二叉樹進行后序遍歷即可。

19

二叉樹的先序遍歷序列為ABDCEFG,中序遍歷序列為DBCAFEG,其后序遍歷序列

為

?「A.DCFGEBA

?「B.DCBFGEA

?1C.FGEDCBA

?廣D.DCFGBEA

?您的答案是：【未答】

?正確答案是：【B】

解析：

根據(jù)二叉樹的先序序列和中序序列可以唯一地恢復(fù)二叉樹，原則是：在先序序列

中確定根結(jié)點的信息（任何一個二叉樹/子樹的先序序列中第一個結(jié)點為根結(jié)

點），而中序序列中提供了由根結(jié)點將整個序列分為左、右子樹的信息。因此，

本題先根據(jù)先序序列和中序序列將二叉樹恢復(fù)出來，然后對二叉樹進行后序遍

歷，啊得到后序序列。

20

已知某二叉樹的先序序列為ABDCE,它可能的中序序列為

?「A.BDAEC

?「B.BCADE

?「C.CBADE

?1D.BEACD

您的答案是：【未答】

正確答案是：【A】

解析：

二叉樹的先序序列可以分為連續(xù)的3個部分：第一個是根結(jié)點，后面分別是左子

樹部分和右子樹部分。中序遍歷也可分為3個部分：左子樹部分、根結(jié)點、右子

樹部分。題目給出的先序序列為ABDCE,可知A為根結(jié)點，選項A給出中序序列

表示BD是左子樹部分，EC是右子樹部分，和先序序列不矛盾，是可能的中序序

列。選項B給出的序列表示BC是左子樹，DE是右子樹，這兩個部分在先序序列

ABDCE中不連續(xù)，說明不是可能的中序序列。同理，選項C和選項D也不是可能

的中