數(shù)據(jù)結(jié)構(gòu)-第3章--棧和隊(duì)列練習(xí)題

1、精品好資料學(xué)習(xí)推薦第3章 棧和隊(duì)列一 選擇題1. 對(duì)于棧操作數(shù)據(jù)的原則是（ ）。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ā)生上溢,則說(shuō)明該棧的最大容量為( )。為了增加內(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.

2、 棧底: A. 兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn).B. 其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn). C. 兩個(gè)棧的棧頂在棧空間的某一位置相遇. D. 兩個(gè)棧均不空,且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底.3. 一個(gè)棧的輸入序列為123n，若輸出序列的第一個(gè)元素是n，輸出第i（1=i0) ? x* f(x-1):2); int i ; i =f(f(1);A2 B. 4 C. 8 D. 無(wú)限遞歸19. 表達(dá)式a*(b+c)-d的后綴表達(dá)式是( )。Aabcd*+- B. abc+*d- C. abc*+d- D. -+*abcd20. 表達(dá)式3* 2(4+2*2-6*3)-5求值過(guò)程中當(dāng)掃描到6時(shí)，對(duì)象棧

3、和算符棧為（ ），其中為乘冪 。A. 3,2,4,1,1；(*(+*- B. 3,2,8；(*- C. 3,2,4,2,2；(*(- D. 3,2,8；(*(-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. 棧22. 用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（ ）。A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改23. 用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)( )。A僅修改隊(duì)頭指針 B.

4、僅修改隊(duì)尾指針 C. 隊(duì)頭、隊(duì)尾指針都要修改 D. 隊(duì)頭,隊(duì)尾指針都可能要修改24. 遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)。A隊(duì)列 B多維數(shù)組 C棧 D. 線性表25. 假設(shè)以數(shù)組Am存放循環(huán)隊(duì)列的元素,其頭尾指針?lè)謩e為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m26. 循環(huán)隊(duì)列A0.m-1存放其元素值，用front和rear分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素?cái)?shù)是( )。A. (rear-front+m)%m B. r

5、ear-front+1 C. rear-front-1 D. rear-front27. 循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A0.m中，則入隊(duì)時(shí)的操作為（ ）。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ù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？( )A. 1和 5 B. 2和4 C. 4和2 D. 5和1 29. 已知輸入序列為abcd 經(jīng)過(guò)輸出受限

6、的雙向隊(duì)列后能得到的輸出序列有（ ）。 A. dacb B. cadb C. dbca D. bdac E. 以上答案都不對(duì) 30. 若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是( )。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 Crear+1=front D. (rear-l) MOD n=front32. 棧和隊(duì)列的共同點(diǎn)是（ ）。A

7、. 都是先進(jìn)先出 B. 都是先進(jìn)后出 C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒(méi)有共同點(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ì)列序列。, : 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,

8、3,2,434. 棧和隊(duì)都是（ ）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依次通過(guò)棧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. 236. 用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的（ ）位置。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)成的序列是

9、以下哪些序列？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. 消除遞歸不一定需要使用棧，此說(shuō)法（ ）2. 棧是實(shí)現(xiàn)過(guò)程和函數(shù)等子程序所必需的結(jié)構(gòu)。（ ）3. 兩個(gè)棧共用靜態(tài)存儲(chǔ)空間，對(duì)頭使用也存在空間溢出問(wèn)題。（ ）4兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。（ ）5. 即使對(duì)不含相同元素的同一輸入序列進(jìn)行兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（ ）6. 有n個(gè)數(shù)順序（依次）進(jìn)棧，出棧序列有Cn種，Cn=1/（

10、n+1）*（2n）!/(n!)*(n!)。（ ）7. 棧與隊(duì)列是一種特殊操作的線性表。（ ）8. 若輸入序列為1,2,3,4,5,6,則通過(guò)一個(gè)?？梢暂敵鲂蛄?,2,5,6,4,1. （ ）9. 棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。（ ）10若輸入序列為1，2，3，4，5，6，則通過(guò)一個(gè)?？梢暂敵鲂蛄?，5，4，6，2，3。（ ）11. 任何一個(gè)遞歸過(guò)程都可以轉(zhuǎn)換成非遞歸過(guò)程。（）12. 只有那種使用了局部變量的遞歸過(guò)程在轉(zhuǎn)換成非遞歸過(guò)程時(shí)才必須使用棧。（）13. 隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。（ ）14. 通常使用隊(duì)列來(lái)處理函數(shù)或過(guò)程的調(diào)用。（ ）1

11、5. 隊(duì)列邏輯上是一個(gè)下端和上端既能增加又能減少的線性表。（ ）16. 循環(huán)隊(duì)列通常用指針來(lái)實(shí)現(xiàn)隊(duì)列的頭尾相接。（ ）17. 循環(huán)隊(duì)列也存在空間溢出問(wèn)題。（ ）18. 隊(duì)列和棧都是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)行運(yùn)算。（ ）19. 棧和隊(duì)列都是線性表，只是在插入和刪除時(shí)受到了一些限制。（ ）20. 棧和隊(duì)列的存儲(chǔ)方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞健＃?）三 填空題 1棧是_的線性表，其運(yùn)算遵循_的原則。2_是限定僅在表尾進(jìn)行插入或刪除操作的線性表。3. 一個(gè)棧的輸入序列是：1，2，3則不可能的棧輸出序列是_。4. 設(shè)有一個(gè)空棧，棧頂指針為1000H(十六進(jìn)制)，現(xiàn)有輸入序列為1，2

12、，3，4，5，經(jīng)過(guò)PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是_，而棧頂指針值是_H。設(shè)棧為順序棧，每個(gè)元素占4個(gè)字節(jié)。5. 當(dāng)兩個(gè)棧共享一存儲(chǔ)區(qū)時(shí)，棧利用一維數(shù)組stack(1,n)表示，兩棧頂指針為top1與top2，則當(dāng)棧1空時(shí)，top1為_(kāi)，棧2空時(shí) ，top2為_(kāi)，棧滿時(shí)為_(kāi)。6兩個(gè)棧共享空間時(shí)棧滿的條件_。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ā)生上溢，則說(shuō)明該棧的最大容量為_(kāi)(3)_。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的空間時(shí)，應(yīng)將兩棧的_(

13、4)_分別設(shè)在內(nèi)存空間的兩端，這樣只有當(dāng)_(5)_時(shí)才產(chǎn)生溢出。8. 多個(gè)棧共存時(shí)，最好用_作為存儲(chǔ)結(jié)構(gòu)。9用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為_(kāi)。10. 順序棧用data1.n存儲(chǔ)數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作是_。11表達(dá)式23+(12*3-2)/4+34*5/7)+108/9的后綴表達(dá)式是_。12. 循環(huán)隊(duì)列的引入，目的是為了克服_。13用下標(biāo)0開(kāi)始的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語(yǔ)言，C語(yǔ)言的考生不填）； M=

