1

對數據結構，下列結論不正確的是

A.相同的邏輯結構，對應的存儲結構也必相同

B.數據結構由邏輯結構、存儲結構和基本操作3個方面組成

C.數據存儲結構就是數據邏輯結構的機內的實現

D.對數據基本操作的實現與存儲結構有關

正確答案是：【A】

解析：

選項A錯誤的原因是相同的邏輯結構可以由不同的存儲結構來實現，例如線性

表可以用順序存儲結構和鏈式存儲結構來實現。數據結構的操作在不同存儲結構

下有不同的實現。

2

以下屬于邏輯結構的是

A.順序表

B.散列表

C.有序表

D.單鏈表

正確答案是：【C】

解析：

選項A、B、D都屬于存儲結溝。其中選項C有序表是線性表的特例，要求每個

元素的值按其邏輯順序非降序排列，它是邏輯結構。

3

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

的時空效率。

A.迭代

B.遞歸

C.先遞歸后迭代

D.先迭代后遞歸

正確答案是：【A】

解析：

遞歸函數在執行過程中會多次重復已做過的計算，還會引起一系列的函數調用和

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

算法更高效。

4

一個遞歸算法必須包括

rA.迭代部分

B.遞歸部分

C.終止條件和迭代部分

D.終止條件和遞歸部分

正確答案是：【D】

解析：

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

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

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

5

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

inti=l,k=100;

while(i<n)){

k++；i+=2;

)

1A.O(n)

rB.O(n-)

rC.O(l)

rDO(7W)

正確答案是：【A】

解析：

設while循環語句執行的次數為m,i從1開始每次遞增2,最后取值為l+2m,

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

6

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

inti=0,s=0;

while(s<n){

i++;s+=i;

)

A.O(n)

B.O(n-)

'C.O(1)

rD<X7W)

正確答案是：【D】

解析：

設while循環語句執行的次數為m,i從0開始每次遞增1,直到m-1為止，有:

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

驛法的時間復雜度為0(品)。

7

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

y=o；

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

y++;

)

rA.O(n)

rB.O(n-)

rC.O(l)

「DG,

正確答案是：【D】

解析:

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

次比較。所以算法的時間復雜度為0（五，）。

8

設n為偶數，分析下面程序段中算法的時間復雜度是（）。

inti,j,m=0;

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

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

m++;

1A.0(n)

rB.O(n-)

rC.0(l)

rD<X7W)

正確答案是：【B】

解析：

算法的基本操作是m++,由于內循環從2*i~n,即i的最大值滿足：2En,iwn/2,

所以該語句的頻度是

n<2nm2〃nil”02

T（n）=-￡￡1工（〃-2?+1）=〃*彳-2力+彳=7=。（介

z=i2I24

9

設n為正整數，分析下面程序段中加下劃線的語句的執行次數是（）。

intij,kfx=O,y=O;

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.

〃(五+1)(2〃+1)

6

D.

正確答案是：【C】

解析：

程序段中加下劃線的語句的執行次數是:

nin

Z(Z+1)_1^21^

-------------—―/Z+-/z

7=1A*1Z=1Z=1乙------/i=l乙1=1

1n{n+1)(2〃+1)1n{n+1)/(〃+1)(/2+2)

——x--------------------~\—x--------------------------------

26226

10

下面說法錯誤的是()。

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

(2)在相同的規模n下，復雜度0(n)的算法在時間上總是優于復雜度O(2n)

的算法

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

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

CA.(l)

CB.⑴O)

rC.⑴，⑷

CD.⑶

正確答案是：【A】

解析：

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

重點回顧

1.結構的分類

注：數據結構分為數據結構，邏輯結構和存儲結構。

2.算法的衡量

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

少,

稱之為問題規模)的某個函數f(n),記作：T(n)=O(f(n))

注意：有的情況下，算法中基本操作重復執行的次數還隨問題的輸入數據集

不問而不問。

常見的漸進時間復雜度有：

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

O(nn)o

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

voidf(intn){

intx=l;

x=2*x;

)

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

分析：基本運算是語句x=2僅，設其執行時間為T(n),則有2Tm)wn,

1

