數(shù)據(jù)結(jié)構(gòu)考研試題棧和隊(duì)列

第3章棧和隊(duì)列

-選擇題

1.對于棧操作數(shù)據(jù)的原則是（）。【青島大學(xué)2001五、2（2分）】

A.先進(jìn)先出B.后進(jìn)先出C.后進(jìn)后出D,不分順序

2.在作進(jìn)棧運(yùn)算時，應(yīng)先判別棧是否（①），在作退棧運(yùn)算時應(yīng)先判別棧

是否（②）。當(dāng)棧中元素為n個，作進(jìn)棧運(yùn)算時發(fā)生上溢，則說明該棧的最

大容量為（③）。

為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片

連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的（④）分別設(shè)在這片內(nèi)存空間的兩端，這

樣，當(dāng)（⑤）時，才產(chǎn)生上溢。

①，②：A.空B.滿C.上溢D.下溢

③：A.n-1B.nC.n+1D.n/2

④：A.長度B.深度C.棧頂D.棧底

⑤：A.兩個棧的棧頂同時到達(dá)?？臻g的中心點(diǎn).

B.其中一個棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn).

C.兩個棧的棧頂在棧空間的某一位置相遇.

D.兩個棧均不空，且一個棧的棧頂?shù)竭_(dá)另一個棧的棧底.

【上海海運(yùn)學(xué)院1997二、1（5分）】【上海海運(yùn)學(xué)院1999二、1（5

分）】

3.一個棧的輸入序列為123,,n,若輸出序列的第一個元素是n,輸出第i

（K=i<=n）個元素是（）。

A.不確定B.n-i+1C.iD.n-i

【中山大學(xué)1999一、9（1分）】

4.若一個棧的輸入序列為1,2,3,?,n,輸出序列的第一個元素是i,則第

j個輸出元素是（）o

A.i-j-1B.i-jC.j-i+1D.不確定的

【武漢大學(xué)2000二、3]

5.若已知一個棧的入棧序列是其輸出序列為巴,2“3,,,，

P、,若p、是n,則%是（）o

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

【南京理工大學(xué)2001一、1（1.5分）】

6.有六個元素6,5,4,3,2,1的順序進(jìn)棧，問下列哪一個不是合法的

出棧序列？（）

A.543612B.453126C.346521D.23

4156

【北方交通大學(xué)2001一、3（2分）】

7.設(shè)棧的輸入序列是1,2,3,4,則（）不可能是其出棧序列?！局锌?/p>

院計(jì)算所2000—、10（2分）】

A.1,2,4,3,B.2,1,3,4,C.1,4,3,2,

D.4,3,1,2,E.3,2,1,4,

8.一個棧的輸入序列為12345,則下列序列中不可能是棧的輸出序列

的是（）o

A.23415B.54132C.23145D.1543

2

【南開大學(xué)2000一、1】【山東大學(xué)2001二、4（1分）】【北京理工

大學(xué)2000一、2（2分）】

9.設(shè)一個棧的輸入序列是1,2,3,4,5,則下列序列中，是棧的合法輸

出序列的是（）。

A.51234B.45132C.43125D.3

2154

【合肥工業(yè)大學(xué)2001一、1（2分）】

10.某堆棧的輸入序列為a,b,c,d,下面的四個序列中，不可能是它的

輸出序列的是（）o

A.a,c,b,dB.b,c,d,aC.c,d,b,aD.

d,c,a,b

【北京航空航天大學(xué)2000一、3（2分）】【北京郵電大學(xué)1999一、

3（2分）】

11.設(shè)abcdef以所給的次序進(jìn)棧，若在進(jìn)棧操作時，允許退棧操作，則下

面得不到的序列為（）。

A.fedcbaB.bcafedC.dcefbaD.cabdef

【南京理工大學(xué)1996一、9（2分）】

12.設(shè)有三個元素X,Y,Z順序進(jìn)棧（進(jìn)的過程中允許出棧），下列得不到

的出棧排列是（）。

A.XYZB.YZXC.ZXYD.ZYX

【南京理工大學(xué)1997一、5（2分）】

13.輸入序列為ABC,可以變?yōu)镃BA時，經(jīng)過的棧操作為（）【中山大

學(xué)1999一、8（1分）】

A.push,pop,push,pop,push,popB.

push,push,push,pop,pop,pop

C.push,push,pop,pop,push,popD.

push,pop,push,push,pop,pop

14.若一個棧以向量V[l..n]存儲，初始棧頂指針top為n+1,則下面x

進(jìn)棧的正確操作是（）o

A.top:=top+l;V[top]:=xB.V[top]:=x;

top:=top+l

C.top:=top-l;V[top]:=xD.V[top]:=x;

top:=top-l

【南京理工大學(xué)1998一、13（2分）】

15.若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間top[i]代表

第i個棧（i=1,2）棧頂，棧1的底在v[l],棧2的底在V[m],則棧滿的

條件是（）。

A.|top[2]-top[1]|=0B.top[l]+l=topL2]C.

top[l]+top[2]=mD.top[l]=top[2]

【南京理工大學(xué)1999一、14（1分）】

16.棧在（）中應(yīng)用。【中山大學(xué)1998二、3（2分）】

A.遞歸調(diào)用B.子程序調(diào)用C.表達(dá)式求值D.A,B,

C