14、_（填C語(yǔ)言，PASCAL語(yǔ)言的考生不填）。14_又稱作先進(jìn)先出表。15. 隊(duì)列的特點(diǎn)是_。16隊(duì)列是限制插入只能在表的一端，而刪除在表的另一端進(jìn)行的線性表，其特點(diǎn)是_。17. 已知鏈隊(duì)列的頭尾指針?lè)謩e是f和r，則將值x入隊(duì)的操作序列是_。18區(qū)分循環(huán)隊(duì)列的滿與空，只有兩種方法，它們是_和_。19設(shè)循環(huán)隊(duì)列用數(shù)組A1.M表示，隊(duì)首、隊(duì)尾指針?lè)謩e是FRONT和TAIL，判定隊(duì)滿的條件為_(kāi)。20. 設(shè)循環(huán)隊(duì)列存放在向量sq.data0:M中，則隊(duì)頭指針sq.front在循環(huán)意義下的出隊(duì)操作可表示為_(kāi)，若用犧牲一個(gè)單元的辦法來(lái)區(qū)分隊(duì)滿和隊(duì)空（設(shè)隊(duì)尾指針sq.rear）,則隊(duì)滿的條件為_(kāi)。21表達(dá)式求

15、值是_應(yīng)用的一個(gè)典型例子。22循環(huán)隊(duì)列用數(shù)組A0.m-1存放其元素值，已知其頭尾指針?lè)謩e是front和rear ，則當(dāng)前隊(duì)列的元素個(gè)數(shù)是_。23設(shè)Q0.N-1為循環(huán)隊(duì)列，其頭、尾指針?lè)謩e為P和R，則隊(duì)Q中當(dāng)前所含元素個(gè)數(shù)為_(kāi)。24完善下面算法。后綴表達(dá)式求值，表達(dá)式13/25+61的后綴表達(dá)式格式為： 13, 25/61, +FUNC compute(a):real; 后綴表達(dá)式存儲(chǔ)在數(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

16、+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;ENDCASEpush(s,x)；i:=i+1；ch:=ai；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)算起始和終

