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

1、精品好資料學(xué)習(xí)推薦第3章 棧和隊(duì)列一 選擇題1. 對于棧操作數(shù)據(jù)的原則是（ ）。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-1 B. n C. n+1 D. n/2 : A. 長度 B. 深度 C. 棧頂 D.

2、 棧底: A. 兩個棧的棧頂同時到達(dá)?？臻g的中心點(diǎn).B. 其中一個棧的棧頂?shù)竭_(dá)棧空間的中心點(diǎn). C. 兩個棧的棧頂在?？臻g的某一位置相遇. D. 兩個棧均不空,且一個棧的棧頂?shù)竭_(dá)另一個棧的棧底.3. 一個棧的輸入序列為123n，若輸出序列的第一個元素是n，輸出第i（1=i0) ? x* f(x-1):2); int i ; i =f(f(1);A2 B. 4 C. 8 D. 無限遞歸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求值過程中當(dāng)掃描到6時，對象棧

3、和算符棧為（ ），其中為乘冪 。A. 3,2,4,1,1；(*(+*- B. 3,2,8；(*- C. 3,2,4,2,2；(*(- D. 3,2,8；(*(-21. 設(shè)計(jì)一個判別表達(dá)式中左，右括號是否配對出現(xiàn)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu) B. 隊(duì)列 C. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) D. 棧22. 用鏈接方式存儲的隊(duì)列，在進(jìn)行刪除運(yùn)算時（ ）。A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改23. 用不帶頭結(jié)點(diǎn)的單鏈表存儲隊(duì)列時,其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時( )。A僅修改隊(duì)頭指針 B.

4、僅修改隊(duì)尾指針 C. 隊(duì)頭、隊(duì)尾指針都要修改 D. 隊(duì)頭,隊(duì)尾指針都可能要修改24. 遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)。A隊(duì)列 B多維數(shù)組 C棧 D. 線性表25. 假設(shè)以數(shù)組Am存放循環(huán)隊(duì)列的元素,其頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個數(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ì)列存儲在數(shù)組A0.m中，則入隊(duì)時的操作為（ ）。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ù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？( )A. 1和 5 B. 2和4 C. 4和2 D. 5和1 29. 已知輸入序列為abcd 經(jīng)過輸出受限

6、的雙向隊(duì)列后能得到的輸出序列有（ ）。 A. dacb B. cadb C. dbca D. bdac E. 以上答案都不對 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. 沒有共同點(diǎn)33. 棧的特點(diǎn)是（ ）,隊(duì)列的特點(diǎn)是（ ）,棧和隊(duì)列都是（ ）。若進(jìn)棧序列為1,2,3,4 則（ ）不可能是一個出棧序列（不一定全部進(jìn)棧后再出棧）；若進(jìn)隊(duì)列的序列為1,2,3,4 則（ ）是一個出隊(duì)列序列。, : 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,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順序存儲的線性結(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)為空，元素e1，e2，e3，e4,e5和e6依次通過棧S，一個元素出棧后即進(jìn)隊(duì)列Q，若6個元素出隊(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)一個元素，機(jī)器可要求下一個元素進(jìn)?；驈棗?，如此進(jìn)行，則?？諘r彈出的元素構(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. 消除遞歸不一定需要使用棧，此說法（ ）2. 棧是實(shí)現(xiàn)過程和函數(shù)等子程序所必需的結(jié)構(gòu)。（ ）3. 兩個棧共用靜態(tài)存儲空間，對頭使用也存在空間溢出問題。（ ）4兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機(jī)會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。（ ）5. 即使對不含相同元素的同一輸入序列進(jìn)行兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（ ）6. 有n個數(shù)順序（依次）進(jìn)棧，出棧序列有Cn種，Cn=1/（

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

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

12、，3，4，5，經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是_，而棧頂指針值是_H。設(shè)棧為順序棧，每個元素占4個字節(jié)。5. 當(dāng)兩個棧共享一存儲區(qū)時，棧利用一維數(shù)組stack(1,n)表示，兩棧頂指針為top1與top2，則當(dāng)棧1空時，top1為_，棧2空時 ，top2為_，棧滿時為_。6兩個棧共享空間時棧滿的條件_。7在作進(jìn)棧運(yùn)算時應(yīng)先判別棧是否_(1)_;在作退棧運(yùn)算時應(yīng)先判別棧是否_(2)_；當(dāng)棧中元素為n個，作進(jìn)棧運(yùn)算時發(fā)生上溢，則說明該棧的最大容量為_(3)_。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的空間時，應(yīng)將兩棧的_(

13、4)_分別設(shè)在內(nèi)存空間的兩端，這樣只有當(dāng)_(5)_時才產(chǎn)生溢出。8. 多個棧共存時，最好用_作為存儲結(jié)構(gòu)。9用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為_。10. 順序棧用data1.n存儲數(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開始的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=

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

15、值是_應(yīng)用的一個典型例子。22循環(huán)隊(duì)列用數(shù)組A0.m-1存放其元素值，已知其頭尾指針分別是front和rear ，則當(dāng)前隊(duì)列的元素個數(shù)是_。23設(shè)Q0.N-1為循環(huán)隊(duì)列，其頭、尾指針分別為P和R，則隊(duì)Q中當(dāng)前所含元素個數(shù)為_。24完善下面算法。后綴表達(dá)式求值，表達(dá)式13/25+61的后綴表達(dá)式格式為： 13, 25/61, +FUNC compute(a):real; 后綴表達(dá)式存儲在數(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)先級別的函數(shù)，operate(opnd1,oper,opnd2)為兩操作數(shù)的運(yùn)算結(jié)果函數(shù)。（#表示運(yùn)算起始和終

17、止符號） 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句填入下面算

18、法的_中：問題：設(shè)有n件物品，重量分別為w1,w2,w3,wn和一個能裝載總重量為T的背包。能否從n件物品中選擇若干件恰好使它們的重量之和等于T。若能，則背包問題有解，否則無解。解此問題的算法如下： 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

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)_) 背包無解END;四 應(yīng)用題1. 名詞解釋：棧。2. 名詞解釋：隊(duì)列3. 什么是循環(huán)隊(duì)列？【4. 假設(shè)以S和X分別表示入棧和出棧操作，則對初態(tài)和終態(tài)均為空的棧操作可由S和X組成的序列表示（如SXSX）。（1）試指出判別給定序列是否合法的一般規(guī)則。（2）兩個不同合法序列（對同一輸入序列）能否得到相同的輸出元素序列？如能得到，請舉列說明。5. 有5 個元素，

20、其入棧次序?yàn)椋篈，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個且D第二個出棧）的次序有哪幾個？6. 如果輸入序列為1 2 3 4 5 6,試問能否通過棧結(jié)構(gòu)得到以下兩個序列:4 3 5 6 1 2和1 3 5 4 2 6;請說明為什么不能或如何才能得到。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,試寫出借助一個棧可得到的兩個輸出序列和兩個不能得到的輸出序列。9. 設(shè)輸入序列為2，3，4，5，6，利用一個棧能得到序列2，5，3，4，6嗎？?？梢杂脝捂湵韺?shí)現(xiàn)嗎

21、？10. 試證明：若借助棧由輸入序列1,2,n得到輸出序列為P1,P2,Pn（它是輸入序列的一個排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著ijk,使PjPk0 THEN BEGIN p(w-1); writeln(w);輸出W p(w-1）END； END；17. 用一個數(shù)組S（設(shè)大小為MAX）作為兩個堆棧的共享空間。請說明共享方法，棧滿/棧空的判斷條件，并用C或PASCAL設(shè)計(jì)公用的入棧操作push（i，x），其中i為0或1，用于表示棧號，x為入棧值。18. 簡述下列程序段的功能。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á)式，畫出棧的變化過程圖。20. 在表達(dá)式中，有的運(yùn)算符要求從右到左計(jì)算，如A*B*C的計(jì)算次序應(yīng)為(A*(B*C)，這在由中綴生成后綴的算法中是怎樣實(shí)現(xiàn)的?(以*為例說明)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 問：(1) 若x為局部變量時；該函數(shù)遞歸結(jié)束后返回調(diào)用程序的sum=? 并畫出在遞歸過程中棧狀態(tài)的變化過程； (2) 若x為全程變量遞歸結(jié)束時返回調(diào)用程序的sum=?22. 畫出對算術(shù)表達(dá)式A-B*C/D-EF求值時操作數(shù)棧和運(yùn)算符棧的變化過程。23. 計(jì)算算術(shù)表達(dá)式的值時，可用兩個棧作輔助工具。對于給出的一個表達(dá)式，從左向右掃描它的字符，并將操作數(shù)放入棧S1中，運(yùn)算符放入棧S2中，但每次掃描到運(yùn)算符時，要把它同S2的棧頂運(yùn)算符進(jìn)行優(yōu)

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

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

26、的主要語句和出棧的主要語句。（2）對棧1、棧2，試分別寫出棧滿、?？盏臈l件。29. 簡述順序存儲隊(duì)列的假溢出的避免方法及隊(duì)列滿和空的條件。30. 舉例說明順序隊(duì)的“假溢出”現(xiàn)象，并給出解決方案。31. 怎樣判定循環(huán)隊(duì)列的空和滿？32. 簡要敘述循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，并寫出其初始狀態(tài)、隊(duì)列空、隊(duì)列滿時的隊(duì)首指針與隊(duì)尾指針的值。 33. 利用兩個棧sl,s2模擬一個隊(duì)列時，如何用棧的運(yùn)算實(shí)現(xiàn)隊(duì)列的插入，刪除以及判隊(duì)空運(yùn)算。請簡述這些運(yùn)算的算法思想。34一個循環(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ì)列實(shí)際存儲空間大小的影響，如果為了不損失存儲空間，你如何改進(jìn)循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿的判斷條件？35. 如果用一個循環(huán)數(shù)組q0.m-1表示隊(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分）36. 給出循環(huán)隊(duì)列中元素個數(shù)的計(jì)算式(設(shè)隊(duì)最大長度為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表示下一個可以插入隊(duì)列的位置。請解釋其原因。38. 設(shè)一個雙端隊(duì)列，元素進(jìn)入該隊(duì)列的次序?yàn)閍，b，c，d。求既不能由輸入受限的雙端隊(duì)列得到,又不能由輸出受限的雙端隊(duì)列得到的輸出序列?！?9. 若以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ì)操作，請給出：（1） 隊(duì)空的初始條件;（2） 執(zhí)行操作序列A3D1A5D2A1D2A4時的狀態(tài),并作必要的說明。41、設(shè)輸入元素為1、2、3、P和A，輸入次序?yàn)?23PA，如圖（編者略）。元素經(jīng)過棧后達(dá)輸出序列，當(dāng)所有元素均到達(dá)輸出序列后，有哪些序列可以作為高級語言的變量名。五 算法設(shè)計(jì)題1. 設(shè)有兩個棧S1,S2都采用順序棧方式，并且共享一個存儲區(qū)O.maxsize-1,為了盡量利用空間，減少溢出的可能，可采用

30、棧頂相向，迎面增長的存儲方式。試設(shè)計(jì)S1,S2有關(guān)入棧和出棧的操作算法。2. 設(shè)從鍵盤輸入一整數(shù)的序列：a1, a2, a3，an,試編寫算法實(shí)現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當(dāng)ai-1時，將ai進(jìn)棧；當(dāng)ai=-1時，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況（入棧滿等）給出相應(yīng)的信息。3. 設(shè)表達(dá)式以字符形式已存入數(shù)組En中，#為表達(dá)式的結(jié)束符，試寫出判斷表達(dá)式中括號（和）是否配對的C語言描述算法：EXYX(E); (注：算法中可調(diào)用棧操作的基本算法。) 4. 從鍵盤上輸入一個逆波蘭表達(dá)式，用偽碼寫出其求值程序。規(guī)定：逆波蘭表達(dá)式的長度不超過一行，以$符作為輸入結(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）通過對（1）的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。6.設(shè)計(jì)一個算法，判斷一個算術(shù)表達(dá)式中的括號是否配對。算術(shù)表達(dá)式保存在帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，每個結(jié)點(diǎn)

32、有兩個域：ch和link，其中ch域?yàn)樽址愋汀?. 請利用兩個棧S1和S2來模擬一個隊(duì)列。已知棧的三個運(yùn)算定義如下：PUSH(ST,x):元素x入ST棧；POP(ST,x)：ST棧頂元素出棧，賦給變量x；Sempty(ST)：判ST棧是否為空。那么如何利用棧的運(yùn)算來實(shí)現(xiàn)該隊(duì)列的三個運(yùn)算：enqueue:插入一個元素入隊(duì)列； dequeue:刪除一個元素出隊(duì)列；queue_empty：判隊(duì)列為空。（請寫明算法的思想及必要的注釋）三(12分)】類似本題的另外敘述有：（1）有兩個長度相同的棧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)成一個隊(duì)列，試寫出下面入隊(duì)列、出隊(duì)列操作算法：PROCEDURE EnQueue(x:Datatype);FUNCTION DeQueue: Datatype;【北京郵電大學(xué) 2000 六（10分）】8. 設(shè)結(jié)點(diǎn)結(jié)構(gòu)為(data,link)，試用一個全局指針p和某種鏈接結(jié)構(gòu)實(shí)現(xiàn)一個隊(duì)列,畫出示意圖,并給出入隊(duì)addq和

34、出隊(duì)deleteq過程,要求它們的時間復(fù)雜性都是O(l)（不計(jì)new和dispose時間）9. 假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個指針指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針，如圖所示（編者略），請寫出相應(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. 在一個循環(huán)鏈隊(duì)中只有尾指針（記為rear，結(jié)點(diǎn)結(jié)構(gòu)為數(shù)據(jù)域data，指針域next），請給出這種隊(duì)列的入隊(duì)和出隊(duì)操作的實(shí)現(xiàn)過程?！?/p>

35、山東科技大學(xué) 2002 一、2 （6分）】12. 雙端隊(duì)列（duque）是一個可以在任一端進(jìn)行插入和刪除的線性表?，F(xiàn)采用一個一維數(shù)組作為雙端隊(duì)列的數(shù)據(jù)存儲結(jié)構(gòu)，使用類PASCAL語言描述如下：CONST maxsize=32; 數(shù)組中可容納的元素個數(shù)TYPE duque=RECORD elem: ARRAY0.MAXSIZE-1 OF datatype; 環(huán)形隊(duì)列的存放數(shù)組 end1,end2:0.MAXSIZE; 環(huán)形數(shù)組的兩端 END;試編寫兩個算法add(Qu:duque;x:datatype;tag:0.1)和delete（Qu:duque; var x:datatype; tag:0.1）用以在此雙端隊(duì)列的任一端進(jìn)行插入和刪除。當(dāng)tag=0時在左端endl端操作，當(dāng)tag=1時在右端end2端操作。13. 一個雙端隊(duì)列deque是限定在兩端end1，end2都可進(jìn)行插入和刪除的線性表。隊(duì)空條件是end1=end2。若用順序方式來組織雙端