棧和隊列的相同之處是

rA.元素的進出滿足先進后出

rB.元素的進出滿足先進先出

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

rD.無共同點

正確答案是：【C】

解析：

棧和隊列都是特殊的線性表。棧和隊列中的數據元素之間的邏輯關系與線性表中

的數據元素之間的邏輯關系完全相同，但它們的運算時不同的。棧將插入和刪除

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

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

2

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

rA.1,3,2,4

「B.2,3,4,1

rC.4,3,1,2

rD.3,4,2,1

正確答案是：【C】

解析：

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

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

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

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

元素應該是L而此時新的棧頂元素為2,而不是L因此，得不到元素L導

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

3

設棧的初始狀態為空，當字符序列nl_作為棧的輸入時，輸出長度為3的且可

用作C語言標識符的序列的數目是

rA.3

rB.4

C.5

D.6

正確答案是：【A】

解析：

本題主要考查的內容有兩個：C語言關于標識符的規定和棧的先進后出的特性。

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

按照上述規定nl_三個字符符合規定的標識符有nl_,n_l,」n,_nl四種形

式。字符按照nl_的順序進棧，根據棧的先進后出的特性，輸出的順序只能出現

前三種形式：

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

第二種輸出n_l的實現：n進棧再出棧，1進棧_進棧，一出棧1出棧;

第三種輸出」n的實現：n進棧1進棧_進棧，一出棧1出棧n出棧。

而輸出_nl的情況不可能實現。

4

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

輸出元素為

rA.j-i

rB.n-j

rC.j-i+1

rD.不確定

正確答案是：【D】

解析:

當i第一個出棧時，L2,…，i?l都壓在棧內，之后還可能有i之后的元素進棧,

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

5

設棧的輸入序列為pl,p2,p3,...?pn,輸出序列為1,2,3,n,若

存在p3=3,則當pl為

rA.一定是2

rB.可能是2

rC.不可能是1

rD.一定是1

正確答案是：【B】

解析：

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

則有多種可能：當pl=Lp2=2時，允許的進棧、出棧的J順序是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的不同排列的數

目為

rA3

B.4

1C.5

「D.6

正確答案是：【C】

解析：

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

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

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

字母最多的排列個數也就是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：不可能出現該順序。

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

7

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

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

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

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

C.bqa,e,f,d

D.afe,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

若棧采用順序存儲方式存儲，現兩棧共享空間top[i]代表第i個棧

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

rA.top[2]-top[l]==0

rB.top[l]+1==top[2]

「C.top[l]+top[2]==m

cD.top[l]==top[2]

正確答案是：【B】

解析：

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

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

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

9

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

rA.只有表頭指針沒有表尾指針的循環雙鏈表

rB.只有表尾指針沒有表頭指針的循環雙鏈表

rC.只有表尾指針沒有表頭指針的循環單鏈表

rD.只有表頭指針沒有表尾指針的循環單鏈表

正確答案是：【D】

解析：

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

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

結點的時間復雜度為0Q)和0(1)。

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

結點的時間復雜度為0Q)和0(1)。

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

結點的時間復雜度為0(1)和0(1)。

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

結點的時間復雜度為0(n)和0(n)(在表頭插入和刪除一個結點仍需將其變為一

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

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

10

當執行函數時，其局部變量的存儲一般采用下列哪個結構進行存儲

rA.樹

「B.靜態鏈表

C.棧

D.隊列

正確答案是：【C】

解析:

調用函數時，系統將會為調用者構造一個由參數表和返回地址組成的活動記錄,

并將記錄壓入系統提供的棧中，若被調用函數有局部變量，也要壓入棧中。

11

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

cA.abcd*+-

rB.abc+*d-

rC.abc*+d-

「D.-+*abcd

正確答案是：【B】

解析：

答案顯然是B。考生需熟悉中綴表達式轉變為后綴表達式的算法，這是一種常考

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

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

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

算)。

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

當前字符運算符棧內容百級表達式

aa

**