17.一個遞歸算法必須包括（）?！疚錆h大學(xué)2000二、2]

A.遞歸部分B.終止條件和遞歸部分C.迭代部分

D.終止條件和迭代部分

18.執(zhí)行完下列語句段后，i值為：（）【浙江大學(xué)2000一、6（3

分）】

intf（intx）

{return（（x>0）?x*f（x-l）:2）;}

inti;

i=f（f（D）；

A.2B.4C.8D.無限遞歸

19.表達(dá)式a*（b+c）-d的后綴表達(dá)式是（）?！灸暇├砉ご髮W(xué)2001一、

2（1.5分）】

A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd

20.表達(dá)式3*2'（4+2*2-6*3）-5求值過程中當(dāng)掃描到6時，對象棧和算符

棧為（），其中,為乘幕。

A.3,2,4,1,1；（*”（+*-B.3,2,8；（*'-C.3,2,4,2,2；（*“（-

D.3,2,8；（**（-

【青島大學(xué)2000五、5（2分）】

21.設(shè)計(jì)一個判別表達(dá)式中左，右括號是否配對出現(xiàn)的算法，采用（）

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

A.線性表的順序存儲結(jié)構(gòu)B.隊(duì)列C.線性表的鏈?zhǔn)酱鎯?/p>

結(jié)構(gòu)D.棧

【西安電子科技大學(xué)1996一、6（2分）】

22.用鏈接方式存儲的隊(duì)列，在進(jìn)行刪除運(yùn)算時（）?！颈狈浇煌ù髮W(xué)

2001一、12（2分）】

A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改

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

23.用不帶頭結(jié)點(diǎn)的單鏈表存儲隊(duì)列時，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾

指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時（）?！颈本├砉ご髮W(xué)2001六、

3（2分）】

A.僅修改隊(duì)頭指針B.僅修改隊(duì)尾指針

C.隊(duì)頭、隊(duì)尾指針都要修改D.隊(duì)頭，隊(duì)尾指針都可能要修改

24.遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（）的

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

A.隊(duì)列R多維數(shù)組C棧D.

線性表

【福州大學(xué)1998一、1（2分）】

25.假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素，其頭尾指針分別為front和

rear,則當(dāng)前隊(duì)列中的元素個數(shù)為（）?！颈本┕ど檀髮W(xué)2001一、2

（3分）】

A.（rear-front+m）%mB.rear-front+1

C.（front-rear+m）%mD.（rear-front）%m

26.循環(huán)隊(duì)列A[0..mT]存放其元素值，用front和rear分別表示隊(duì)頭和

隊(duì)尾，則當(dāng)前隊(duì)列中的元素數(shù)是（）o【南京理工大學(xué)2001一、5（1.5

分）】

A.（rear-front+m）%mB.rear-front+1C.rear-front-1

D.rear-front

27.循環(huán)隊(duì)列存儲在數(shù)組中，則入隊(duì)時的操作為（）。【中山

大學(xué)1999一、6（1分）】

A.rear=rear+lB.rear=(rear+1)mod(m-1)

C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)

28.若用一個大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值

分別為0和3,當(dāng)從隊(duì)列中刪除一個元素，再加入兩個元素后，rear和front

的值分別為多少？（）【浙江大學(xué)1999四、1（4分）】

A.1和5B.2和4C.4和2D.5和1

29.已知輸入序列為abed經(jīng)過輸出受限的雙向隊(duì)列后能得到的輸出序列

有（）。

A.dacbB.cadbC.dbeaD.bdacE.以上答

案都不對

【西安交通大學(xué)1996三、3（3分）】

30.若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列

得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是（）。【西安電子

科技大學(xué)1996一、5（2分）】

A.1234B.4132C.4231D.4213

31.最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear,隊(duì)頭是front,則隊(duì)空

的條件是()。

A.(rear+1)MODn=frontB.rear=front

C.rear+l=frontD.(rear-1)MOD

n=front

【南京理工大學(xué)1999一、16（2分）】

32.棧和隊(duì)列的共同點(diǎn)是（）?！狙嗌酱髮W(xué)2001—、1（2分）】

A.都是先進(jìn)先出B.都是先進(jìn)后出

C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)

33.棧的特點(diǎn)是（①），隊(duì)列的特點(diǎn)是（②），棧和隊(duì)列都是

（③）0若進(jìn)棧序列為1,2,3,4則（④）不可能是一個出棧序列

（不一定全部進(jìn)棧后再出棧）；若進(jìn)隊(duì)列的序列為1,2,3,4則（⑤）

是一個出隊(duì)列序列?！颈狈浇煌ù髮W(xué)1999一、1（5分）】

①，②：A.先進(jìn)先出B.后進(jìn)先出C.進(jìn)優(yōu)于出

D.出優(yōu)于進(jìn)

③：A.順序存儲的線性結(jié)構(gòu)B.鏈?zhǔn)酱鎯Φ木€性結(jié)構(gòu)

C.限制存取點(diǎn)的線性結(jié)構(gòu)D.限制存取點(diǎn)的非線性結(jié)構(gòu)

④，⑤：A.3,2,1,4B.3,2,4,1C.4,2,3,1D.4,3,2,1

F.1,2,3,4G.1,3,2,4

34.棧和隊(duì)都是（）【南京理工大學(xué)1997一、3（2分）】