17、止符號(hào)） 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 :theta:=POP(OPTR);b:=POP(OPND);a:=POP(OPND);(3)_； ENDC;RETURN(GETTOP(OPND);ENDF; 26根據(jù)需要，用適當(dāng)?shù)恼Z(yǔ)句填入下面算

18、法的_中：?jiǎn)栴}：設(shè)有n件物品，重量分別為w1,w2,w3,wn和一個(gè)能裝載總重量為T的背包。能否從n件物品中選擇若干件恰好使它們的重量之和等于T。若能，則背包問(wèn)題有解，否則無(wú)解。解此問(wèn)題的算法如下： FUNCTION kanp_stack(VAR stack,w:ARRAY1.n OF real; VAR top:integer; T:real):boolean; w1：n 存放n件物品的重量，依次從中取出物品放入背包中，檢查背包重量，若不超過(guò)T，則裝入，否則棄之，取下一個(gè)物品試之。若有解則返回函數(shù)值true,否則返回falseBEGIN top:=0; i:=1; i指示待選物品 WHILE

19、 (1)_ AND(2)_DO IF (3)_ OR (4)_ AND (i0) THEN i:=(7)_;取出棧頂物品 top:= (8)_ ；T:= (9)_ ; 恢復(fù)T值 i:=i+1 準(zhǔn)備挑選下一件物品 ; ; RETURN(10)_) 背包無(wú)解END;四 應(yīng)用題1. 名詞解釋：棧。2. 名詞解釋：隊(duì)列3. 什么是循環(huán)隊(duì)列？【4. 假設(shè)以S和X分別表示入棧和出棧操作，則對(duì)初態(tài)和終態(tài)均為空的棧操作可由S和X組成的序列表示（如SXSX）。（1）試指出判別給定序列是否合法的一般規(guī)則。（2）兩個(gè)不同合法序列（對(duì)同一輸入序列）能否得到相同的輸出元素序列？如能得到，請(qǐng)舉列說(shuō)明。5. 有5 個(gè)元素，

20、其入棧次序?yàn)椋篈，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個(gè)且D第二個(gè)出棧）的次序有哪幾個(gè)？6. 如果輸入序列為1 2 3 4 5 6,試問(wèn)能否通過(guò)棧結(jié)構(gòu)得到以下兩個(gè)序列:4 3 5 6 1 2和1 3 5 4 2 6;請(qǐng)說(shuō)明為什么不能或如何才能得到。7. 若元素的進(jìn)棧序列為：A、B、C、D、E，運(yùn)用棧操作，能否得到出棧序列B、C、A、E、D和D、B、A、C、E？為什么？8. 設(shè)輸入序列為a,b,c,d,試寫出借助一個(gè)?？傻玫降膬蓚€(gè)輸出序列和兩個(gè)不能得到的輸出序列。9. 設(shè)輸入序列為2，3，4，5，6，利用一個(gè)棧能得到序列2，5，3，4，6嗎？棧可以用單鏈表實(shí)現(xiàn)嗎