(*(

b*(ab

+*(+ab

c*(+abc

)*abc+左括號及其

--abc+*"”出找

d―abc+*d

abc+*d-全部出援

但是對于選擇題，也可以將后綴表達式轉變為中綴表達式，以abc+*d-為例,

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

前面最靠近的操作數是be,應該是b+c；此刻將b+c作為一個操作數，繼續掃

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

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

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

12

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

rA.O(n)

rB°(吟

rcOP)

「D.O(n!)

正確答案是：【C】

解析:

本題主要考查遞歸函數時間復雜度的il算。Hanoi算法的時間復雜度的遞推關系

式是T(n)=2T(n-l)+L解此關系式得到T(n)=2門-L因此時間復雜度為0(2門)

13

若用一個大小為6的數組來實現循環隊列，且當前rear和front的值分別為0

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

為

A.1和5

B.2和4

C.4和2

D.5和1

正確答案是：【B】

解析:

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

后，rear+2

14

循環隊列用數組存放其元素值，己知其隊頭指針front指向隊頭元

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

rA.(rear-front+m)MODm

cB.rear-front+1

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

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

正確答案是：【C】

解析：

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

置。當rear>front時，隊列的元素個數是rear-front+1；當rearvfront時，

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

15

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

rA.只帶隊首指針的非循環雙鏈表

rB.只帶隊首指針的循環雙鏈表

rC.只帶隊尾指針的循環雙鏈表

rD.只帶隊尾指針的循環單鏈表

正確答案是：【A】

解析:

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

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

均為0(1)。

16

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

「A.僅修改頭指針

CB.僅修改尾指針

rC.頭、尾指針都要修改

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

正確答案是：【D】

解析:

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

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

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

17

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

rA.dacb

cB.cadb

rC.dbca

rD.以上答案都不對

正確答案是：【B】

解析：

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

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

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

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

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

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

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

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

隊列中的序列為bd：輸出d,再輸出b。最后得到輸出序列為cad機

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

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

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

以db開頭的輸出序列只有dbac<>

18

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

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

rA.1221

rB.1227

rC.1239

rD.1257

正確答案是：【B】

解析:

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

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

19

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

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

組的地址相同

CA.b[l][7]

CB.b[l][8]

C.b[8][l]

D.b[7][l]

正確答案是：【C】

解析:

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

20

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

rA.表達變得簡單

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

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

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

正確答案是：【D】

解析：

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

存儲空間的開銷。

21

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

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

rA.(i+3)i/2

rB.(i+l)i/2

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

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

正確答案是：【C】

解析:

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

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

22

試證明：若借助棧由輸入序列L2n得到輸出序列為Pi,Pz...,Pn(它是輸入序

列的一個排列)，則在輸出序列中不可能出現這樣的情形：存在著使

Pj<Pk<Pio

參考答案是：

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

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

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

3,不可能出現3,1,2的輸出序列。

解析：

無

23

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

結點的單循環鏈表中，每個結點有兩個域：ch和next,其中ch域為字符類型。

設棧己定義：InitStack(S),Push(S,e),StackEmpty(S),Gettop(S,e),Pop(Sze)

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

參考答案是:

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

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

則退棧，若不是其對應的左括號，則結論為括號不配對。當表達式結束，若棧為

空，則結論表達式括號配對，否則，結論表達式括號不配對。

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

intMatch(LinkListla){

〃算術表達式存儲在以la為頭結點的單循環鏈表中，本算法判斷括號是否正確

配對

p=la->next;〃p為工作指針，指向待處理結點

InitStack(s);//初始化棧s

while(p!=la){〃循環到頭結點為止

switch(p->ch){

case:push(szp->ch);

break;

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

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

return0;

}

elsepop(s);

break;

case:push(szp->ch);

break;

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

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

return0;

}

elsepop(s);

break;

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

break;

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

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

return0;

)

elsepop(s);

break;

)

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

}

if(StackEmpty(s)){

printf("括號配對\n〃)；

return1;

)

else{

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

return0;

}

}

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

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

論括號不配對。

解析：

無

重點回顧

1.棧的存儲實現和運算實現

注：（1）棧的動態分配順序存儲結構如下：

#defineSTACKJNIT.SIZE100〃存儲空間的初始分配量

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

typedefstruct{

SEIemType*base;〃在棧構造之前和銷毀之后，

base的值

為NULL

SEIemType*top;〃棧頂指針

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

}SqStack;

需要注意，在棧的動態分配順序存儲結構中，base始終指向棧

底

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

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

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

intPush(SqStack&S,SEIemTypee){

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

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

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

個位置

returnOK;

)

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

回0K,否則返回ERRORo

intPop(SqStack&S,SEIemType&e){

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

e=*—S.top;

returnOK;

)

2.隊列隊列的存儲實現及運算實現

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

#defineMAXQSIZE100〃最大隊列長度

typedefstruct{

Q日emType*base;〃動態分配存儲空間

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

元素

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

素的

下一個位置

}SqQueue;

循環隊列上基本操作的實現如下：

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

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

iii)求循環隊列元素個數：intQueueLength(SqQueueQ)

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

typedefstructQNode{//結點類型

QEIemTypedata;

structQNode*next;

}QNode,*QueuePtr;

typedefstruct{〃鏈隊列類型

QueuePtrfront;〃隊頭指針

QueuePtrrear;〃隊尾指針

}LinkQueue;

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

下面是鏈隊列的基本運算的實現：

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

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

3.特殊矩陣的壓縮存儲

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

的計算:

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

個數組

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

數計算：

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

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

在第i行

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

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

下列敘述中，樹形結構最適合用來描述

?rA.有序的數據元素

?rB.無序的數據元素

?rC.數據元素之間具有層次關系的數據

?rD.數據元素之間沒有關系的數據

.您的答案是：【未答】

?正確答案是：【C】

解析：

樹形結構是一種層次墓構,最適合咽數據元素之間具有層次關系的數據。

2

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

A.n

B.n-1

C.n-2

D.n+1

您的答案是：【未答】

正確答案是：【B】

解析：

在一棵樹中，度之和二分支數，而分支數二結點數

3

按照二叉樹的定義,具有3個結點的二叉樹有幾種形態？不考慮數據信息的組合

情況）

A.2

B.3

C.4

D.5

您的答案是：【未答】

正確答案是：【D】

解析：

如果不考慮結點數據信息的組合情況,具有3個結點的二叉樹有5種形態。其中,

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

樹的鳥空1。

4

以下說法中正確的是

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

子結點

rB.任何一棵二叉樹，葉子結點數為度為2的結點數減1

rC.二叉樹不適合用順序結構存儲

rD.結點按層序編號的二叉樹，第i個結點的左孩子（如果存在）的編

號為2i

您的答案是：【未答】

正確答案是：【心

解析；

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

中葉子結點數應為度為2的結點數加1；選項C二叉樹可以用順序結構存儲；選

項D成立的年是二g樹是完全二叉樹。

5

設二叉樹中有n2個度為2的結點，有nl個度為1的結點，有nO個度為。的結

點，則該二叉樹中空指針的數目為

A.n2+nl+n0

B.n2+nl+2no

C.2n2+nl

D.nl+2n0

您的答案是：【未答】

正確答案是：[D]

解析：

每個度為1的結點有1個空指針，每個度為0的結點有2個空指針，度為2的結

整聲主阿色：所豈譬gn哈0

6

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

的結點，有5個度為4的結點，有4個度為5的結點，有3個度為6的結點，

有2個度為7的結點，該樹一共擁有的葉子結點的數目是

rA.35

B.28

C.77

D.78

您的答案是：【未答】

正確答案是：[D]

解析：

度為7的樹應該有l+n2+2n3+3n4+4n5+5n6+6n7個葉結點（與度為1的結

點的個數無關）。因此，如nO表示葉結點的個數，則應該有n0=l+

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

7

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

「A.Log?11」

rB.Ll°g2(n+D」

rcJbgJn+l)]