A.順序存儲的線性結(jié)構(gòu)B.鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu)

C.限制存取點(diǎn)的線性結(jié)構(gòu)D.限制存取點(diǎn)的非線性結(jié)構(gòu)

35.設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素el,e2,e3,e4,e5和e6依次

通過棧S,一個元素出棧后即進(jìn)隊(duì)列Q,若6個元素出隊(duì)的序列是e2,e4,

e3,e6,e5,el則棧S的容量至少應(yīng)該是（）。

A.6B.4C.3D.2

【南京理工大學(xué)2000一、6（1.5分）】

36.用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的（）位置。【清華大學(xué)

1998一、1（2分）】

A.鏈頭B.鏈尾C.鏈中

37.依次讀入數(shù)據(jù)元素序列｛a,b,c,d,e,f,g｝進(jìn)棧，每進(jìn)一個元素，

機(jī)器可要求下一個元素進(jìn)棧或彈棧，如此進(jìn)行，則?？諘r彈出的元素構(gòu)成

的序列是以下哪些序列？【哈爾濱工業(yè)大學(xué)2000七（8分）】

A.{d，e,c,f,b,g,a}B.{f,e,g,d,a,c,b)

C.{e,f,d,g,b,c,a}D.{c,d,b,e,f,a,g}

二判斷題

1.消除遞歸不一定需要使用棧，此說法（）

【中科院計(jì)算所1998二、2（2分）】【中國科技大學(xué)1998二、2（2

分）】

2.棧是實(shí)現(xiàn)過程和函數(shù)等子程序所必需的結(jié)構(gòu)。（）【合肥工業(yè)大學(xué)

2000二、2（1分）】

3.兩個棧共用靜態(tài)存儲空間，對頭使用也存在空間溢出問題。（）【青

島大學(xué)2000四、2（1分）】

4.兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機(jī)會，

應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。（）【上海海運(yùn)學(xué)院

1998一、4（1分）】

5.即使對不含相同元素的同一輸入序列進(jìn)行兩組不同的合法的入棧和出

棧組合操作，所得的輸出序列也一定相同。（）【北京郵電大學(xué)1999二、

4（2分）】

6.有n個數(shù)順序（依次）進(jìn)棧，出棧序列有Cn種，Cn=[l/（n+1）]*

（2n）!/[（n!）*（n!）]o（）

【北京郵電大學(xué)1998一、3（2分）】

7.棧與隊(duì)列是一種特殊操作的線性表。（）【青島大學(xué)2001四、3（1

分）】

8.若輸入序列為1,2,3,4,5,6,則通過一個?？梢暂敵鲂蛄?,2,5,6,4,1.

（）

【上海海運(yùn)學(xué)院1995一、2（1分）1997一、3（1分）】

9.棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。（）【中科院軟件所1999六、

⑸（2分）】

10.若輸入序列為1,2,3,4,5,6,則通過一個?？梢暂敵鲂蛄?,5,

4,6,2,3o（）

【上海海運(yùn)學(xué)院1999一、3（1分）】

11.任何一個遞歸過程都可以轉(zhuǎn)換成非遞歸過程。（）【上海交通大學(xué)

1998->3（1分）】

12.只有那種使用了局部變量的遞歸過程在轉(zhuǎn)換成非遞歸過程時才必須使

用棧。（）

【上海交通大學(xué)1998一、4（1分）】

13.隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先

進(jìn)后出型結(jié)構(gòu)。（）

【上海海運(yùn)學(xué)院1998一、3（1分）】

14.通常使用隊(duì)列來處理函數(shù)或過程的調(diào)用。（）【南京航空航天大學(xué)

1997一、5（1分）】

15.隊(duì)列邏輯上是一個下端和上端既能增加又能減少的線性表。（）【上

海交通大學(xué)1998一、2]

16.循環(huán)隊(duì)列通常用指針來實(shí)現(xiàn)隊(duì)列的頭尾相接。（）【南京航空航天

大學(xué)1996六、1（1分）】

17.循環(huán)隊(duì)列也存在空間溢出問題。（）【青島大學(xué)2002一、2（1

分）】

18.隊(duì)列和棧都是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)行運(yùn)算。（）

【長沙鐵道學(xué)院1997一、5（1分）】

19.棧和隊(duì)列都是線性表，只是在插入和刪除時受到了一些限制。（）

【北京郵電大學(xué)2002一、3（1分）】

20.棧和隊(duì)列的存儲方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞?。（?/p>

【上海海運(yùn)學(xué)院1996一、2（1分）1999一、2（1分）】

三填空題

1棧是的線性表，其運(yùn)算遵循的原則。【北京科技大學(xué)1997

一、3]

2是限定僅在表尾進(jìn)行插入或刪除操作的線性表【。燕山大學(xué)1998

一、3（1分）】

A個棧的輸入序列是：1,2,3則不可能的棧輸出序列是o【中

國人民大學(xué)2001—、1（2分）】

段有一個空棧，棧頂指針為1000H（十六進(jìn)制），現(xiàn)有輸入序列為1,2,3,

4,5,經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是

，而棧頂指針值是Ho設(shè)棧為順序棧，每個元素占4個字節(jié)。

【西安電子科技大學(xué)1998二、1（4分）】

為兩個棧共享一存儲區(qū)時，棧利用一維數(shù)組stack。,n）表示，兩棧頂指針

