第3章????? 棧和隊(duì)列

一? 選擇題

1. 對(duì)于棧操作數(shù)據(jù)的原則是（?? ）?！厩鄭u大學(xué) 2001 五、2（2分）】

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

2. 在作進(jìn)棧運(yùn)算時(shí),應(yīng)先判別棧是否( ?① ?),在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否( ②? ?)。當(dāng)棧中元素為n個(gè),作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說明該棧的最大容量為( ?③ ?)。

為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí),應(yīng)將兩棧的 ( ④ ??)分別設(shè)在這片內(nèi)存空間的兩端,這樣,當(dāng)(? ⑤ ?)時(shí)，才產(chǎn)生上溢。

①, ②: A. 空????? ???B. 滿????????? C. 上溢???? ???D. 下溢?????

??? ③: A. n-1?? ?????B. n????????? ?C. n+1 ????????D.? n/2

??? ④: A. 長(zhǎng)度? ?????B. 深度?????? ?C. 棧頂?? ?????D. 棧底

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

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

??????? C. 兩個(gè)棧的棧頂在?？臻g的某一位置相遇.

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

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

3. 一個(gè)棧的輸入序列為123…n，若輸出序列的第一個(gè)元素是n，輸出第i（1<=i<=n）個(gè)元素是（??? ）。

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

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

4. 若一個(gè)棧的輸入序列為1,2,3,…,n，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是（???? ）。

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

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

5. 若已知一個(gè)棧的入棧序列是1,2,3,…,n，其輸出序列為p₁,p₂,p₃，…，p_N,若p_N是n，則p_i是(??? )。

??? A. i_?? ?????????B. n-i??????? C. n-i+1?????? D. 不確定

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

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

A. 5 4 3 6 1 2???? B. 4 5 3 1 2 6???? C. 3 4 6 5 2 1??? D. 2 3 4 1 5 6

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

7. 設(shè)棧的輸入序列是1，2，3，4,則（? ）不可能是其出棧序列?！局锌圃河?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. 一個(gè)棧的輸入序列為1 2 3 4 5，則下列序列中不可能是棧的輸出序列的是（??? ）。

?? A. 2 3 4 1 5???? B. 5 4 1 3 2???? C. 2 3 1 4 5????? D. 1 5 4 3 2

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

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

A. 5 1 2 3 4??????? B. 4 5 1 3 2????? C. 4 3 1 2 5??????? D. 3 2 1 5 4

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

10. 某堆棧的輸入序列為a, b，c ，d,下面的四個(gè)序列中，不可能是它的輸出序列的是（??? ）。

??? A. a，c，b，d???????? B. b, c，d，a??? C. c, d，b, a???????? D. d, c，a，b

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

11. 設(shè)abcdef以所給的次序進(jìn)棧，若在進(jìn)棧操作時(shí)，允許退棧操作,則下面得不到的序列為（??? ）。

A．fedcba ??????B. bcafed ???????C. dcefba? ??????D. cabdef

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

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

A．XYZ?? ????????B. YZX??? ????????C. ZXY???? ???????D. ZYX

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

13. 輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過的棧操作為（??? ）【中山大學(xué) 1999 一、8(1分)】

A. push,pop,push,pop,push,pop??????? B. push,push,push,pop,pop,pop

??? C. push,push,pop,pop,push,pop??????? D. push,pop,push,push,pop,pop

14. 若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針top為n+1，則下面x進(jìn)棧的正確操作是( ???)。

A．top:=top+1; ?V [top]:=x?????? ?????B.? V [top]:=x; top:=top+1?? ?

C. top:=top-1; ?V [top]:=x????? ??????D. ?V [top]:=x; top:=top-1

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

15. 若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V[1..m]，top[i]代表第i個(gè)棧( i =1,2)棧頂，棧1的底在v[1]，棧2的底在V[m]，則棧滿的條件是（??? ）。

A. |top[2]-top[1]|=0? ?B. top[1]+1=top[2] ???C. top[1]+top[2]=m ????D. top[1]=top[2]

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

16. 棧在（??? ）中應(yīng)用?！局猩酱髮W(xué) 1998 二、3（2分）】

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

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

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

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

???? int?? f(int x)

?? ??{ return? ((x>0) ? x* f(x-1):2);}

??? ??int i? ;

??? ??i =f(f(1));

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

19. 表達(dá)式a*(b+c)-d的后綴表達(dá)式是(??? )。【南京理工大學(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時(shí)，對(duì)象棧和算符棧為（ ??），其中^為乘冪 。

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ì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（??? ）數(shù)據(jù)結(jié)構(gòu)最佳。

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

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

22. 用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（??? ）?！颈狈浇煌ù髮W(xué) 2001 一、12（2分）】

A. 僅修改頭指針?? B. 僅修改尾指針??? C. 頭、尾指針都要修改??? D. 頭、尾指針可能都要修改

23. 用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)(??? ?)?！颈本├砉ご髮W(xué) 2001 六、3（2分）】

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

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