「D.「log2n

您的答案是：【未答】

正確答案是：【C】

解析：

【答案解析】設二叉樹的深度為k,則有2k-iNn,即kNlog.n+l),所￡

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

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

根據二叉樹的性質，具有n個結點的完全二叉樹的深度k為口og2n」+

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

「A.2h

rB.2h-i

rh

c.2+1

「D2^1

您的答案是：【未答】

正確答案是：【D】

解析：

若某完全二叉樹的深度為h,則前h—l層一定有2^—1個結點，由于第h層至

少有一個結點，加上前h—l層的結點總數，得到(2^—1)+1=于_個結點，

即深度為h的完全二叉樹中至少有個結點。

9

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

?'A.73

?rB.127

?rC.235

?rD.255

?您的答案是：【未答】

?正確答案是：【C】

解析：

本題沒說明完全二叉樹的高度，但根據題意，求二叉樹的結點數最多的情況，因

此此二叉樹只能是8層。第7層共有2^=64個結點，己知有10葉子結點，其余

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

點數最我達（27-1+108）=235。

10

將有關二叉樹的概念推廣到三叉樹，則一棵有244個結點的完全三叉樹的高度

是

?rA.4

?rB.5

?rC.6

?rD.7

?您的答案是：【未答】

?正確答案是：【C】