為top[l]與top[2],則當(dāng)棧1空時，top[l]為,棧2空時,

top[2]為,棧滿時為o

【南京理工大學(xué)1997三、1（3分）】

6兩個棧共享空間時棧滿的條件?！局猩酱髮W(xué)1998一、3（1分）】

7在作進(jìn)棧運(yùn)算時應(yīng)先判別棧是否（1）;在作退棧運(yùn)算時應(yīng)先判別棧是否

（2）；當(dāng)棧中元素為n個，作進(jìn)棧運(yùn)算時發(fā)生上溢，則說明該棧的最大容

為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片

連續(xù)的空間時，應(yīng)將兩棧的（4）分別設(shè)在內(nèi)存空間的兩端，這樣只有當(dāng)

（5）時才產(chǎn)生溢出?！旧綎|工業(yè)大學(xué)1994一、1（5分）】

8多個棧共存時，最好用作為存儲結(jié)構(gòu)?！灸暇├砉ご髮W(xué)2001二、

7（2分）】

fflS表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234,為了得

到1342出棧順序，相應(yīng)的S和X的操作串為?！疚髂辖煌ù髮W(xué)

2000一、5]

順序棧用data[L.n]存儲數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操

作是o

【合肥工業(yè)大學(xué)2001三、2（2分）】

11.表達(dá)式23+（（12*3-2）/4+34*5/7）+108/9的后綴表達(dá)式是?！局?/p>

山大學(xué)1998一、4（1分）】

12.循環(huán)隊(duì)列的引入，目的是為了克服0【廈門大學(xué)2001一、1

（14/8分）]

13.用下標(biāo)0開始的N元數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列時，為實(shí)現(xiàn)下標(biāo)變量M加1后

在數(shù)組有效下標(biāo)范圍內(nèi)循環(huán)，可采用的表達(dá)式是：M：=（填PASCAL

語言，C語言的考生不填）；M=（填C語言，PASCAL語言的考生

不填）?！疚髂辖煌ù髮W(xué)2000一、7]

14.又稱作先進(jìn)先出表?！局貞c大學(xué)2000一、7]

15.隊(duì)列的特點(diǎn)是?！颈本├砉ご髮W(xué)2000二、2（2分）】

16.隊(duì)列是限制插入只能在表的一端，而刪除在表的另一端進(jìn)行的線性表，

其特點(diǎn)是o

【北方交通大學(xué)2001二、5]

17.已知鏈隊(duì)列的頭尾指針分別是f和r,則將值x入隊(duì)的操作序列是

【合肥工業(yè)大學(xué)2000三、3（2分）】

18.區(qū)分循環(huán)隊(duì)列的滿與空，只有兩種方法，它們是和0【北

京郵電大學(xué)2001二、2（4分）】

19.設(shè)循環(huán)隊(duì)列用數(shù)組A[L.M]表示，隊(duì)首、隊(duì)尾指針分別是FRONT和TAIL,

判定隊(duì)滿的條件為。

【山東工業(yè)大學(xué)1995一、1（1分）】

20.設(shè)循環(huán)隊(duì)列存放在向量sq.data[0:M]中，則隊(duì)頭指針sq.front在循

環(huán)意義下的出隊(duì)操作可表示為，若用犧牲一個單元的辦法來區(qū)分隊(duì)

滿和隊(duì)空（設(shè)隊(duì)尾指針sq.rear），則隊(duì)滿的條件為。

【長沙鐵道學(xué)院1997二、4（4分）】

21.表達(dá)式求值是應(yīng)用的一個典型例子?！局貞c大學(xué)2000一、10]

22.循環(huán)隊(duì)列用數(shù)組A[0..mT]存放其元素值，已知其頭尾指針分別是

front和rear，則當(dāng)前隊(duì)列的元素個數(shù)是?！緩B門大學(xué)2000六、

1(16%/3分)]

23.設(shè)Q[0..21]為循環(huán)隊(duì)列，其頭、尾指針分別為P和R,則隊(duì)Q中當(dāng)

前所含元素個數(shù)為o

【北京科技大學(xué)1997一、4]

24.完善下面算法?！局猩酱髮W(xué)1998四、2(6分)】

后綴表達(dá)式求值，表達(dá)式13/25+61的后綴表達(dá)式格式為：13,25/61,

+

FUNCcompute(a):real;后綴表達(dá)式存儲在數(shù)組a[l..m]中。

BEGIN

setnull(s)；i:=l；ch:=Xl)；

WHILEch。'DO

BEGIN

CASEchOF

'O'..'9':x:=0;

WHILEch<>','DO

BEGIN

x:=x*10+ord(ch)-ord(*0*);

i:=i+l；ch:=(2);

END

'+':x:=pop(s)+pop(s);

'：X:=pop(s)；X:=pop(s)-X;

'*':x:=pop(s)*pop(s);

'/':x:=pop(s);x:=pop(s)/x;

ENDCASE

push(s,x)；i:=i+l；ch:=a[i]；

END;

comput:=(3)；

END;

25.算術(shù)表達(dá)式求值的流程，其中OPTR為算術(shù)符棧，OPND為操作數(shù)棧，

precede(operl,oper2)是比較運(yùn)算符優(yōu)先級別的函數(shù)，