24. 遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（??? ）的數(shù)據(jù)結(jié)構(gòu)。

A．隊(duì)列? ???????????B．多維數(shù)組?? ????????C．棧???????????? D. 線性表

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

25. 假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素,其頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（??? ）?！颈本┕ど檀髮W(xué) 2001 一、2（3分）】

A．(rear-front+m)%m???? B．rear-front+1????? C．(front-rear+m)%m????? D．(rear-front)%m

26. 循環(huán)隊(duì)列A[0..m-1]存放其元素值，用front和rear分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素?cái)?shù)是(??? )。【南京理工大學(xué) 2001 一、5（1.5分）】

A. (rear-front+m)%m???? ?B. rear-front+1??? C. ?rear-front-1? ??D. ?rear-front

27. 循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為（??? ）?！局猩酱髮W(xué) 1999 一、6（1分）】

A. rear=rear+1 ??????????????B. rear=(rear+1) mod (m-1)

????C. rear=(rear+1) mod m ??????D. rear=(rear+1)mod(m+1)

28. 若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？(? )【浙江大學(xué)1999 四、1(4分)】

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

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

??? A. dacb??? ?B. cadb????? C. dbca?????? D. bdac???? E. 以上答案都不對(duì)?

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

30. 若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是(?? )?！疚靼搽娮涌萍即髮W(xué) 1996 一、5（2分）】

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

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

???? A. (rear+1) MOD n=front?????????????????? B. rear=front??????????????????????????????????????????????????? ??????

C．rear+1=front?????????????????????????? D. (rear-l) MOD n=front

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

32. 棧和隊(duì)列的共同點(diǎn)是（??? ）。【燕山大學(xué) 2001 一、1（2分）】

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

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

33. 棧的特點(diǎn)是（? ①? ）,隊(duì)列的特點(diǎn)是（? ②? ）,棧和隊(duì)列都是（? ③? ）。若進(jìn)棧序列為1,2,3,4 則（? ④? ）不可能是一個(gè)出棧序列（不一定全部進(jìn)棧后再出棧）；若進(jìn)隊(duì)列的序列為1,2,3,4 則（? ⑤? ）是一個(gè)出隊(duì)列序列?！颈狈浇煌ù髮W(xué) 1999 一、1（5分）】

①, ②: A. 先進(jìn)先出????????? B. 后進(jìn)先出??????? C. 進(jìn)優(yōu)于出????? D. 出優(yōu)于進(jìn)

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

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

④, ⑤: A. 3,2,1,4??? B. 3,2,4,1??? C. 4,2,3,1?? D. 4,3,2,1??? F. 1,2,3,4??? G. 1,3,2,4

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

A．順序存儲(chǔ)的線性結(jié)構(gòu)?????? B. 鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)

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

35. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，e3，e4,e5和e6依次通過棧S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e2，e4，e3,e6,e5,e1則棧S的容量至少應(yīng)該是(??? )。

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

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

36. 用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的（??? ）位置?！厩迦A大學(xué) 1998 一、1（2分）】

A．鏈頭? ???????????B．鏈尾?? ????????????C．鏈中