21、？10. 試證明：若借助棧由輸入序列1,2,n得到輸出序列為P1,P2,Pn（它是輸入序列的一個(gè)排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著ijk,使PjPk0 THEN BEGIN p(w-1); writeln(w);輸出W p(w-1）END； END；17. 用一個(gè)數(shù)組S（設(shè)大小為MAX）作為兩個(gè)堆棧的共享空間。請(qǐng)說(shuō)明共享方法，棧滿/?？盏呐袛鄺l件，并用C或PASCAL設(shè)計(jì)公用的入棧操作push（i，x），其中i為0或1，用于表示棧號(hào)，x為入棧值。18. 簡(jiǎn)述下列程序段的功能。PROC algo(VAR S : stack; k:integer);VAR T: stack; te

22、mp: 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,temp);19. 用棧實(shí)現(xiàn)將中綴表達(dá)式8-(3+5)*(5-6/2)轉(zhuǎn)換成后綴表達(dá)式，畫出棧的變化過(guò)程圖。20. 在表達(dá)式中，有的運(yùn)算符要求從右到左計(jì)算，如A*B*C的計(jì)算次序應(yīng)為(A*(B*C)，這在由中綴生成后綴的算法中是怎樣實(shí)現(xiàn)的?(以*為例說(shuō)明)21. 有遞歸算法如下： FUNCTION sum (n:integer):intger;BEGIN IF

23、 n=0 THEN sum:=0 ELSE BEGIN read(x)；sum:=sum(n-1)+x END；END； 設(shè)初值n=4，讀入 x=4,9,6,2 問(wèn)：(1) 若x為局部變量時(shí)；該函數(shù)遞歸結(jié)束后返回調(diào)用程序的sum=? 并畫出在遞歸過(guò)程中棧狀態(tài)的變化過(guò)程； (2) 若x為全程變量遞歸結(jié)束時(shí)返回調(diào)用程序的sum=?22. 畫出對(duì)算術(shù)表達(dá)式A-B*C/D-EF求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過(guò)程。23. 計(jì)算算術(shù)表達(dá)式的值時(shí)，可用兩個(gè)棧作輔助工具。對(duì)于給出的一個(gè)表達(dá)式，從左向右掃描它的字符，并將操作數(shù)放入棧S1中，運(yùn)算符放入棧S2中，但每次掃描到運(yùn)算符時(shí)，要把它同S2的棧頂運(yùn)算符進(jìn)行優(yōu)

24、先級(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的變化過(guò)程。24. 有字符串次序?yàn)?*-y-a/y2,利用棧，給出將次序改為3y-*ay2/-的操作步驟。（可用X代表掃描該字符串過(guò)程中順序取一個(gè)字符進(jìn)棧的操作，用S代表從棧中取出一個(gè)字符加入到新字符串尾的出棧操作。例如，ABC變?yōu)锽CA的操作步驟為XXSXSS）25

25、. 內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m）提供給兩個(gè)棧S1和S2使用，怎樣分配這部分存儲(chǔ)空間，使得對(duì)任一個(gè)棧，僅當(dāng)這部分空間全滿時(shí)才發(fā)生上溢。26. 將兩個(gè)棧存入數(shù)組V1.m應(yīng)如何安排最好？這時(shí)?？?、棧滿的條件是什么？27. 在一個(gè)算法中需要建立多個(gè)堆棧時(shí)可以選用下列三種方案之一，試問(wèn)：這三種方案之間相比較各有什么優(yōu)缺點(diǎn)？（1）分別用多個(gè)順序存儲(chǔ)空間建立多個(gè)獨(dú)立的堆棧；（2）多個(gè)堆棧共享一個(gè)順序存儲(chǔ)空間；（3）分別建立多個(gè)獨(dú)立的鏈接堆棧。28在某程序中，有兩個(gè)棧共享一個(gè)一維數(shù)組空間SPACEN、SPACE0、SPACEN-1 分別是兩個(gè)棧的棧底。（1）對(duì)棧1、棧2，試分別寫出（元素x）入棧