operate(opndl,oper,opnd2)為兩操作數(shù)的運(yùn)算結(jié)果函數(shù)。(#表示運(yùn)算起始

和終止符號)【西北工業(yè)大學(xué)1999六、2(7分)】

FUNCTIONexp_reduced:operandtype;

INITSTACK(OPTR);PUSH(OPTR"#")；INITSTACK(OPND);read(w)；

WHILEN0T((w='#')AND(GETTOP(OPTR)='#'))DO

IFNOTwinopTHENPUSH(OPND,w);

ELSECASEprecede(GETTOP(OPTR),w)OF

〈’：L0Q________;read(w);]

=':_______；read(w);];

'>':[theta:=POP(OPTR);b:=POP(OPND);a:=POP(OPND);(3)；]

ENDC;

RETURN(GETTOP(OPND));

ENDF;

26.根據(jù)需要，用適當(dāng)?shù)恼Z句填入下面算法的中：

問題：設(shè)有n件物品，重量分別為w,w,w,,,,w和一個能裝載總重量

123n

為T的背包。能否從n件物品中選擇若干件恰好使它們的重量之和等于T。

若能，則背包問題有解，否則無解。解此問題的算法如下：

FUNCTIONkanp_stack(VARstack,w:ARRAY[1..n]OFreal;VAR

top:integer;T:real):boolean;

｛w[l：n]存放n件物品的重量，依次從中取出物品放入背包中，檢

查背包重量，若不超過T,則裝入，否則棄之，取下一個物品試之。若有

解則返回函數(shù)值true,否則返回false｝

BEGIN

top:=0;i:=l;｛i指示待選物品｝

WHILEUI_______ANEU2LDO

[IF?OR?AND(i<n)

THEN[top:=國_____;stack[top]:=i;｛第i件物品

裝入背包｝

T:=T-w[i]]；

IFT=0THENRETURNOfil_______)｛背包問題有解｝

ELSE[IF(i=n)AND(top>0)

THEN[i:=171;｛取出棧頂物品｝

top:=X8)；T:=(9)];

｛恢復(fù)T值｝

i：=i+l｛準(zhǔn)備挑選下一件物品｝

]；

]；

RETURN((10))｛背包無解｝

END;

【北京郵電大學(xué)1996四(10分)】

四應(yīng)用題

1.名詞解釋：棧?！狙嗌酱髮W(xué)1999一、1(2分)】【吉林工業(yè)大學(xué)1999

3（2分）】

2.名詞解釋：隊(duì)列【大連海事大學(xué)1996一、6（1分）】

3.什么是循環(huán)隊(duì)列？【哈爾濱工業(yè)大學(xué)2001三、2（3分）】【河南大學(xué)

1998一、4（3分）】

4.假設(shè)以S和X分別表示入棧和出棧操作，則對初態(tài)和終態(tài)均為空的棧操

作可由S和X組成的序列表示（如SXSX）。

（1）試指出判別給定序列是否合法的一般規(guī)則。

（2）兩個不同合法序列（對同一輸入序列）能否得到相同的輸出元素

序列？如能得到，請舉列說明。

【東南大學(xué)1992二（10分）】

5.有5個元素，其入棧次序?yàn)椋篈,B,C,D,E,在各種可能的出棧次序

中，以元素C,D最先出棧（即C第一個且D第二個出棧）的次序有哪幾個？

【西南交通大學(xué)2000二、1]

6.如果輸入序列為123456,試問能否通過棧結(jié)構(gòu)得到以下兩個序列:4

35612和135426;請說明為什么不能或如何才能得到。【武漢交通科

技大學(xué)1996二、3（3分）】

7.若元素的進(jìn)棧序列為：A、B、C、D、E,運(yùn)用棧操作，能否得到出棧序

列B、C、A、E、D和D、B、A、C、E?為什么？【北京科技大學(xué)1998—、

2]

8.設(shè)輸入序列為a,b,c,d,試寫出借助一個?？傻玫降膬蓚€輸出序列和兩

個不能得到的輸出序列。

【北京科技大學(xué)2001一、4（2分）】

9.設(shè)輸入序列為2,3,4,5,6,利用一個棧能得到序列2,5,3,4,6

嗎？棧可以用單鏈表實(shí)現(xiàn)嗎？

【山東師范大學(xué)1996五、4（2分）】

10.試證明：若借助棧由輸入序列l(wèi),2,,,,n得到輸出序列為P,P,,,,P

12n

（它是輸入序列的一個排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存

在著使P,〈Pk〈P,?！旧虾＝煌ù髮W(xué)1998二（15分）】

11.設(shè)一數(shù)列的詢I人廟序?yàn)?23456,若采用堆棧結(jié)構(gòu)，并以A和D分別表

示入棧和出棧操作，試問通過入出棧操作的合法序列。

（1）能否得到輸出順序?yàn)?25641的序列。（5分）

（2）能否得到輸出順序?yàn)?54623的序列。（5分）【北方交通大學(xué)1995

一（10分）】

12.（1）什么是遞歸程序？

（2）遞歸程序的優(yōu)、缺點(diǎn)是什么？

（3）遞歸程序在執(zhí)行時，應(yīng)借助于什么來完成？

（4）遞歸程序的入口語句、出口語句一般用什么語句實(shí)現(xiàn)？【大連海

事大學(xué)1996二、4(4分)】

13.設(shè)有下列遞歸算法：