37. 依次讀入數(shù)據(jù)元素序列{a，b，c，d，e，f，g}進(jìn)棧,每進(jìn)一個(gè)元素，機(jī)器可要求下一個(gè)元素進(jìn)棧或彈棧，如此進(jìn)行，則?？諘r(shí)彈出的元素構(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分）】【中國(guó)科技大學(xué) 1998 二、2（2分）】

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

3. 兩個(gè)棧共用靜態(tài)存儲(chǔ)空間，對(duì)頭使用也存在空間溢出問題。（??? ）【青島大學(xué) 2000 四、2（1分）】

4．兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。（??? ）【上海海運(yùn)學(xué)院 1998 一、4（1分）】

5. 即使對(duì)不含相同元素的同一輸入序列進(jìn)行兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（??? ）【北京郵電大學(xué) 1999 二、4（2分）】

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

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

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

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

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

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

10．若輸入序列為1，2，3，4，5，6，則通過一個(gè)?？梢暂敵鲂蛄?，5，4，6，2，3。（? ??）

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

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

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

【上海交通大學(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ì)列邏輯上是一個(gè)下端和上端既能增加又能減少的線性表。（?? ）【上海交通大學(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)算。（ ）【長(zhǎng)沙鐵道學(xué)院1997一、5(1分)】

19. 棧和隊(duì)列都是線性表，只是在插入和刪除時(shí)受到了一些限制。（??? ）【北京郵電大學(xué)2002一、3(1分)】

20. 棧和隊(duì)列的存儲(chǔ)方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞健?#xff08;??? ）

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

?

三? 填空題

1．棧是_______的線性表，其運(yùn)算遵循_______的原則?！颈本┛萍即髮W(xué) 1997 一、3】

2．_______是限定僅在表尾進(jìn)行插入或刪除操作的線性表?！狙嗌酱髮W(xué) 1998 一、3 （1分）】

3. 一個(gè)棧的輸入序列是：1，2，3則不可能的棧輸出序列是_______。【中國(guó)人民大學(xué)2001一、1(2分)】

4. 設(shè)有一個(gè)空棧，棧頂指針為1000H(十六進(jìn)制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是_______，而棧頂指針值是_______H。設(shè)棧為順序棧，每個(gè)元素占4個(gè)字節(jié)?！疚靼搽娮涌萍即髮W(xué) 1998 二、1（4分）】

5. 當(dāng)兩個(gè)棧共享一存儲(chǔ)區(qū)時(shí)，棧利用一維數(shù)組stack(1,n)表示，兩棧頂指針為top[1]與top[2]，則當(dāng)棧1空時(shí)，top[1]為_______，棧2空時(shí) ，top[2]為_______，棧滿時(shí)為_______。

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

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

7．在作進(jìn)棧運(yùn)算時(shí)應(yīng)先判別棧是否_(1)_;在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否_(2)_；當(dāng)棧中元素為n個(gè)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說明該棧的最大容量為_(3)_。

為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的空間時(shí)，應(yīng)將兩棧的_(4)_分別設(shè)在內(nèi)存空間的兩端，這樣只有當(dāng)_(5)_時(shí)才產(chǎn)生溢出?！旧綎|工業(yè)大學(xué) 1994 一、1（5分）】

8. 多個(gè)棧共存時(shí)，最好用_______作為存儲(chǔ)結(jié)構(gòu)?！灸暇├砉ご髮W(xué) 2001 二、7（2分）】

9．用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為_______?！疚髂辖煌ù髮W(xué) 2000 一、5】

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

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

11．表達(dá)式23+((12*3-2)/4+34*5/7)+108/9的后綴表達(dá)式是_______。【中山大學(xué) 1998 一、4（1分）】

12. 循環(huán)隊(duì)列的引入，目的是為了克服_______?！緩B門大學(xué) 2001 一、1 （14/8分）】??????????????????????????????????

13．用下標(biāo)0開始的N元數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列時(shí)，為實(shí)現(xiàn)下標(biāo)變量M加1后在數(shù)組有效下標(biāo)范圍內(nèi)循環(huán)，可采用的表達(dá)式是：M：=_______（填PASCAL語言，C語言的考生不填）； M= _______（填C語言，PASCAL語言的考生不填）。【西南交通大學(xué) 2000 一、7】

14．________又稱作先進(jìn)先出表。【重慶大學(xué) 2000 一、7】

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

16．隊(duì)列是限制插入只能在表的一端，而刪除在表的另一端進(jìn)行的線性表，其特點(diǎn)是_______。

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

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

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

18．區(qū)分循環(huán)隊(duì)列的滿與空，只有兩種方法，它們是______和______?！颈本┼]電大學(xué)2001 二、2（4分）】

19．設(shè)循環(huán)隊(duì)列用數(shù)組A[1..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ì)操作可表示為_______，若用犧牲一個(gè)單元的辦法來區(qū)分隊(duì)滿和隊(duì)空（設(shè)隊(duì)尾指針sq.rear）,則隊(duì)滿的條件為_______。

【長(zhǎng)沙鐵道學(xué)院 1997 二、4 (4分)】

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

22．循環(huán)隊(duì)列用數(shù)組A[0..m-1]存放其元素值，已知其頭尾指針分別是front和rear ，則當(dāng)前隊(duì)列的元素個(gè)數(shù)是_______。【廈門大學(xué) 2000 六、1（16%/3分）】

23．設(shè)Q[0..N-1]為循環(huán)隊(duì)列，其頭、尾指針分別為P和R，則隊(duì)Q中當(dāng)前所含元素個(gè)數(shù)為_______。

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

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

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

FUNC? compute(a):real;?? 后綴表達(dá)式存儲(chǔ)在數(shù)組a[1..m]中。

BEGIN

? ?setnull(s)；i:=1；ch:= (1)______；

?? WHILE ch<>’@’ DO

???? BEGIN

?????? CASE ch OF

???? ???‘0’..‘9’:? x:=0;

???? ?????????WHILE ch<>’,’DO

?????? ?????????BEGIN

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

??????? ??????????i:=i+1；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+1；ch:=a[i]；

END;

comput:= (3)_______；

END;

25. 算術(shù)表達(dá)式求值的流程，其中OPTR為算術(shù)符棧，OPND為操作數(shù)棧，precede(oper1，oper2)是比較運(yùn)算符優(yōu)先級(jí)別的函數(shù)，operate(opnd1,oper,opnd2)為兩操作數(shù)的運(yùn)算結(jié)果函數(shù)。（#表示運(yùn)算起始和終止符號(hào)）【西北工業(yè)大學(xué) 1999 六、2 (7分)】

? FUNCTION? exp_reduced:operandtype;

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

? WHILE? NOT((w='#’) AND (GETTOP(OPTR)='#')) DO

???? IF NOT w in op THEN PUSH(OPND,w);

???? ELSE CASE precede(GETTOP(OPTR),w)OF

?????????? ???'<':[(1)_______; read(w);]

????????? ????'=':[(2)_______; 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_n和一個(gè)能裝載總重量為T的背包。能否從n件物品中選擇若干件恰好使它們的重量之和等于T。若能，則背包問題有解，否則無解。解此問題的算法如下：?

??? FUNCTION kanp_stack(VAR stack,w:ARRAY[1..n] OF real; VAR top:integer; T:real):boolean;

???? {w[1：n] 存放n件物品的重量，依次從中取出物品放入背包中，檢查背包重量，若不超過T，則裝入，否則棄之，取下一個(gè)物品試之。若有解則返回函數(shù)值true,否則返回false}

BEGIN

??? top:=0;? i:=1;?????????????? { i指示待選物品}

??? WHILE (1)_______ AND(2)_______DO

?????? [IF (3)______ OR (4)_______ AND (i<n)

????????? THEN? [top := (5)_______ ;stack[top] :=i;{第i件物品裝入背包}

???????????? ????T:=T-w[i]];

??????? IF T=0 THEN RETURN ((6)_______)? {背包問題有解}

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

?????????????? ???????THEN? [i:=(7)_______;{取出棧頂物品}

????????????????? ???????????top:= (8)_______ ；T:= (9)_______ ];? {恢復(fù)T值}

?????????????? ????????i:=i+1??????? {準(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分別表示入棧和出棧操作，則對(duì)初態(tài)和終態(tài)均為空的棧操作可由S和X組成的序列表示（如SXSX）。

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

（2）兩個(gè)不同合法序列（對(duì)同一輸入序列）能否得到相同的輸出元素序列？如能得到，請(qǐng)舉列說明。

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

5. 有5 個(gè)元素，其入棧次序?yàn)?#xff1a;A，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個(gè)且D第二個(gè)出棧）的次序有哪幾個(gè)？【西南交通大學(xué) 2000 二、1】

6. 如果輸入序列為1 2 3 4 5 6,試問能否通過棧結(jié)構(gòu)得到以下兩個(gè)序列:4 3 5 6 1 2和1 3 5 4 2 6;請(qǐng)說明為什么不能或如何才能得到?！疚錆h交通科技大學(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,試寫出借助一個(gè)?？傻玫降膬蓚€(gè)輸出序列和兩個(gè)不能得到的輸出序列。

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

9. 設(shè)輸入序列為2，3，4，5，6，利用一個(gè)棧能得到序列2，5，3，4，6嗎？?？梢杂脝捂湵韺?shí)現(xiàn)嗎？

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

10. 試證明：若借助棧由輸入序列1,2,…,n得到輸出序列為P₁,P₂,…,P_n（它是輸入序列的一個(gè)排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i<j<k,使P_j<P_k<P_i。【上海交通大學(xué) 1998 二（15分）】

11. 設(shè)一數(shù)列的輸入順序?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í)行時(shí)，應(yīng)借助于什么來完成？

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

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

FUNCTION? vol(n:integer):integer;

VAR??? x :integer:

BEGIN IF n=0 THEN? vol:=0

???????????? ELSE?? BEGIN read(x)；vol:=vol(n-1)+x；END；

?END；

如該函數(shù)被調(diào)用時(shí)，參數(shù)n值為4,讀入的x值依次為5,3,4,2，函數(shù)調(diào)用結(jié)束時(shí)返回值vol為多少?用圖示描述函數(shù)執(zhí)行過程中，遞歸工作棧的變化過程。【北京工業(yè)大學(xué) 1998 四 (10分)】

14. 當(dāng)過程P遞歸調(diào)用自身時(shí)，過程P內(nèi)部定義的局部變量在P的2次調(diào)用期間是否占用同一數(shù)據(jù)區(qū)？為什么？【山東師范大學(xué) 1999 一、4 （4分）】

15. 試推導(dǎo)出當(dāng)總盤數(shù)為n的Hanoi塔的移動(dòng)次數(shù)。 【北京郵電大學(xué) 2001 四、3 （5分）】

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

PROCEDURE p（w：integer）;

?? BEGIN

???? ?IF w>0 THEN

?BEGIN

????????????????? p(w-1);

????????????????? writeln(w);{輸出W}

???????????? ?????p(w-1）

END；

? ?END；

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

17. 用一個(gè)數(shù)組S（設(shè)大小為MAX）作為兩個(gè)堆棧的共享空間。請(qǐng)說明共享方法，棧滿/?？盏呐袛鄺l件，并用C或PASCAL設(shè)計(jì)公用的入棧操作push（i，x），其中i為0或1，用于表示棧號(hào)，x為入棧值。

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

18. 簡(jiǎn)述下列程序段的功能。

PROC??? algo(VAR S : stack;? k:integer);

VAR?? T: stack; temp: integer;

??? WHILE NOT? empty(S) DO

????? [temp:=POP(S); IF temp<>k? THEN PUSH(T,temp)];

??? WHILE NOT? empty(T)? DO?? [temp:=POP(T);PUSH(S,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. 有遞歸算法如下：

FUNCTION? sum (n:integer):intger;

BEGIN?

?IF n=0 THEN sum:=0

?????????? ?ELSE BEGIN read(x)；sum:=sum(n-1)+x END；

END；

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

? 問：(1) 若x為局部變量時(shí)；該函數(shù)遞歸結(jié)束后返回調(diào)用程序的sum=? 并畫出在遞歸過程中棧狀態(tài)的變化過程；

????? (2) 若x為全程變量遞歸結(jié)束時(shí)返回調(diào)用程序的sum=?【北京郵電大學(xué) 1997 一 （10分）】

22. 畫出對(duì)算術(shù)表達(dá)式A-B*C/D-E↑F求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程。

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

23. 計(jì)算算術(shù)表達(dá)式的值時(shí)，可用兩個(gè)棧作輔助工具。對(duì)于給出的一個(gè)表達(dá)式，從左向右掃描它的字符，并將操作數(shù)放入棧S1中，運(yùn)算符放入棧S2中，但每次掃描到運(yùn)算符時(shí)，要把它同S2的棧頂運(yùn)算符進(jìn)行優(yōu)先級(jí)比較，當(dāng)掃描到的運(yùn)算符的優(yōu)先級(jí)不高于棧頂運(yùn)算符的優(yōu)先級(jí)時(shí)，取出棧S1的棧頂和次棧頂?shù)膬蓚€(gè)元素，以及棧S2的棧頂運(yùn)算符進(jìn)行運(yùn)算將結(jié)果放入棧S1中（得到的結(jié)果依次用T1、T2等表示）。為方便比較，假設(shè)棧S2的初始棧頂為?（?運(yùn)算符的優(yōu)先級(jí)低于加、減、乘、除中任何一種運(yùn)算）?，F(xiàn)假設(shè)要計(jì)算表達(dá)式： A-B*C/D+E/F。寫出棧S1和S2的變化過程?！旧綎|科技大學(xué) 2001 一、4 （7分）】

24. 有字符串次序?yàn)?*-y-a/y^2,利用棧，給出將次序改為3y-*ay2^/-的操作步驟。（可用X代表掃描該字符串過程中順序取一個(gè)字符進(jìn)棧的操作，用S代表從棧中取出一個(gè)字符加入到新字符串尾的出棧操作。例如，ABC變?yōu)锽CA的操作步驟為XXSXSS）【東北大學(xué) 2001 一、4 ( 4分)】

25. 內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m）提供給兩個(gè)棧S1和S2使用，怎樣分配這部分存儲(chǔ)空間，使得對(duì)任一個(gè)棧，僅當(dāng)這部分空間全滿時(shí)才發(fā)生上溢?！緰|北大學(xué) 2000 一、1 (3分)】

26. 將兩個(gè)棧存入數(shù)組V[1..m]應(yīng)如何安排最好？這時(shí)棧空、棧滿的條件是什么？【東南大學(xué)1998一、5】

27. 在一個(gè)算法中需要建立多個(gè)堆棧時(shí)可以選用下列三種方案之一，試問：這三種方案之間相比較各有什么優(yōu)缺點(diǎn)？

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

（2）多個(gè)堆棧共享一個(gè)順序存儲(chǔ)空間；

（3）分別建立多個(gè)獨(dú)立的鏈接堆棧。【北京航空航天大學(xué) 1998 一、6（4分）】

28．在某程序中，有兩個(gè)棧共享一個(gè)一維數(shù)組空間SPACE[N]、SPACE[0]、SPACE[N-1] 分別是兩個(gè)棧的棧底。

（1）對(duì)棧1、棧2，試分別寫出（元素x）入棧的主要語句和出棧的主要語句。

（2）對(duì)棧1、棧2，試分別寫出棧滿、棧空的條件?！颈本├砉ご髮W(xué) 1999 二、2（8分）】

29. 簡(jiǎn)述順序存儲(chǔ)隊(duì)列的假溢出的避免方法及隊(duì)列滿和空的條件。【山東大學(xué) 2000 一、2 (4分)】

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

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

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

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

33. 利用兩個(gè)棧sl,s2模擬一個(gè)隊(duì)列時(shí)，如何用棧的運(yùn)算實(shí)現(xiàn)隊(duì)列的插入，刪除以及判隊(duì)空運(yùn)算。請(qǐng)簡(jiǎn)述這些運(yùn)算的算法思想。【北京郵電大學(xué) 1992 ?一、1】【東南大學(xué) 1999 一、1 （7分）】

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

TYPE sequeuetp=RECORD

???? ????????????????elem：ARRAY[1..MAXSIZE] OF elemtp；

??? ?????????????????front，rear：0..MAXSIZE；

?? ????????????????END；

給出循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿的判斷條件，并且分析一下該條件對(duì)隊(duì)列實(shí)際存儲(chǔ)空間大小的影響，如果為了不損失存儲(chǔ)空間，你如何改進(jìn)循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿的判斷條件？【西北工業(yè)大學(xué) 1999 三 (8分)】

35. 如果用一個(gè)循環(huán)數(shù)組q[0..m-1]表示隊(duì)列時(shí)，該隊(duì)列只有一個(gè)隊(duì)列頭指針front，不設(shè)隊(duì)列尾指針rear，而改置計(jì)數(shù)器count用以記錄隊(duì)列中結(jié)點(diǎn)的個(gè)數(shù)。

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

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

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

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

37. 順序隊(duì)列一般應(yīng)該組織成為環(huán)狀隊(duì)列的形式，而且一般隊(duì)列頭或尾其中之一應(yīng)該特殊處理。例如，隊(duì)列為listarray[0..n-1]，隊(duì)列頭指針為 front，隊(duì)列尾指針為 rear， 則listarray [rear]表示下一個(gè)可以插入隊(duì)列的位置。請(qǐng)解釋其原因。【北京大學(xué) 1999 一、3 （20/3分）】

38. 設(shè)一個(gè)雙端隊(duì)列，元素進(jìn)入該隊(duì)列的次序?yàn)閍，b，c，d。求既不能由輸入受限的雙端隊(duì)列得到,又不能由輸出受限的雙端隊(duì)列得到的輸出序列?！局猩酱髮W(xué) 1999 一、4 （3分）】

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

（1）能由輸入受限的雙端隊(duì)列得到，但不能由輸出受限的雙端隊(duì)列得到的輸出序列；

（2）能由輸出受限的雙端隊(duì)列得到，但不能由輸入受限的雙端隊(duì)列得到的輸出序列；

（3）既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列。

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

40. 假設(shè)以數(shù)組sq[0..7]存放循環(huán)隊(duì)列元素,變量f指向隊(duì)頭元素的前一位置,變量r指向隊(duì)尾元素，如用A和D分別表示入隊(duì)和出隊(duì)操作，請(qǐng)給出：

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

（2） 執(zhí)行操作序列A³D¹A⁵D²A¹D²A⁴時(shí)的狀態(tài),并作必要的說明?！颈狈浇煌ù髮W(xué) 1993 四（12分）】

41、設(shè)輸入元素為1、2、3、P和A，輸入次序?yàn)?23PA，如圖（編者略）。元素經(jīng)過棧后達(dá)輸出序列，當(dāng)所有元素均到達(dá)輸出序列后，有哪些序列可以作為高級(jí)語言的變量名?！局猩酱髮W(xué) 1997】

?

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

1. 設(shè)有兩個(gè)棧S₁,S₂都采用順序棧方式，并且共享一個(gè)存儲(chǔ)區(qū)[O..maxsize-1],為了盡量利用空間，減少溢出的可能，可采用棧頂相向，迎面增長(zhǎng)的存儲(chǔ)方式。試設(shè)計(jì)S₁,S₂有關(guān)入棧和出棧的操作算法。

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

2. 設(shè)從鍵盤輸入一整數(shù)的序列：a₁, a₂, a₃，…，a_n,試編寫算法實(shí)現(xiàn)：用棧結(jié)構(gòu)存儲(chǔ)輸入的整數(shù)，當(dāng)a_i≠-1時(shí)，將a_i進(jìn)棧；當(dāng)a_i=-1時(shí)，輸出棧頂整數(shù)并出棧。算法應(yīng)對(duì)異常情況（入棧滿等）給出相應(yīng)的信息。

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

3. 設(shè)表達(dá)式以字符形式已存入數(shù)組E[n]中，‘#’為表達(dá)式的結(jié)束符，試寫出判斷表達(dá)式中括號(hào)（‘（’和‘）’）是否配對(duì)的C語言描述算法：EXYX(E); (注：算法中可調(diào)用棧操作的基本算法。)

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

4. 從鍵盤上輸入一個(gè)逆波蘭表達(dá)式，用偽碼寫出其求值程序。規(guī)定：逆波蘭表達(dá)式的長(zhǎng)度不超過一行，以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔,操作符只可能有+、-、*、/四種運(yùn)算。例如：234 34+2*$

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

5. 假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。

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

???????? A. IOIIOIOO???? B. IOOIOIIO????? C. IIIOIOIO???? D. IIIOOIOO

? （2）通過對(duì)（1）的分析，寫出一個(gè)算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）?！疚錆h大學(xué) 2000 五、2】

6.設(shè)計(jì)一個(gè)算法，判斷一個(gè)算術(shù)表達(dá)式中的括號(hào)是否配對(duì)。算術(shù)表達(dá)式保存在帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)域：ch和link，其中ch域?yàn)樽址愋?。【南京郵電大學(xué) 2000五】

7. 請(qǐng)利用兩個(gè)棧S1和S2來模擬一個(gè)隊(duì)列。已知棧的三個(gè)運(yùn)算定義如下：PUSH(ST,x):元素x入ST棧；POP(ST,x)：ST棧頂元素出棧，賦給變量x；Sempty(ST)：判ST棧是否為空。那么如何利用棧的運(yùn)算來實(shí)現(xiàn)該隊(duì)列的三個(gè)運(yùn)算：enqueue:插入一個(gè)元素入隊(duì)列； dequeue:刪除一個(gè)元素出隊(duì)列；queue_empty：判隊(duì)列為空。（請(qǐng)寫明算法的思想及必要的注釋）

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

類似本題的另外敘述有：

（1）有兩個(gè)長(zhǎng)度相同的棧S1,S2，已知以下入棧、出棧、判棧滿和判?？詹僮?#xff1a;

PROCEDURE ??push(Stack:Stacktype;x:Datatype);

FUNCTION??? Pop(Stack:Stacktype ):Datatype;

FUNCTION??? Full (Stack:Stacktype):Boolean;

FUNCTION??? Empty(Stack:Stacktype)Boolean;

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

PROCEDURE? EnQueue(x:Datatype);

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

8. 設(shè)結(jié)點(diǎn)結(jié)構(gòu)為(data,link)，試用一個(gè)全局指針p和某種鏈接結(jié)構(gòu)實(shí)現(xiàn)一個(gè)隊(duì)列,畫出示意圖,并給出入隊(duì)addq和出隊(duì)deleteq過程,要求它們的時(shí)間復(fù)雜性都是O(l)（不計(jì)new和dispose時(shí)間）

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

9. 假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針，如圖所示（編者略），請(qǐng)寫出相應(yīng)的入隊(duì)列和出隊(duì)列算法?！疚靼搽娮涌萍即髮W(xué) 1999計(jì)應(yīng)用 六 （10分）】

10. 如果允許在循環(huán)隊(duì)列的兩端都可以進(jìn)行插入和刪除操作。要求：

（1）寫出循環(huán)隊(duì)列的類型定義；

（2）寫出“從隊(duì)尾刪除”和“從隊(duì)頭插入”的算法?！颈狈浇煌ù髮W(xué) 1994 ?三 （12分）】

11. 在一個(gè)循環(huán)鏈隊(duì)中只有尾指針（記為rear，結(jié)點(diǎn)結(jié)構(gòu)為數(shù)據(jù)域data，指針域next），請(qǐng)給出這種隊(duì)列的入隊(duì)和出隊(duì)操作的實(shí)現(xiàn)過程?！旧綎|科技大學(xué) 2002 ?一、2 （6分）】

12. 雙端隊(duì)列（duque）是一個(gè)可以在任一端進(jìn)行插入和刪除的線性表?，F(xiàn)采用一個(gè)一維數(shù)組作為雙端隊(duì)列的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，使用類PASCAL語言描述如下：

CONST maxsize=32;????????? {數(shù)組中可容納的元素個(gè)數(shù)}

TYPE duque=RECORD

????????? ??elem: ARRAY[0..MAXSIZE-1] OF datatype;??? {環(huán)形隊(duì)列的存放數(shù)組}

?????????? ?end1,end2:0..MAXSIZE;???????????????? ????{環(huán)形數(shù)組的兩端}

????????? END;

試編寫兩個(gè)算法add(Qu:duque;x:datatype;tag:0..1)和delete（Qu:duque; var x:datatype; tag:0..1）用以在此雙端隊(duì)列的任一端進(jìn)行插入和刪除。當(dāng)tag=0時(shí)在左端endl端操作，當(dāng)tag=1時(shí)在右端end2端操作?！厩迦A大學(xué) ?1998 ?二（10分）】

13. 一個(gè)雙端隊(duì)列deque是限定在兩端end1，end2都可進(jìn)行插入和刪除的線性表。隊(duì)空條件是end1=end2。若用順序方式來組織雙端隊(duì)列，試根據(jù)下列要求，定義雙端隊(duì)列的結(jié)構(gòu)，并給出在指定端i（i=1，2）的插入enq和刪除deq操作的實(shí)現(xiàn)。

（1） 當(dāng)隊(duì)滿時(shí)，最多只能有一個(gè)元素空間可以是空的。

（2） 在做兩端的插入和刪除時(shí)，隊(duì)列中其它元素一律不動(dòng)。【清華大學(xué) 1999 六（12分）】

14. 已知Q是一個(gè)非空隊(duì)列，S是一個(gè)空棧。僅用隊(duì)列和棧的ADT函數(shù)和少量工作變量，使用Pascal或C語言編寫一個(gè)算法，將隊(duì)列Q中的所有元素逆置。棧的ADT函數(shù)有：

makeEmpty(s:stack);?????????????? 置空棧

push(s:stack;value:datatype);?? ??新元素value進(jìn)棧

pop(s:stack):datatype;????????? ??出棧，返回棧頂值

isEmpty(s:stack):Boolean;?????? ??判棧空否

?隊(duì)列的 ADT函數(shù)有：

enqueue(q:queue:value:datatype); ?元素value進(jìn)隊(duì)

deQueue(q:queue):datatype;???? ???出隊(duì)列，返回隊(duì)頭值

isEmpty(q:queue):boolean;???? ????判隊(duì)列空否 【清華大學(xué) 2000 六（12分）】

15. 將n個(gè)隊(duì)列順序映射到數(shù)組v[l..m]中，每一隊(duì)列在v中表示為一循環(huán)隊(duì)列。試畫出其示意圖并寫出對(duì)應(yīng)這種表示的addq和deleteq過程?！緰|南大學(xué) 1993 二（20分）】

16. 設(shè)整數(shù)序列a₁,a₂,…,a_n，給出求解最大值的遞歸程序?！灸暇┖娇蘸教齑髮W(xué) 2000 六】

17．線性表中元素存放在向量A（1,…,n）中，元素是整型數(shù)。試寫出遞歸算法求出A中的最大和最小元素?！颈本┼]電大學(xué) 1994 八 （10分）】