解析：

由有n個結點的完全三叉樹的高度為3〃_|+l=|_10g3244」+1=6

11

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

rA.10

rB.16

C.31

D.63

您的答案是：【未答】

正確答案是：[C]

解析：

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

按完全二叉樹來存儲，根據二叉樹的性質：深度為k的二叉樹最多有2卜-1個結

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

少為31,答案應為C

12

具有n個結點的二叉樹采用三叉鏈表存儲結構，鏈表中空的指針域的數目是

rA.n-1

B.n

C.n+1

D.2n

您的答案是：【未答】

正確答案是：【口

解析：

具有n個結點的二叉樹采用二叉鏈表存儲結構，則該鏈表中共有2n個指針域，

其中，有n—1個指針域存放指好舌封的地址,剩余的n+1個指針域為空。

13

某二叉樹T有n個結點，設按某種順序對T中的每個結點進行編號，編號為1,

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

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

是

「A.中序遍歷序列

CB.先序遍歷序列

rC.后序遍歷序列

rD.層次遍歷

您的答案是：【未答】

正確答案是：【C】

解析：

對照后序遍歷的先后關系（左右子樹的大小關系，雙親和孩子結點的相對關系）,

可2逑容易判四照編誓后g遍叫

14

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

「A.空或僅有一個結點

B.其分支結點無左子樹

C.其分支結點無右子樹

D.其分支結點的度都為1

您的答案是：【未答】

正確答案是：［D1

解析：

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

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

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

都不完整。

15

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

「A.左子樹為空

B.其中任一結點無左孩子

C.右子樹為空

D.其中任一結點無右孩子

您的答案是：【未答】

正確答案是：［D1

解析：

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

說明對于任何空:結點都沒有右子樹,即其中任一宜點無守w。

16

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

「A.左子樹為空

B.其中任一結點無左孩子

C.右子樹為空

D.其中任一結點無右孩子

?您的答案是：【未答】

?正確答案是：【D】

解析：

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

說明也壬何■々支邕點都啰右逑,即其中華二結點無右孩子。

17

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

位置

?CA.都會發生改變

?CB.不會發生改變

?rC.有可能會發生改變

?rD.部分會發生改變

.您的答案是：【未答】

?正確答案是：【B】

解析：

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

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

.遍睡后里遍吧的吧四置都受冬發生改變。

18

已知某完全二叉樹采用順序存儲結構，結點數據信息的存放順序依次為A、B、C、

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

?rA.HIDJEBFGCA

?rB.HTJDEFGBCA

?rC.IHDJEBGFCA

?rD.IHDJEFGBCA

?您的答案是：【未答】

?正確答案是：【A】

解析：

先根據二叉樹的順序存儲結構將二叉樹恢復，然后對二叉樹進行后序遍歷即可。

19

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

為

?rA.DCFGEBA

?rB.DCBFGEA

?rC.FGEDCBA

?rD.DCFGBEA

?您的答案是：【未答】

?正確答案是：【B】

解析：

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

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

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

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

歷二即曾到后序尼■列。

20

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

?rA.BDAEC

?rB.BCADE

?rC.CBADE

?rD.BEACD

?您的答案是：【未答】

?正確答案是：【A】

解析：

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

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

樹部分。題目給出的先序序列為ABDCE,可知A為根結點，選