FUNCTIONvol(n:integer):integer;

VARx:integer:

BEGINIFn=0THENvol:=0

ELSEBEGINread(x)；vol:=vol(n-l)+x；END；

END；

如該函數(shù)被調(diào)用時，參數(shù)n值為4,讀入的x值依次為5,3,4,2,函數(shù)調(diào)用

結(jié)束時返回值vol為多少？用圖示描述函數(shù)執(zhí)行過程中，遞歸工作棧的變化

過程?！颈本┕I(yè)大學(xué)1998四(10分)】

14.當(dāng)過程P遞歸調(diào)用自身時，過程P內(nèi)部定義的局部變量在P的2次調(diào)

用期間是否占用同一數(shù)據(jù)區(qū)？為什么？【山東師范大學(xué)1999一、4(4

分)】

15.試推導(dǎo)出當(dāng)總盤數(shù)為n的Hanoi塔的移動次數(shù)?！颈本┼]電大學(xué)2001

四、3(5分)】

16.對下面過程寫出調(diào)用P(3)的運(yùn)行結(jié)果。

PROCEDUREp(w：integer);

BEGIN

IFw>0THEN

BEGIN

p(w-l);

writein(w);{輸出W}

p(w-1)

END；

END；

【西北大學(xué)2001三、7]

17.用一個數(shù)組S(設(shè)大小為MAX)作為兩個堆棧的共享空間。請說明共享

方法，棧滿/?？盏呐袛鄺l件，并用C或PASCAL設(shè)計(jì)公用的入棧操作push

(i,x),其中i為0或1,用于表示棧號，x為入棧值。

【浙江大學(xué)1998五、2(7分)】

18.簡述下列程序段的功能。

PROCalgo(VARS:stack;k:integer);

VART:stack;temp:integer;

WHILENOTempty(S)DO

[temp:=P0P(S);IFtempOkTHENPUSH(T,temp)];

WHILENOTempty(T)DO[temp:=POP(T);PUSH⑸temp)];

【山東科技大學(xué)2002一、1(4分)】

19.用棧實(shí)現(xiàn)將中綴表達(dá)式8-（3+5）*（5-6/2）轉(zhuǎn)換成后綴表達(dá)式，畫出棧

的變化過程圖。

【南京航空航天大學(xué)2001五（10分）】

20.在表達(dá)式中，有的運(yùn)算符要求從右到左計(jì)算，如A**B**C的計(jì)算次序

應(yīng)為（A**（B**C））,這在由中綴生成后綴的算法中是怎樣實(shí)現(xiàn)的？（以**為例

說明）【東南大學(xué)1993一、2（6分）1997一、1（8分）】

21.有遞歸算法如下：

FUNCTIONsum（n:integer）:intger;

BEGIN

IFn=0THENsum:=0

ELSEBEGINread（x）；sum:=sum（nT）+xEND；

END；

設(shè)初值n=4,讀入x=4,9,6,2

問：（1）若x為局部變量時；該函數(shù)遞歸結(jié)束后返回調(diào)用程序的sum=?并

畫出在遞歸過程中棧狀態(tài)的變化過程；

（2）若x為全程變量遞歸結(jié)束時返回調(diào)用程序的sum=?【北京郵電

大學(xué)1997—（10分）】

22.畫出對算術(shù)表達(dá)式A-B*C/D-EtF求值時操作數(shù)棧和運(yùn)算符棧的變化

過程。

【東南大學(xué)2000一、3（6分）】

23.計(jì)算算術(shù)表達(dá)式的值時，可用兩個棧作輔助工具。對于給出的一個表

達(dá)式，從左向右掃描它的字符，并將操作數(shù)放入棧S1中，運(yùn)算符放入棧

S2中，但每次掃描到運(yùn)算符時，要把它同S2的棧頂運(yùn)算符進(jìn)行優(yōu)先級比

較，當(dāng)掃描到的運(yùn)算符的優(yōu)先級不高于棧頂運(yùn)算符的優(yōu)先級時，取出棧S1

的棧頂和次棧頂?shù)膬蓚€元素，以及棧S2的棧頂運(yùn)算符進(jìn)行運(yùn)算將結(jié)果放入

棧S1中（得到的結(jié)果依次用Tl、T2等表示）。為方便比較，假設(shè)棧S2的

初始棧頂為?（夠算符的優(yōu)先級低于加、減、乘、除中任何一種運(yùn)算）現(xiàn)假設(shè)

要計(jì)算表達(dá)式：A-B*C/D+E/FO寫出棧S1和S2的變化過程?！旧綎|科技大

學(xué)2001—、4（7分）】

24.有字符串次序?yàn)?*-y-a/y，2,利用棧，給出將次序改為3y-*ay2"-的操

作步驟。（可用X代表掃描該字符串過程中順序取一個字符進(jìn)棧的操作，

用S代表從棧中取出一個字符加入到新字符串尾的出棧操作。例如，ABC

變?yōu)锽CA的操作步驟為XXSXSS）【東北大學(xué)2001一、4（4分）】

25.內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m）提供給兩個棧S1和S2

使用，怎樣分配這部分存儲空間，使得對任一個棧，僅當(dāng)這部分空間全滿

時才發(fā)生上溢?！緰|北大學(xué)2000一、1（3分）】