26、的主要語(yǔ)句和出棧的主要語(yǔ)句。（2）對(duì)棧1、棧2，試分別寫出棧滿、?？盏臈l件。29. 簡(jiǎn)述順序存儲(chǔ)隊(duì)列的假溢出的避免方法及隊(duì)列滿和空的條件。30. 舉例說(shuō)明順序隊(duì)的“假溢出”現(xiàn)象，并給出解決方案。31. 怎樣判定循環(huán)隊(duì)列的空和滿？32. 簡(jiǎn)要敘述循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，并寫出其初始狀態(tài)、隊(duì)列空、隊(duì)列滿時(shí)的隊(duì)首指針與隊(duì)尾指針的值。 33. 利用兩個(gè)棧sl,s2模擬一個(gè)隊(duì)列時(shí)，如何用棧的運(yùn)算實(shí)現(xiàn)隊(duì)列的插入，刪除以及判隊(duì)空運(yùn)算。請(qǐng)簡(jiǎn)述這些運(yùn)算的算法思想。34一個(gè)循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)描述如下：TYPE sequeuetp=RECORD elem：ARRAY1.MAXSIZE OF elemtp； front，

27、rear：0.MAXSIZE； END；給出循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿的判斷條件，并且分析一下該條件對(duì)隊(duì)列實(shí)際存儲(chǔ)空間大小的影響，如果為了不損失存儲(chǔ)空間，你如何改進(jìn)循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿的判斷條件？35. 如果用一個(gè)循環(huán)數(shù)組q0.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分）36. 給出循環(huán)隊(duì)列中元素個(gè)數(shù)的計(jì)算式(設(shè)隊(duì)最大長(zhǎng)度為N,隊(duì)首指針FRONT，隊(duì)尾指針REAR) 37. 順序隊(duì)列一般應(yīng)該組織成為環(huán)狀隊(duì)列的形式，

28、而且一般隊(duì)列頭或尾其中之一應(yīng)該特殊處理。例如，隊(duì)列為listarray0.n-1，隊(duì)列頭指針為 front，隊(duì)列尾指針為 rear， 則listarray rear表示下一個(gè)可以插入隊(duì)列的位置。請(qǐng)解釋其原因。38. 設(shè)一個(gè)雙端隊(duì)列，元素進(jìn)入該隊(duì)列的次序?yàn)閍，b，c，d。求既不能由輸入受限的雙端隊(duì)列得到,又不能由輸出受限的雙端隊(duì)列得到的輸出序列。【39. 若以1、2、3、4作為雙端隊(duì)列的輸入序列，試分別求出以下條件的輸出序列：（1）能由輸入受限的雙端隊(duì)列得到，但不能由輸出受限的雙端隊(duì)列得到的輸出序列；（2）能由輸出受限的雙端隊(duì)列得到，但不能由輸入受限的雙端隊(duì)列得到的輸出序列；（3）既不能由輸入受

29、限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列。40. 假設(shè)以數(shù)組sq0.7存放循環(huán)隊(duì)列元素,變量f指向隊(duì)頭元素的前一位置,變量r指向隊(duì)尾元素，如用A和D分別表示入隊(duì)和出隊(duì)操作，請(qǐng)給出：（1） 隊(duì)空的初始條件;（2） 執(zhí)行操作序列A3D1A5D2A1D2A4時(shí)的狀態(tài),并作必要的說(shuō)明。41、設(shè)輸入元素為1、2、3、P和A，輸入次序?yàn)?23PA，如圖（編者略）。元素經(jīng)過(guò)棧后達(dá)輸出序列，當(dāng)所有元素均到達(dá)輸出序列后，有哪些序列可以作為高級(jí)語(yǔ)言的變量名。五 算法設(shè)計(jì)題1. 設(shè)有兩個(gè)棧S1,S2都采用順序棧方式，并且共享一個(gè)存儲(chǔ)區(qū)O.maxsize-1,為了盡量利用空間，減少溢出的可能，可采用