18. 已知求兩個(gè)正整數(shù)m與n的最大公因子的過程用自然語言可以表述為反復(fù)執(zhí)行如下動(dòng)作：第一步：若n等于零，則返回m；第二步：若m小于n，則m與n相互交換；否則，保存m，然后將n送m，將保存的m除以n的余數(shù)送n。

（1）將上述過程用遞歸函數(shù)表達(dá)出來（設(shè)求x除以y的余數(shù)可以用x MOD y 形式表示）。

（2）寫出求解該遞歸函數(shù)的非遞歸算法。【北京航空航天大學(xué) 2001 五（15分）】

19. 寫出和下列遞歸過程等價(jià)的非遞歸過程。

PROCEDURE?? test(VAR? sum:integer);

?? ?VAR? a:integer,

BEGIN

???? ?read(a);

??? ??IF a=0? THEN? sum:=1

? ????????????ELSE ?BEGIN test(sum); sum:=sum*a；END;

write(sum)；

END;??????????????? 【清華大學(xué) 1996 二】

20. 試將下列遞歸過程改寫為非遞歸過程。

??????? void? test(int? &sum)

??????? { int? x；

????????? scanf(x)；

????????? if(x=0) sum=0 else {test(sum); sum+=x;}

????????? printf(sum)；

??????? }??? ?????【北京輕工業(yè)學(xué)院 2000 三 （15分）】

21. 已知Ackermann函數(shù)定義如下:

??????

??? （1） 寫出Ack(2,1)的計(jì)算過程。

（2） 寫出計(jì)算Ack(m,n)的非遞歸算法。 【北京航空航天大學(xué) 1999 ?六 （15分）】

22．設(shè)計(jì)算法以求解從集合{1..n}中選取k（k<=n）個(gè)元素的所有組合。例如，從集合{1..4}中選取2個(gè)元素的所有組合的輸出結(jié)果為：1? 2，1? 3，1 ?4，2? 3， 2? 4，3? 4。

【合肥工業(yè)大學(xué) 2000 五、5（8分）】

總結(jié)

以上是生活随笔為你收集整理的数据结构1800试题(第3章)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。