26.將兩個棧存入數(shù)組應(yīng)如何安排最好？這時棧空、棧滿的條件

是什么？【東南大學(xué)1998一、5]

27.在一個算法中需要建立多個堆棧時可以選用下列三種方案之一，試問：

這三種方案之間相比較各有什么優(yōu)缺點(diǎn)？

（1）分別用多個順序存儲空間建立多個獨(dú)立的堆棧；

（2）多個堆棧共享一個順序存儲空間；

（3）分別建立多個獨(dú)立的鏈接堆棧?！颈本┖娇蘸教齑髮W(xué)1998一、6

（4分）】

28.在某程序中，有兩個棧共享一個一維數(shù)組空間SPACE[N]、SPACE[OK

SPACE[N-1]分別是兩個棧的棧底。

（1）對棧1、棧2,試分別寫出（元素x）入棧的主要語句和出棧的主

要語句。

（2）對棧1、棧2,試分別寫出棧滿、?？盏臈l件?！颈本├砉ご髮W(xué)1999

二、2（8分）】

29.簡述順序存儲隊(duì)列的假溢出的避免方法及隊(duì)列滿和空的條件L山東大

學(xué)2000—、2（4分）】

30.舉例說明順序隊(duì)的“假溢出”現(xiàn)象，并給出解決方案?！靖Ｖ荽髮W(xué)1998

三、5（6分）】

31.怎樣判定循環(huán)隊(duì)列的空和滿？【燕山大學(xué)1999二、3（4分）】

32.簡要敘述循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，并寫出其初始狀態(tài)、隊(duì)列空、隊(duì)列滿

時的隊(duì)首指針與隊(duì)尾指針的值。

【南京航空航天大學(xué)1995七（5分）】

33.利用兩個棧sl,s2模擬一個隊(duì)列時，如何用棧的運(yùn)算實(shí)現(xiàn)隊(duì)列的插入，

刪除以及判隊(duì)空運(yùn)算。請簡述這些運(yùn)算的算法思想?！颈本┼]電大學(xué)1992

一、1】【東南大學(xué)1999一、1（7分）】

34.一個循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)描述如下：

TYPEsequeuetp=RECORD

elem：ARRAY[1..MAXSIZE]OFelemtp；front,rear：0..MAXSIZE；

END；

給出循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿的判斷條件，并且分析一下該條件對隊(duì)列實(shí)際

存儲空間大小的影響，如果為了不損失存儲空間，你如何改進(jìn)循環(huán)隊(duì)列的

隊(duì)空和隊(duì)滿的判斷條件？【西北工業(yè)大學(xué)1999三（8分）】

35.如果用一個循環(huán)數(shù)組表示隊(duì)列時，該隊(duì)列只有一個隊(duì)列頭

指針front,不設(shè)隊(duì)列尾指針rear,而改置計(jì)數(shù)器count用以記錄隊(duì)列中

結(jié)點(diǎn)的個數(shù)。

（1）編寫實(shí)現(xiàn)隊(duì)列的三個基本運(yùn)算：判空、入隊(duì)、出隊(duì)（3分）

（2）隊(duì)列中能容納元素的最多個數(shù)是多少？（1分）【東北大學(xué)2002—、

1]

36.給出循環(huán)隊(duì)列中元素個數(shù)的計(jì)算式（設(shè)隊(duì)最大長度為N,隊(duì)首指針

FRONT,隊(duì)尾指針REAR）

【西北大學(xué)2000二、7（5分）】

37.順序隊(duì)列一般應(yīng)該組織成為環(huán)狀隊(duì)列的形式，而且一般隊(duì)列頭或尾其

中之一應(yīng)該特殊處理。例如,隊(duì)列為listarray[O..n-1],隊(duì)列頭指針為

front,隊(duì)列尾指針為rear,則listarray[rear]表示下一個可以插入

隊(duì)列的位置。請解釋其原因。【北京大學(xué)1999一、3（20/3分）】

38.設(shè)一個雙端隊(duì)列，元素進(jìn)入該隊(duì)列的次序?yàn)閍,b,c,do求既不能由

輸入受限的雙端隊(duì)列得到,又不能由輸出受限的雙端隊(duì)列得到的輸出序列。

【中山大學(xué)1999一、4（3分）】

39.若以1、2、3、4作為雙端隊(duì)列的輸入序列，試分別求出以下條件的輸

出序列：

①能由輸入受限的雙端隊(duì)列得到，但不能由輸出受限的雙端隊(duì)列得到

的輸出序列；

②能由輸出受限的雙端隊(duì)列得到，但不能由輸入受限的雙端隊(duì)列得到

的輸出序列；

⑶既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列

得到的輸出序列。

【山東科技大學(xué)2001—、3（6分）】

40.假設(shè)以數(shù)組sq[0..7]存放循環(huán)隊(duì)列元素，變量f指向隊(duì)頭元素的前一

位置，變量r指向隊(duì)尾元素，如用A和D分別表示入隊(duì)和出隊(duì)操作，請給出：

（1）隊(duì)空的初始條件；

（2）執(zhí)行操作序列A3DIA5D2ADA，時的狀態(tài)，并作必要的說明?！颈狈浇?/p>

通大學(xué)1993四（12分）】

41、設(shè)輸入元素為1、2、3、P和A,輸入次序?yàn)?23PA,如圖（編者略）。