30、棧頂相向，迎面增長(zhǎng)的存儲(chǔ)方式。試設(shè)計(jì)S1,S2有關(guān)入棧和出棧的操作算法。2. 設(shè)從鍵盤輸入一整數(shù)的序列：a1, a2, a3，an,試編寫算法實(shí)現(xiàn)：用棧結(jié)構(gòu)存儲(chǔ)輸入的整數(shù)，當(dāng)ai-1時(shí)，將ai進(jìn)棧；當(dāng)ai=-1時(shí)，輸出棧頂整數(shù)并出棧。算法應(yīng)對(duì)異常情況（入棧滿等）給出相應(yīng)的信息。3. 設(shè)表達(dá)式以字符形式已存入數(shù)組En中，#為表達(dá)式的結(jié)束符，試寫出判斷表達(dá)式中括號(hào)（和）是否配對(duì)的C語(yǔ)言描述算法：EXYX(E); (注：算法中可調(diào)用棧操作的基本算法。) 4. 從鍵盤上輸入一個(gè)逆波蘭表達(dá)式，用偽碼寫出其求值程序。規(guī)定：逆波蘭表達(dá)式的長(zhǎng)度不超過(guò)一行，以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔,操作符只可能

31、有+、-、*、/四種運(yùn)算。例如：234 34+2*$5. 假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。 （1）下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO （2）通過(guò)對(duì)（1）的分析，寫出一個(gè)算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。6.設(shè)計(jì)一個(gè)算法，判斷一個(gè)算術(shù)表達(dá)式中的括號(hào)是否配對(duì)。算術(shù)表達(dá)式保存在帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，每個(gè)結(jié)點(diǎn)

32、有兩個(gè)域：ch和link，其中ch域?yàn)樽址愋汀?. 請(qǐng)利用兩個(gè)棧S1和S2來(lái)模擬一個(gè)隊(duì)列。已知棧的三個(gè)運(yùn)算定義如下：PUSH(ST,x):元素x入ST棧；POP(ST,x)：ST棧頂元素出棧，賦給變量x；Sempty(ST)：判ST棧是否為空。那么如何利用棧的運(yùn)算來(lái)實(shí)現(xiàn)該隊(duì)列的三個(gè)運(yùn)算：enqueue:插入一個(gè)元素入隊(duì)列； dequeue:刪除一個(gè)元素出隊(duì)列；queue_empty：判隊(duì)列為空。（請(qǐng)寫明算法的思想及必要的注釋）三(12分)】類似本題的另外敘述有：（1）有兩個(gè)長(zhǎng)度相同的棧S1,S2，已知以下入棧、出棧、判棧滿和判?？詹僮鳎篜ROCEDURE push(Stack:Stackty

33、pe;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和

34、出隊(duì)deleteq過(guò)程,要求它們的時(shí)間復(fù)雜性都是O(l)（不計(jì)new和dispose時(shí)間）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)過(guò)程?！?/p>

35、山東科技大學(xué) 2002 一、2 （6分）】12. 雙端隊(duì)列（duque）是一個(gè)可以在任一端進(jìn)行插入和刪除的線性表。現(xiàn)采用一個(gè)一維數(shù)組作為雙端隊(duì)列的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，使用類PASCAL語(yǔ)言描述如下：CONST maxsize=32; 數(shù)組中可容納的元素個(gè)數(shù)TYPE duque=RECORD elem: ARRAY0.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端操作。13. 一個(gè)雙端隊(duì)列deque是限定在兩端end1，end2都可進(jìn)行插入和刪除的線性表。隊(duì)空條件是end1=end2。若用順序方式來(lái)組織雙端