數(shù)據(jù)結(jié)構(gòu)1800試題-第3章棧和隊列

1、第3章 棧和隊列一 選擇題1. 對于棧操作數(shù)據(jù)的原則是（ ）。【青島大學 2001 五、2（2分）】A. 先進先出 B. 后進先出 C. 后進后出 D. 不分順序2. 在作進棧運算時,應先判別棧是否( 滿 ),在作退棧運算時應先判別棧是否( 空 )。當棧中元素為n個,作進棧運算時發(fā)生上溢,則說明該棧的最大容量為( )。為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個棧共享一片連續(xù)的內(nèi)存空間時,應將兩棧的 ( )分別設在這片內(nèi)存空間的兩端,這樣,當( )時，才產(chǎn)生上溢。 , : A. 空 B. 滿 C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 : A. 長度

2、B. 深度 C. 棧頂 D. 棧底 : A. 兩個棧的棧頂同時到達?？臻g的中心點.B. 其中一個棧的棧頂?shù)竭_棧空間的中心點. C. 兩個棧的棧頂在?？臻g的某一位置相遇. D. 兩個棧均不空,且一個棧的棧頂?shù)竭_另一個棧的棧底.【上海海運學院 1997 二、1（5分）】【上海海運學院 1999 二、1（5分）】3. 一個棧的輸入序列為123n，若輸出序列的第一個元素是n，輸出第i（1=i0) ? x* f(x-1):2); int i ; i =f(f(1);A2 B. 4 C. 8 D. 無限遞歸19. 表達式a*(b+c)-d的后綴表達式是( )?！灸暇├砉ご髮W 2001 一、2（1.5分）】

3、Aabcd*+- B. abc+*d- C. abc*+d- D. -+*abcd20. 表達式3* 2(4+2*2-6*3)-5求值過程中當掃描到6時，對象棧和算符棧為（ ），其中為乘冪 。A. 3,2,4,1,1；(*(+*- B. 3,2,8；(*- C. 3,2,4,2,2；(*(- D. 3,2,8；(*(-【青島大學 2000 五、5（2分）】21. 設計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu) B. 隊列 C. 線性表的鏈式存儲結(jié)構(gòu) D. ?！疚靼搽娮涌萍即髮W 1996 一、6（2分）】22. 用鏈接方式存儲的隊列，在進行刪除運

4、算時（ ）?！颈狈浇煌ù髮W 2001 一、12（2分）】A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改23. 用不帶頭結(jié)點的單鏈表存儲隊列時,其隊頭指針指向隊頭結(jié)點,其隊尾指針指向隊尾結(jié)點，則在進行刪除操作時( )。【北京理工大學 2001 六、3（2分）】A僅修改隊頭指針 B. 僅修改隊尾指針 C. 隊頭、隊尾指針都要修改 D. 隊頭,隊尾指針都可能要修改24. 遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)。A隊列 B多維數(shù)組 C棧 D. 線性表【福州大學 1998 一、1（2分）】25. 假設以數(shù)組Am存放循環(huán)隊列的

5、元素,其頭尾指針分別為front和rear，則當前隊列中的元素個數(shù)為（ ）?！颈本┕ど檀髮W 2001 一、2（3分）】A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m26. 循環(huán)隊列A0.m-1存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數(shù)是( )。【南京理工大學 2001 一、5（1.5分）】A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front27. 循環(huán)隊列存儲在數(shù)組A0.m中，則入隊時的操作為（ ）。

6、【中山大學 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. 若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？( )【浙江大學1999 四、1(4分)】A. 1和 5 B. 2和4 C. 4和2 D. 5和1 29. 已知輸入序列為abcd 經(jīng)過輸出受限的雙向隊列后能得到的輸出序列有（ ）。 A. dacb B. cadb

7、 C. dbca D. bdac E. 以上答案都不對 【西安交通大學 1996 三、3 (3分)】30. 若以1234作為雙端隊列的輸入序列，則既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列是( )。【西安電子科技大學 1996 一、5（2分）】A. 1234 B. 4132 C. 4231 D. 4213 31. 最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是 （ ）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front【南京理工大學

8、1999 一、16（2分）】32. 棧和隊列的共同點是（ ）?！狙嗌酱髮W 2001 一、1（2分）】A. 都是先進先出 B. 都是先進后出 C. 只允許在端點處插入和刪除元素 D. 沒有共同點33. 棧的特點是（ 先進后出 ）,隊列的特點是（ 先進先出 ）,棧和隊列都是（ ）。若進棧序列為1,2,3,4 則（ ）不可能是一個出棧序列（不一定全部進棧后再出棧）；若進隊列的序列為1,2,3,4 則（ ）是一個出隊列序列?！颈狈浇煌ù髮W 1999 一、1（5分）】, : A. 先進先出 B. 后進先出 C. 進優(yōu)于出 D. 出優(yōu)于進: A.順序存儲的線性結(jié)構(gòu) B.鏈式存儲的線性結(jié)構(gòu) C.限制存取點的

9、線性結(jié)構(gòu) D.限制存取點的非線性結(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,434. 棧和隊都是（ ）【南京理工大學 1997 一、3（2分）】A順序存儲的線性結(jié)構(gòu) B. 鏈式存儲的非線性結(jié)構(gòu)C. 限制存取點的線性結(jié)構(gòu) D. 限制存取點的非線性結(jié)構(gòu)35. 設棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，e3，e4,e5和e6依次通過棧S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e2，e4，e3,e6,e5,e1則棧S的容量至少應該是( )。A 6 B. 4 C. 3 D. 2【南京理工大學 2

10、000 一、6（1.5分）】36. 用單鏈表表示的鏈式隊列的隊頭在鏈表的（ ）位置?！厩迦A大學 1998 一、1（2分）】A鏈頭 B鏈尾 C鏈中37. 依次讀入數(shù)據(jù)元素序列a，b，c，d，e，f，g進棧,每進一個元素，機器可要求下一個元素進棧或彈棧，如此進行，則棧空時彈出的元素構(gòu)成的序列是以下哪些序列？【哈爾濱工業(yè)大學 2000 七（8分）】Ad ，e，c，f，b，g，a B. f，e，g，d，a，c，bC. e，f，d，g，b，c，a D. c，d，b，e，f，a，g二 判斷題1. 消除遞歸不一定需要使用棧，此說法（ T ）【中科院計算所 1998 二、2（2分）】【中國科技大學 1998

11、二、2（2分）】2. 棧是實現(xiàn)過程和函數(shù)等子程序所必需的結(jié)構(gòu)。（ T ）【合肥工業(yè)大學 2000 二、2（1分）】3. 兩個棧共用靜態(tài)存儲空間，對頭使用也存在空間溢出問題。（ T ）【青島大學 2000 四、2（1分）】4兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內(nèi)存空間的兩端。（ T ）【上海海運學院 1998 一、4（1分）】5. 即使對不含相同元素的同一輸入序列進行兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（ F ）【北京郵電大學 1999 二、4（2分）】6. 有n個數(shù)順序（依次）進棧，出棧序列有Cn種，Cn=1/（n

12、+1）*（2n）!/(n!)*(n!)。（ T ）【北京郵電大學 1998 一、3（2分）】7. 棧與隊列是一種特殊操作的線性表。（ T ）【青島大學 2001 四、3 （1分）】8. 若輸入序列為1,2,3,4,5,6,則通過一個棧可以輸出序列3,2,5,6,4,1. （ T ）【上海海運學院1995 一、2（1分） 1997 一、3（1分）】9. 棧和隊列都是限制存取點的線性結(jié)構(gòu)。（ T ）【中科院軟件所 1999 六、(5)（2分）】10若輸入序列為1，2，3，4，5，6，則通過一個?？梢暂敵鲂蛄?，5，4，6，2，3。（ F ）【上海海運學院 1999 一、3（1分）】11. 任何一個

13、遞歸過程都可以轉(zhuǎn)換成非遞歸過程。（T）【上海交通大學 1998一、3（1分）】12. 只有那種使用了局部變量的遞歸過程在轉(zhuǎn)換成非遞歸過程時才必須使用棧。（F）【上海交通大學 1998 一、4（1分）】13. 隊列是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結(jié)構(gòu)。（ F ）【上海海運學院 1998 一、3（1分）】14. 通常使用隊列來處理函數(shù)或過程的調(diào)用。（ F ）【南京航空航天大學 1997 一、5（1分）】15. 隊列邏輯上是一個下端和上端既能增加又能減少的線性表。（ T ）【上海交通大學 1998 一、2】16. 循環(huán)隊列通常用指針來實現(xiàn)隊列的頭尾相接。（ F ）【南

14、京航空航天大學 1996 六、1（1分）】17. 循環(huán)隊列也存在空間溢出問題。（ ）【青島大學 2002 一、2 （1分）】18. 隊列和棧都是運算受限的線性表，只允許在表的兩端進行運算。（ F）【長沙鐵道學院1997一、5(1分)】19. 棧和隊列都是線性表，只是在插入和刪除時受到了一些限制。（ T ）【北京郵電大學2002一、3(1分)】20. 棧和隊列的存儲方式，既可以是順序方式，又可以是鏈式方式。（ T ）【上海海運學院 1996 一、2（1分） 1999 一、2（1分）】三 填空題 1棧是_操作受限_的線性表，其運算遵循_后進先出_的原則。【北京科技大學 1997 一、3】2_棧_是

15、限定僅在表尾進行插入或刪除操作的線性表?！狙嗌酱髮W 1998 一、3 （1分）】3. 一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是_3 1 2_?！局袊嗣翊髮W2001一、1(2分)】4. 設有一個空棧，棧頂指針為1000H(十六進制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是_2 3_，而棧頂指針值是_100CH _H。設棧為順序棧，每個元素占4個字節(jié)?！疚靼搽娮涌萍即髮W 1998 二、1（4分）】5. 當兩個棧共享一存儲區(qū)時，棧利用一維數(shù)組stack(1,n)表示，兩棧頂指針為top1與top2，則當棧1

16、空時，top1為_0_，棧2空時 ，top2為_n+1_，棧滿時為_ top1+1=top2【南京理工大學 1997 三、1（3分）】6兩個棧共享空間時棧滿的條件_兩棧頂指針相鄰_?！局猩酱髮W 1998 一、3（1分）】7在作進棧運算時應先判別棧是否_(1)_滿;在作退棧運算時應先判別棧是否_(2)空_；當棧中元素為n個，作進棧運算時發(fā)生上溢，則說明該棧的最大容量為_(3)n_。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的空間時，應將兩棧的_(4)棧底_分別設在內(nèi)存空間的兩端，這樣只有當_(5) 兩棧頂指針相鄰_時才產(chǎn)生溢出?！旧綎|工業(yè)大學 1994 一、1（5分）】8.

17、 多個棧共存時，最好用_鏈式存儲結(jié)構(gòu)_作為存儲結(jié)構(gòu)?！灸暇├砉ご髮W 2001 二、7（2分）】SSSS9用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應的S和X的操作串為_ SSSS _?！疚髂辖煌ù髮W 2000 一、5】10. 順序棧用data1.n存儲數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作是_ data+top=x；_?！竞戏使I(yè)大學 2001 三、2 （2分）】11表達式23+(12*3-2)/4+34*5/7)+108/9的后綴表達式是_?！局猩酱髮W 1998 一、4（1分）】12. 循環(huán)隊列的引入，目的是為了克服_假溢出時大量移動

18、數(shù)據(jù)元素。_?！緩B門大學 2001 一、1 （14/8分）】 13用下標0開始的N元數(shù)組實現(xiàn)循環(huán)隊列時，為實現(xiàn)下標變量M加1后在數(shù)組有效下標范圍內(nèi)循環(huán)，可采用的表達式是：M：=_（填PASCAL語言，C語言的考生不填）； M= _(M+1) MOD N _（填C語言，PASCAL語言的考生不填）?！疚髂辖煌ù髮W 2000 一、7】14隊列_又稱作先進先出表。【重慶大學 2000 一、7】15. 隊列的特點是_先進先出_?！颈本├砉ご髮W 2000 二、2（2分）】16隊列是限制插入只能在表的一端，而刪除在表的另一端進行的線性表，其特點是_先進先出_。【北方交通大學 2001 二、5】17. 已知

19、鏈隊列的頭尾指針分別是f和r，則將值x入隊的操作序列是_ 17、s=(LinkedList)malloc(sizeof(LNode)； s-data=x;s-next=r-next；r-next=s；r=s；_?！竞戏使I(yè)大學 2000 三、3（2分）】18區(qū)分循環(huán)隊列的滿與空，只有兩種方法，它們是_犧牲一個存儲單元 設標記_和_?！颈本┼]電大學2001 二、2（4分）】19設循環(huán)隊列用數(shù)組A1.M表示，隊首、隊尾指針分別是FRONT和TAIL，判定隊滿的條件為_（TAIL+1）MOD M=FRONT _ 。【山東工業(yè)大學 1995 一、1（1分）】20. 設循環(huán)隊列存放在向量sq.data0

20、:M中，則隊頭指針sq.front在循環(huán)意義下的出隊操作可表示為_，若用犧牲一個單元的辦法來區(qū)分隊滿和隊空（設隊尾指針sq.rear）,則隊滿的條件為_?！鹃L沙鐵道學院 1997 二、4 (4分)】21表達式求值是_應用的一個典型例子?！局貞c大學 2000 一、10】22循環(huán)隊列用數(shù)組A0.m-1存放其元素值，已知其頭尾指針分別是front和rear ，則當前隊列的元素個數(shù)是_。【廈門大學 2000 六、1（16%/3分）】23設Q0.N-1為循環(huán)隊列，其頭、尾指針分別為P和R，則隊Q中當前所含元素個數(shù)為_?！颈本┛萍即髮W 1997 一、4】24完善下面算法?！局猩酱髮W 1998 四、2（6分

21、）】后綴表達式求值，表達式13/25+61的后綴表達式格式為： 13, 25/61, +FUNC compute(a):real; 后綴表達式存儲在數(shù)組a1.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:=p

22、op(s)/x;ENDCASEpush(s,x)；i:=i+1；ch:=ai；END;comput:= (3)_；END;25. 算術(shù)表達式求值的流程，其中OPTR為算術(shù)符棧，OPND為操作數(shù)棧，precede(oper1，oper2)是比較運算符優(yōu)先級別的函數(shù)，operate(opnd1,oper,opnd2)為兩操作數(shù)的運算結(jié)果函數(shù)。（#表示運算起始和終止符號）【西北工業(yè)大學 1999 六、2 (7分)】 FUNCTION exp_reduced:operandtype; INITSTACK(OPTR);PUSH(OPTR#)；INITSTACK(OPND);read(w)； WHILE

23、NOT(w=#) AND (GETTOP(OPTR)=#) DO IF NOT w in op THEN PUSH(OPND,w); ELSE CASE precede(GETTOP(OPTR),w)OF :theta:=POP(OPTR);b:=POP(OPND);a:=POP(OPND);(3)_； ENDC;RETURN(GETTOP(OPND);ENDF; 26根據(jù)需要，用適當?shù)恼Z句填入下面算法的_中：問題：設有n件物品，重量分別為w1,w2,w3,wn和一個能裝載總重量為T的背包。能否從n件物品中選擇若干件恰好使它們的重量之和等于T。若能，則背包問題有解，否則無解。解此問題的算法如下

24、： FUNCTION kanp_stack(VAR stack,w:ARRAY1.n OF real; VAR top:integer; T:real):boolean; w1：n 存放n件物品的重量，依次從中取出物品放入背包中，檢查背包重量，若不超過T，則裝入，否則棄之，取下一個物品試之。若有解則返回函數(shù)值true,否則返回falseBEGIN top:=0; i:=1; i指示待選物品 WHILE (1)_ AND(2)_DO IF (3)_ OR (4)_ AND (i0) THEN i:=(7)_;取出棧頂物品 top:= (8)_ ；T:= (9)_ ; 恢復T值 i:=i+1 準備

25、挑選下一件物品 ; ; RETURN(10)_) 背包無解END;【北京郵電大學 1996 四（10分）】四 應用題1. 名詞解釋：棧。【燕山大學 1999 一、1（2分）】【吉林工業(yè)大學 1999 一、3（2分）】2. 名詞解釋：隊列【大連海事大學 1996 一、6 ( 1分 )】3. 什么是循環(huán)隊列？【哈爾濱工業(yè)大學 2001 三、2（3分）】【河南大學 1998 一、4（3分）】4. 假設以S和X分別表示入棧和出棧操作，則對初態(tài)和終態(tài)均為空的棧操作可由S和X組成的序列表示（如SXSX）。（1）試指出判別給定序列是否合法的一般規(guī)則。（2）兩個不同合法序列（對同一輸入序列）能否得到相同的輸出

26、元素序列？如能得到，請舉列說明?！緰|南大學 1992 二（10分）】5. 有5 個元素，其入棧次序為：A，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個且D第二個出棧）的次序有哪幾個？【西南交通大學 2000 二、1】6. 如果輸入序列為1 2 3 4 5 6,試問能否通過棧結(jié)構(gòu)得到以下兩個序列:4 3 5 6 1 2和1 3 5 4 2 6;請說明為什么不能或如何才能得到。【武漢交通科技大學 1996 二、3 (3分)】7. 若元素的進棧序列為：A、B、C、D、E，運用棧操作，能否得到出棧序列B、C、A、E、D和D、B、A、C、E？為什么？【北京科技大學 1998

27、一、2】8. 設輸入序列為a,b,c,d,試寫出借助一個棧可得到的兩個輸出序列和兩個不能得到的輸出序列?！颈本┛萍即髮W 2001 一、4（2分）】9. 設輸入序列為2，3，4，5，6，利用一個棧能得到序列2，5，3，4，6嗎？?？梢杂脝捂湵韺崿F(xiàn)嗎？【山東師范大學 1996 五、4（2分）】10. 試證明：若借助棧由輸入序列1,2,n得到輸出序列為P1,P2,Pn（它是輸入序列的一個排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著ijk,使PjPk0 THEN BEGIN p(w-1); writeln(w);輸出W p(w-1）END； END；【西北大學 2001 三、7】17. 用一個數(shù)

28、組S（設大小為MAX）作為兩個堆棧的共享空間。請說明共享方法，棧滿/?？盏呐袛鄺l件，并用C或PASCAL設計公用的入棧操作push（i，x），其中i為0或1，用于表示棧號，x為入棧值?！菊憬髮W 1998 五、2 (7分)】18. 簡述下列程序段的功能。PROC algo(VAR S : stack; k:integer);VAR T: stack; temp: integer; WHILE NOT empty(S) DO temp:=POP(S); IF tempk THEN PUSH(T,temp); WHILE NOT empty(T) DO temp:=POP(T);PUSH(S,te

29、mp);【山東科技大學 2002 一、1（4分）】19. 用棧實現(xiàn)將中綴表達式8-(3+5)*(5-6/2)轉(zhuǎn)換成后綴表達式，畫出棧的變化過程圖?！灸暇┖娇蘸教齑髮W 2001 五 （10分）】20. 在表達式中，有的運算符要求從右到左計算，如A*B*C的計算次序應為(A*(B*C)，這在由中綴生成后綴的算法中是怎樣實現(xiàn)的?(以*為例說明)【東南大學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

30、)+x END；END； 設初值n=4，讀入 x=4,9,6,2 問：(1) 若x為局部變量時；該函數(shù)遞歸結(jié)束后返回調(diào)用程序的sum=? 并畫出在遞歸過程中棧狀態(tài)的變化過程； (2) 若x為全程變量遞歸結(jié)束時返回調(diào)用程序的sum=?【北京郵電大學 1997 一 （10分）】 22. 畫出對算術(shù)表達式A-B*C/D-EF求值時操作數(shù)棧和運算符棧的變化過程?！緰|南大學2000一、3（6分）】23. 計算算術(shù)表達式的值時，可用兩個棧作輔助工具。對于給出的一個表達式，從左向右掃描它的字符，并將操作數(shù)放入棧S1中，運算符放入棧S2中，但每次掃描到運算符時，要把它同S2的棧頂運算符進行優(yōu)先級比較，當掃描到

31、的運算符的優(yōu)先級不高于棧頂運算符的優(yōu)先級時，取出棧S1的棧頂和次棧頂?shù)膬蓚€元素，以及棧S2的棧頂運算符進行運算將結(jié)果放入棧S1中（得到的結(jié)果依次用T1、T2等表示）。為方便比較，假設棧S2的初始棧頂為（運算符的優(yōu)先級低于加、減、乘、除中任何一種運算）?，F(xiàn)假設要計算表達式： A-B*C/D+E/F。寫出棧S1和S2的變化過程?！旧綎|科技大學 2001 一、4 （7分）】24. 有字符串次序為3*-y-a/y2,利用棧，給出將次序改為3y-*ay2/-的操作步驟。（可用X代表掃描該字符串過程中順序取一個字符進棧的操作，用S代表從棧中取出一個字符加入到新字符串尾的出棧操作。例如，ABC變?yōu)锽CA的操

32、作步驟為XXSXSS）【東北大學 2001 一、4 ( 4分)】25. 內(nèi)存中一片連續(xù)空間（不妨假設地址從1到m）提供給兩個棧S1和S2使用，怎樣分配這部分存儲空間，使得對任一個棧，僅當這部分空間全滿時才發(fā)生上溢?！緰|北大學 2000 一、1 (3分)】26. 將兩個棧存入數(shù)組V1.m應如何安排最好？這時棧空、棧滿的條件是什么？【東南大學1998一、5】27. 在一個算法中需要建立多個堆棧時可以選用下列三種方案之一，試問：這三種方案之間相比較各有什么優(yōu)缺點？（1）分別用多個順序存儲空間建立多個獨立的堆棧；（2）多個堆棧共享一個順序存儲空間；（3）分別建立多個獨立的鏈接堆棧?！颈本┖娇蘸教齑髮W

33、1998 一、6（4分）】28在某程序中，有兩個棧共享一個一維數(shù)組空間SPACEN、SPACE0、SPACEN-1 分別是兩個棧的棧底。（1）對棧1、棧2，試分別寫出（元素x）入棧的主要語句和出棧的主要語句。（2）對棧1、棧2，試分別寫出棧滿、?？盏臈l件?！颈本├砉ご髮W 1999 二、2（8分）】29. 簡述順序存儲隊列的假溢出的避免方法及隊列滿和空的條件?！旧綎|大學 2000 一、2 (4分)】30. 舉例說明順序隊的“假溢出”現(xiàn)象，并給出解決方案?！靖Ｖ荽髮W 1998 三、5 (6分)】31. 怎樣判定循環(huán)隊列的空和滿？【燕山大學 1999 二、3（4分）】32. 簡要敘述循環(huán)隊列的數(shù)據(jù)結(jié)

34、構(gòu)，并寫出其初始狀態(tài)、隊列空、隊列滿時的隊首指針與隊尾指針的值。 【南京航空航天大學 1995 七（5分）】33. 利用兩個棧sl,s2模擬一個隊列時，如何用棧的運算實現(xiàn)隊列的插入，刪除以及判隊空運算。請簡述這些運算的算法思想。【北京郵電大學 1992 一、1】【東南大學 1999 一、1 （7分）】34一個循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)描述如下：TYPE sequeuetp=RECORD elem：ARRAY1.MAXSIZE OF elemtp； front，rear：0.MAXSIZE； END；給出循環(huán)隊列的隊空和隊滿的判斷條件，并且分析一下該條件對隊列實際存儲空間大小的影響，如果為了不損失存儲空

35、間，你如何改進循環(huán)隊列的隊空和隊滿的判斷條件？【西北工業(yè)大學 1999 三 (8分)】35. 如果用一個循環(huán)數(shù)組q0.m-1表示隊列時，該隊列只有一個隊列頭指針front，不設隊列尾指針rear，而改置計數(shù)器count用以記錄隊列中結(jié)點的個數(shù)。（1）編寫實現(xiàn)隊列的三個基本運算：判空、入隊、出隊（3分）（2）隊列中能容納元素的最多個數(shù)是多少？（1分）【東北大學 2002 一、1】36. 給出循環(huán)隊列中元素個數(shù)的計算式(設隊最大長度為N,隊首指針FRONT，隊尾指針REAR) 【西北大學 2000 二、7 (5分)】37. 順序隊列一般應該組織成為環(huán)狀隊列的形式，而且一般隊列頭或尾其中之一應該特殊

36、處理。例如，隊列為listarray0.n-1，隊列頭指針為 front，隊列尾指針為 rear， 則listarray rear表示下一個可以插入隊列的位置。請解釋其原因?！颈本┐髮W 1999 一、3 （20/3分）】38. 設一個雙端隊列，元素進入該隊列的次序為a，b，c，d。求既不能由輸入受限的雙端隊列得到,又不能由輸出受限的雙端隊列得到的輸出序列?！局猩酱髮W 1999 一、4 （3分）】39. 若以1、2、3、4作為雙端隊列的輸入序列，試分別求出以下條件的輸出序列：（1）能由輸入受限的雙端隊列得到，但不能由輸出受限的雙端隊列得到的輸出序列；（2）能由輸出受限的雙端隊列得到，但不能由輸入

37、受限的雙端隊列得到的輸出序列；（3）既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列?！旧綎|科技大學 2001 一、3 （6分）】40. 假設以數(shù)組sq0.7存放循環(huán)隊列元素,變量f指向隊頭元素的前一位置,變量r指向隊尾元素，如用A和D分別表示入隊和出隊操作，請給出：（1） 隊空的初始條件;（2） 執(zhí)行操作序列A3D1A5D2A1D2A4時的狀態(tài),并作必要的說明?！颈狈浇煌ù髮W 1993 四（12分）】41、設輸入元素為1、2、3、P和A，輸入次序為123PA，如圖（編者略）。元素經(jīng)過棧后達輸出序列，當所有元素均到達輸出序列后，有哪些序列可以作為高級語言的變量名?！局猩?/p>

38、大學 1997】五 算法設計題1. 設有兩個棧S1,S2都采用順序棧方式，并且共享一個存儲區(qū)O.maxsize-1,為了盡量利用空間，減少溢出的可能，可采用棧頂相向，迎面增長的存儲方式。試設計S1,S2有關(guān)入棧和出棧的操作算法?！竟枮I工業(yè)大學 2001 七 （12分）】2. 設從鍵盤輸入一整數(shù)的序列：a1, a2, a3，an,試編寫算法實現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當ai-1時，將ai進棧；當ai=-1時，輸出棧頂整數(shù)并出棧。算法應對異常情況（入棧滿等）給出相應的信息?！灸暇┖娇蘸教齑髮W 1998 六 （10分）】3. 設表達式以字符形式已存入數(shù)組En中，#為表達式的結(jié)束符，試寫出判斷表達

39、式中括號（和）是否配對的C語言描述算法：EXYX(E); (注：算法中可調(diào)用棧操作的基本算法。) 【北京科技大學 2001 九、1 （10分）】4. 從鍵盤上輸入一個逆波蘭表達式，用偽碼寫出其求值程序。規(guī)定：逆波蘭表達式的長度不超過一行，以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔,操作符只可能有+、-、*、/四種運算。例如：234 34+2*$【山東師范大學 1999 七 （10分）】5. 假設以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。 （1）下面所示的序列中哪些是合法的？ A. IOII

40、OIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO （2）通過對（1）的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）?！疚錆h大學 2000 五、2】6.設計一個算法，判斷一個算術(shù)表達式中的括號是否配對。算術(shù)表達式保存在帶頭結(jié)點的單循環(huán)鏈表中，每個結(jié)點有兩個域：ch和link，其中ch域為字符類型?！灸暇┼]電大學 2000五】7. 請利用兩個棧S1和S2來模擬一個隊列。已知棧的三個運算定義如下：PUSH(ST,x):元素x入ST棧；POP(ST,x)：ST棧頂元素出棧，賦給變量x；S

41、empty(ST)：判ST棧是否為空。那么如何利用棧的運算來實現(xiàn)該隊列的三個運算：enqueue:插入一個元素入隊列； dequeue:刪除一個元素出隊列；queue_empty：判隊列為空。（請寫明算法的思想及必要的注釋）【西安電子科技大學2001軟件五(10分)】【上海交通大學1999 二(12分)】【河海大學1998 三(12分)】類似本題的另外敘述有：（1）有兩個長度相同的棧S1,S2，已知以下入棧、出棧、判棧滿和判?？詹僮鳎篜ROCEDURE push(Stack:Stacktype;x:Datatype);FUNCTION Pop(Stack:Stacktype ):Datatyp

42、e;FUNCTION Full (Stack:Stacktype):Boolean;FUNCTION Empty(Stack:Stacktype)Boolean;現(xiàn)用此二棧構(gòu)成一個隊列，試寫出下面入隊列、出隊列操作算法：PROCEDURE EnQueue(x:Datatype);FUNCTION DeQueue: Datatype;【北京郵電大學 2000 六（10分）】8. 設結(jié)點結(jié)構(gòu)為(data,link)，試用一個全局指針p和某種鏈接結(jié)構(gòu)實現(xiàn)一個隊列,畫出示意圖,并給出入隊addq和出隊deleteq過程,要求它們的時間復雜性都是O(l)（不計new和dispose時間）【東南大學 1996 二 （10分）】9. 假設以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾結(jié)點，但不設頭指針，如圖所示（編者略），請寫出相應的入隊列和出隊列算法?！疚靼搽娮涌萍即髮W 1999計應用 六 （10分）】10. 如果允許在循環(huán)隊列的兩端