元素經(jīng)過棧后達(dá)輸出序列，當(dāng)所有元素均到達(dá)輸出序列后，有哪些序列可

以作為高級語言的變量名?！局猩酱髮W(xué)1997]

五算法設(shè)計(jì)題

1.設(shè)有兩個棧S,S都采用順序棧方式，并且共享一個存儲區(qū)

12

[0..maxsize-1],為了盡量利用空間，減少溢出的可能，可采用棧頂相向，

迎面增長的存儲方式。試設(shè)計(jì)S,S有關(guān)入棧和出棧的操作算法。

12

【哈爾濱工業(yè)大學(xué)2001七（12分）】

2.設(shè)從鍵盤輸入一整數(shù)的序列：a,a,a,”，a，試編寫算法實(shí)現(xiàn)：用

123n

棧結(jié)構(gòu)存儲輸入的整數(shù)，當(dāng)3工-1時，將a,進(jìn)棧；當(dāng)3=-1時，輸出棧頂

整數(shù)并出棧。算法應(yīng)對異常善況（入棧滿等’）給出相應(yīng)的信息。

【南京航空航天大學(xué)1998六（10分）】

3.設(shè)表達(dá)式以字符形式已存入數(shù)組E[n]中，'中為表達(dá)式的結(jié)束符，試

寫出判斷表達(dá)式中括號（'（'和'）'）是否配對的C語言描述算法：EXYX（E）;

（注：算法中可調(diào)用棧操作的基本算法。）

【北京科技大學(xué)2001九、1（10分）】

4.從鍵盤上輸入一個逆波蘭表達(dá)式，用偽碼寫出其求值程序。規(guī)定：逆波蘭

表達(dá)式的長度不超過一行，決符作為輸入結(jié)束，操作數(shù)之間用空格分隔，操

作符只可能有+、-、*、/四種運(yùn)算。例如:23434+2*$

【山東師范大學(xué)1999七（10分）】

5.假設(shè)以I和0分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧

和出棧的操作序列可表示為僅由I和0組成的序列，稱可以操作的序列為

合法序列，否則稱為非法序列。

（1）下面所示的序列中哪些是合法的？

A.I0II0I00B.I00I0II0C.III0I0I0D.

III00I00

（2）通過對（1）的分析，寫出一個算法，判定所給的操作序列是否合

法。若合法，返回true,否則返回false（假定被判定的操作序列已存入

一維數(shù)組中）?！疚錆h大學(xué)2000五、2]

6.設(shè)計(jì)一個算法，判斷一個算術(shù)表達(dá)式中的括號是否配對。算術(shù)表達(dá)式保

存在帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，每個結(jié)點(diǎn)有兩個域：ch和link,其中ch

域?yàn)樽址愋??！灸暇┼]電大學(xué)2000五】

7.請利用兩個棧S1和S2來模擬一個隊(duì)列。已知棧的三個運(yùn)算定義如下：

PUSH（ST,x）:元素x入ST棧；POP（ST,x）：ST棧頂元素出棧，賦給變量x；

Semply（ST）：判ST棧是否為空。那么如何利用棧的運(yùn)算來實(shí)現(xiàn)該隊(duì)列的三個

運(yùn)算：enqueue:插入一個元素入隊(duì)列；dequeue:刪除一個元素出隊(duì)列；

queue_empty：判隊(duì)列為空。（請寫明算法的思想及必要的注釋）

【西安電子科技大學(xué)2001軟件五（10分）】【上海交通大學(xué)1999二（12

分）】【河海大學(xué)1998三（12分）】

類似本題的另外敘述有：

（1）有兩個長度相同的棧S1,S2,已知以下入棧、出棧、判棧滿和判

?？詹僮鳎?/p>

PROCEDUREpush（Stack:Stacktype;x:Datatype）;

FUNCTIONPop（Stack:Stacktype）:Datatype;

FUNCTIONFul1（Stack:Stacktype）:Boolean;

FUNCTIONEmpty（Stack:Stacktype）Boolean;

現(xiàn)用此二棧構(gòu)成一個隊(duì)列，試寫出下面入隊(duì)列、出隊(duì)列操作算法：

PROCEDUREEnQueue（x:Datatype）;

FUNCTIONDeQueue:Datatype;【北京郵電大學(xué)2000六（10分）】

8.設(shè)結(jié)點(diǎn)結(jié)構(gòu)為（data,link）,試用一個全局指針p和某種鏈接結(jié)構(gòu)實(shí)現(xiàn)

一個隊(duì)列，畫出示意圖，并給出入隊(duì)addq和出隊(duì)deleteq過程，要求它們的

時間復(fù)雜性都是0（1）（不計(jì)new和dispose時間）

【東南大學(xué)1996二（10分

第三章棧和隊(duì)列

一、選擇題

1.B2.1B2.2A2.3B2.4D2.5.C3.B4.D5.D6.C7.D8.B

9.D10.D11.D12.C13.B14.C15.B16.D17.B18.B19.B20.D

21.D22.D23.D24.C25.A26.A27.D28.B29.BD30.C31.B32.C

33.1B33.2A33.3C33.4C33.5F34.C35.C36.A37.AD

二、判斷題

1.2.V3.4.5.x6.V7.8.9.10.x11.12.x

VVJVVVV

13.14.x15.16.x17.18.x19.20.

X