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

2、B。兩個棧的棧頂同時到達棧空間的中心點 其中一個棧的棧頂到達棧空間的中心點 . C。 D。【上海海運學院一個棧的輸入序列為元素是 （A。3。）.兩個棧的棧頂在棧空間的某一位置相遇 . 兩個棧均不空 , 且一個棧的棧頂到達另一個棧的棧底 1997 二、 1（5 分） 】【上海海運學院1999 二、123n,若輸出序列的第一個元素是n,輸出第i1(5 分) 】1 =i<=n )確定C。i1999 一、 9（1 分）】4. 若一個棧的輸入序列為1 , 2, 3,，n,i+1中山大學B。D. n i輸出序列的第一個元素是 i ，則第 j 個輸出元素是 （） .A 。i-j-1j-i+1D. 不確

3、定的【武漢大學 2000二、3】5. 若已知一個棧的入棧序列是 1,2 ，3, ， n, 則 pi 是（A。）。in-i+1D. 不確定B. iC.n,其輸出序列為 pi, p2,p3,， PN,若pN是B. nC。【南京理工大學 2001 一、 1（1。5分）】6. 有六個元素6，5，4，3,2 ，1 的順序進棧 , 問下列哪一個不是合法的出棧序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 34 1 5 6北方交通大學 20013（2 分）】7. 設棧的輸入序列是 1， 一、 10（2分）】A. 1 ， 2,4,3 ，D。 4 ， 3,

4、1 ， 2， 一個棧的輸入序列為A. 2 3 4 1 52， 3，4, 則（B. 2 ，E。8。學9。（10。（11。為） 不可能是其出棧序列。【中科院計算所1，3，4，3,2 ，1，4，1 2 3 4 5,則下列序列中不可能是棧的輸出序列的是B. 5 4 1 3 2【南開大學 20002000 一、 2（2 分）】設一個棧的輸入序列是）。5 1 2 3 4 D. 3 2 1 5 4合肥工業大學 2001A。2000C。 2 3 1 4 51】【山東大學C. 1 ，4，3,2,).D. 1 52001 二、 4 （ 1 分）】北京理工大1,2,3 ， 4,5, 則下列序列中，是棧的合法輸出序列

5、的是某堆棧的輸入序列為 a， b ，c ，）.A。 a,c ， b， d D. d ， c ， a， b 北京航空航天大學 2000B。4 5 1 3 2C。4 3 1 2、 1 （ 2 分）】d,下面的四個序列中，不可能是它的輸出序列的是B。 b ， c ， d ， aC。 c, d,b ，、32 分）】 【北京郵電大學設 abcdef 以所給的次序進棧 , 若在進棧操作時，允許退棧操作1999 一、3（2 分）】 , 則下面得不到的序列）。（Afedcba cabdef 南京理工大學 設有三個元素）。XYZB. bcafedC. dcefbaD。12. (X，1996Y， Z一、 9（2

6、分）】順序進棧 （進的過程中允許出棧），列得不到的出棧排列是B。YZXC。ZXYD。 ZYX、 5（2 分）】【南京理工大學輸入序列為ABC可以變為CBA時,經過的棧操作為（ 分）】A. push,pop ，push,pop ，push,poppop13.8(11997B。）【中山大學 1999push ， push,push,pop,pop ，C. push,push ，pop，pop，push,pop pop,pop若一個棧以向量 ）。A top ： =top+1 top ：=top+1 C. top:=top-1;D。 push,pop,push,push ，14。作是=x；V 1.n

7、存儲，初始棧頂指針top為n+1,則下面x進棧的正確操V top :=xV top ： =xD。B.V top ：V top:=x;top ： =top-1南京理工大學 若棧采用順序存儲方式存儲、 13（ 2 分）】15.若棧采用順序存儲方式存儲 ,現兩棧共享空間 V1。.m ,top2）棧頂，棧1的底在v1 ，棧2的底在Vm，則棧滿的條件是1998i 代表第 i 個棧 （ i =1 ， （ ）。=mD. top1【南京理工大學 =top2 1999一、 14（ 1 分） 】16.棧在 （）中應用。【中山大學1998 二、3（2分）】A. 遞 歸調 用B。子程 序調 用C。表達 式求值DoA,

8、 B,c17。一個遞歸算法必須包括（） 。【武漢大學 2000 二、 2】A。遞 歸 部 分B. 終止條件 和 遞歸 部分C. 迭 代 部Aabcd*+-B。 abc+*d C。 abc*+d D. + abcd20。 表達式3* 2A （4+2 * 2-6*3）-5 求值過程中當掃描到6時,對象棧和算符棧為（）,其中a為乘幕.A. 3， 2， 4， 1,1 ；( * A( +*B. 3， 2,8 ；(* A2;（*A（ -D. 3 ， 2， 8; （ *A（-【青島大學 2000 五、 5（2 分）】21。 設計一個判別表達式中左， 右括號是否配對出現的算法 , 采用（ 佳。C。 3 ， 2

9、,4,2 ，） 數據結構最A.線性表的順序存儲結構B.隊列結構D。棧【西安電子科技大學 1996 一、 6（ 2 分）】22。 用鏈接方式存儲的隊列， 在進行刪除運算時 （C. 線性表的鏈式存儲）。【北方交通大學 2001 一12（ 2 分）】A。僅修改頭指針B。僅修改尾指針C。頭、尾指針都要修分 D. 終止條件和迭代部分18. 執行完下列語句段后，i值為：（）【浙江大學 2000 一、6 （3 分）】intf(int x) return( (x>0) ? x* f(x-1 ): 2) ; int i;i =f(f(1)；A .2B。4C。8D.無限遞歸19。表達式 a* ( b+c)

10、d的后綴表達式是 （） 。【南京理工大學2001 一、 21.5 分）】改 D. 頭、尾指針可能都要修改23. 用不帶頭結點的單鏈表存儲隊列時，其隊頭指針指向隊頭結點，其隊尾指針指向隊尾結點，則在進行刪除操作時 （） 。 【北京理工大學 2001 六、3 （2分）】A.僅修改隊頭指針B.僅修改隊尾指針C. 隊頭、隊尾指針都要修改D. 隊頭 , 隊尾指針都可能要修改24. 遞歸過程或函數調用時 , 處理參數及返回地址， 要用一種稱為 （）的數據結構。A . 隊 列B . 多 維 數組C.棧D.線性表【福州大學 1998 一、1（2 分）】25. 假設以數組Am存放循環隊列的元素，其頭尾指針分別為

11、front和rear，則當前隊列中的元素個數為（）. 【北京工商大學 2001 一、2（3分）】A(rear front+m) mBrear-front+1C(front-rear+m) mD（ rear front） m26. 循環隊列 A 0.m 1存放其元素值，用 front 和 rear 分別表示隊頭和隊尾，則當A。( rear front+m)%mBfront+1C。rear-front-1D。rear-front前隊列中的元素數是 （） 。【南京理工大學 2001 一、 5（1.5 分）】的 操作 為 （rear27.學28。循 環 隊列 存 儲在 數組 A0 。 .m 中 ， 則

12、入 隊時 1999 一、 6（1 分）】 A。 rear=rear+1C. rear= （ rear+1） mod m 若用一個大小為 6 的數組來實現循環隊列） 。 【 中山 大當從隊列中刪除一個元素，再加入兩個元素后， 江大學 1999 四、 1（4 分）】A 。 1 和 5B。 rear=(rear+1) mod (m-1)D。 rear=(rear+1)mod ( m+1) , 且當前 rear 和 front 的值分別為 rear 和 front 的值分別為多少?(0和 3，）【浙B.2和4C。4和229。bdac已知輸入序列為A. dacbE。西安交通大學D。 5 和 1abcd

13、經過輸出受限的雙向隊列后能得到的輸出序列有 B. cadb C. dbca 以上答案都不對1996 三、 3 （3 分） 】 則既不能由輸入受限的雙端隊列得到， ）. 【西安電子科技大學若以 1234 作為雙端隊列的輸入序列，（30.輸出受限的雙端隊列得到的輸出序列是）。D。也不能由1996 一、5（2 分 ） 】A.1234B4231D。 42134132 C.rear ，隊頭是 front ，則隊空的條件B.31 。 最大容量為 n 的循環隊列，隊尾指針是 是 （ ） .A. （ rear+1） MOD n=front rear=frontC rear+1=frontD。( rear-l)

14、 MOD n=front【南京理工大學 1999一、 16（2 分）】32。 棧和隊列的共同點是（）。【燕山大學2001 一、 1（2 分） 】A。 都是先進先出B. 都是先進后出C. 只允許在端點處插入和刪除元素D。 沒有共同點33. 棧的特點是（），隊列的特點是 （），棧和隊列都是 （ ）。若進棧序列為 1， 2，3，4則（ ）不可能是一個出棧序列（不一定全部進棧后再出棧） ; 若進隊列的序列為1，2,3 ，4 則（）是一個出隊列序列。【北方交通大學 1999 一、 1（ 5 分）】， ： A。 先進先出B.后進先出C。 進優于出D。 出優于進：A.順序存儲的線性結構B。鏈式存儲的線性結構

15、C限制存取點的線性結構0限制存取點的非線性結構， : A. 3,2 ，1,4B. 3 ，2,4 ， 1C。 4，2,3，1D。 4 ，3,2,1F。 1,2,3,4G。 1,3,2,434。 棧和隊都是（ ）【南京理工大學A.順序存儲的線性結構BoC。 限制存取點的線性結構D。1997 一、 3（2 分）】鏈式存儲的非線性結構 限制存取點的非線性結構35o 設棧 S 和隊列 個元素出棧后即進隊列 至少應該是 （A.62 【南京理工大學Q的初始狀態為空，元素e1,Q若6個兀素出隊的序列是）oe2, e3,e4 , e5和e6依次通過棧 S, e2， e4， e3,e6,e5 ， e1 則棧 S

16、的容量Bo 4C. 3Do2000 一、 6（1.5 分）】36. 用單鏈表表示的鏈式隊列的隊頭在鏈表的（ 1（2 分）】A.鏈頭）位置。【清華大學1998B.鏈尾C.鏈37.依次讀入數據元素序列 a,b , c, d,e , f,g 進棧，每進一個元素,機器可要求下一個 元素進棧或彈棧， 如此進行 , 則棧空時彈出的元素構成的序列是以下哪些序列？【哈爾濱工業大學 2000 七（ 8分）】A. d , e, c, f, b, g, aBo f,e,g, d,a , c, bC. e, f , d, g, b, c,aDo c, d,b,e , f,a , g二判斷題1o消除遞歸不一定需要使用棧

17、,此說法（)【中科院計算所1998 二、 2（2 分）】【中國科技大學1998 二、 2( 2 分)】2.棧是實現過程和函數等子程序所必需的結構。(）【合肥工業大學2000 二2(1分）】3.兩個棧共用靜態存儲空間，對頭使用也存在空間溢出冋題。(）【青島大學2000 四、 2( 1 分)】4. 兩個棧共享一片連續內存空間時, 為提高內存利用率 , 減少溢出機會 , 應把兩個棧的棧底分別設在這片內存空間的兩端。（）【上海海運學院1998 一、4（1分）】5o即使對不含相同元素的同一輸入序列進行兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（）【北京郵電大學1999二、4 （2分）

18、】6o 有n個數順序（依次）進棧，出棧序列有Cn種，Cn=1/ （n +1）衣（2n） ! / （n!）*（n!） （）【北京郵電大學 1998 一、 3（2 分）】7o棧與隊列是一種特殊操作的線性表。）【青島大學 2001四、 3( 1 分)】8.若輸入序列為 1,2, 3,4, 5, 6,則通過一個棧可以輸出序列 3, 2, 5,6,4,1。（)【上海海運學院 1995 一、 2（1 分）1997 一、 3(1 分)】9.棧和隊列都是限制存取點的線性結構。（）【中科院軟件所1999六、 (5 )(2分）】10.若輸入序列為 1, 2, 3,4 , 5, 6,則通過一個棧可以輸出序列1, 5

19、,4, 6,2, 3。()【上海海運學院 1999 一、 3（1 分）】11.任何一個遞歸過程都可以轉換成非遞歸過程。（）【上海交通大學1998 一、3 （1分）】12. 只有那種使用了局部變量的遞歸過程在轉換成非遞歸過程時才必須使用棧。【上海交通大學1998 、4（ 1分）】13。隊列是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。（ ）【上海海運學院1998 一、3（1分）】14。 通常使用隊列來處理函數或過程的調用.（）【南京航空航天大學1997 5（1分）】）【上海交通大）【南京航空航天大15。隊列邏輯上是一個下端和上端既能增加又能減少的線性表。（學 1998 一

20、、2 】16。循環隊列通常用指針來實現隊列的頭尾相接。（學 1996六、1（ 1分）】17。循環隊列也存在空間溢出問題。（）【青島大學2002 、2( 1 分)】（）【長沙鐵道學院）【北京郵電）1997 一、3】1998 一、3(118. 隊列和棧都是運算受限的線性表，只允許在表的兩端進行運算。1997 一、5（ 1 分）】19. 棧和隊列都是線性表，只是在插入和刪除時受到了一些限制.（大學2002 一、3（1分）】20. 棧和隊列的存儲方式，既可以是順序方式，又可以是鏈式方式。（【上海海運學院1996 一、2（ 1分） 1999 一、2（ 1分）】三 填空題1 棧是的線性表，其運算遵循 的原

21、則.【北京科技大學2. 是限定僅在表尾進行插入或刪除操作的線性表。【燕山大學 分)3。 一個棧的輸入序列是：1, 2, 3則不可能的棧輸出序列是 .【中國人民大學2001一、1 （2 分）4. 設有一個空棧，棧頂指針為1000H（十六進制），現有輸入序列為1, 2, 3, 4, 5,經過PUSH,PUSHPOP,PUSH,POPPUSHPUSH之后，輸出序列是，而棧頂指針值是H.設棧為順序棧，每個元素占4個字節。【西安電子科技大學1998二、1 （4分）5。當兩個棧共享一存儲區時，棧利用一維數組stack（1 , n）表示，兩棧頂指針為top : 1與top : 2，則當棧1空時,top :

22、1 為，棧2空時,top :2為,棧滿時為【南京理工大學1997三、1（3分）6. 兩個棧共享空間時棧滿的條件 。【中山大學 1998 一、3（1分）7在作進棧運算時應先判別棧是否（1）;在作退棧運算時應先判別棧是否;當棧中元素為n個，作進棧運算時發生上溢，則說明該棧的最大容量為。為了增加內存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續的空間時，應將兩棧的（4 ）分別設在內存空間的兩端，這樣只有當（5）時才產生溢岀。【山東工業大學 1994 一、1 （5 分）& 多個棧共存時，最好用作為存儲結構。【南京理工大學2001二、7 （2分）9. 用S表示入棧操作，X表示出棧操作，若元

23、素入棧的順序為1234，為了得到1342出棧順序，相應的S和X的操作串為.【西南交通大學2000 一、510。順序棧用data1。n 存儲數據，棧頂指針是top，則值為x的元素入棧的操作是11. 表達式23+ （ （ 12 * 3-2）/4+34*5/7）+108/9 的后綴表達式是.【中山大學 1998 一、4 （1 分）】12。循環隊列的引入，目的是為了克服 。【廈門大學 2001 一、1（ 14/813. 用下標0開始的N元數組實現循環隊列時，為實現下標變量 M加1后在數組有效下標范圍內循環，可采用的表達式是：M: = （填PASCAL語言，C語言的考生不填）； M= （填C語言，PAS

24、CALS言的考生不填）。【西南交通大學2000 一、7】14. 又稱作先進先出表。【重慶大學2000 一、7】15. 隊列的特點是。【北京理工大學2000二、2 （2分）】16. 隊列是限制插入只能在表的一端，而刪除在表的另一端進行的線性表，其特點是。【北方交通大學 2001二、5】17。已知鏈隊列的頭尾指針分別是f和r，則將值x入隊的操作序列是 .【合肥工業大學2000三、3 （2分）】18 區分循環隊列的滿與空，只有兩種方法，它們是 和.【北京郵電大學 2001 二、2 （4 分）】19. 設循環隊列用數組 A 1.M 表示，隊首、隊尾指針分別是FRONT和TAIL，判定隊滿的條件為。【山

25、東工業大學1995 一、1 （1分）】20。設循環隊列存放在向量 sq.data 0: M中，則隊頭指針 sq.front 在循環意義下的出隊操作可表示為,若用犧牲一個單元的辦法來區分隊滿和隊空（設隊尾指針sq。rear ），則隊滿的條件為。【長沙鐵道學院1997二、4 （4分）】21表達式求值是 應用的一個典型例子.【重慶大學2000 一、10】22. 循環隊列用數組 A0。m 1 存放其元素值，已知其頭尾指針分別是front和rear則當前隊列的元素個數是 。【廈門大學2000六、1 （16%/3分）】23. 設Q0.N 1 為循環隊列，其頭、尾指針分別為 P和R,則隊Q中當前所含元素個數

26、為o【北京科技大學1997 一、4】24. 完善下面算法。【中山大學1998后綴表達式求值，表達式13/25+61FUNC compute(a ) : real;BEGINset null (s) ; i : =1;ch:=WHILE ch >'' DOBEGINCASE ch OF'0'。 9四、2 （6分）】的后綴表達式格式為：后綴表達式存儲在數組 a1.m中。(1 )x： =0;WHILE ch< >BEGIN13, 25/61, +','DO=x*10+ord(ch) ord( 0');=i+1 ; ch:= (

27、2)i :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:=a i;END;comput: = (3) ;END;25。算術表達式求值的流程，其中OPTF為算術符棧，OPND為操作數棧，precede(oper1 ,oper2)是比較運算符優先級別的函數operate (opnd1,oper,opnd2 )為兩操作數的運算結果函數。(#表示運算起始和終止

28、符號)【西北工業大學1999六、2 ( 7分)】FUNCTION exp_reduced:opera ndtype;INITSTACK(OPTF);PUSH (OPTR"#") ； INITSTACK( OPND) read(w);WHILE NOT( w='#')AND (GETTOP(OPTR)=' # ' ) ) DOIF NOT w in op THEN PUSH(OPND , w);ELSE CASE precede (GETTO( OPTR , w)OF'：;read(w );:'=':0; read(w)

29、;'>':theta:=POP(OPTR) ; b: =POP(OPN)a:=POP(OPND ;(3) ；ENDC;RETURN(GETTOP(OPND；ENDF;26. 根據需要，用適當的語句填入下面算法的 中：問題：設有n件物品，重量分別為 w , w,W3,wn和一個能裝載總重量為 T的背包。能 否從n件物品中選擇若干件恰好使它們的重量之和等于T。若能，則背包問題有解，否則無解。解此問題的算法如下：FUNCTION kanp_stack(VAR stack , w:ARRAY1。.n OF real; VAR top:integer ; T： real) : bo

30、olean;w 1 ： n存放n件物品的重量，依次從中取出物品放入背包中， 檢查背包重量， 若不超過T,則裝入，否則棄之，取下一個物品試之。若有解則返回函數值true，否則返回falseBEGINtop : =0;i:=1; i指示待選物品WHILE (1)AND(2 )DOIF (3)OR(4)AND (i n)THEN : top :=(5) ; stacktop :=i; 第 i 件物品裝入背包T:=T-w : i;IF T=0 THEN RETURN (6)背包問題有解ELSE : IF (i=n ) AND (top > 0)THEN i : = (7);取出棧頂物品top :

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

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

33、么？【北京科技大學1998 一、2& 設輸入序列為 a, b,c,d,試寫出借助一個棧可得到的兩個輸出序列和兩個不能得到的 輸出序列。【北京科技大學2001 一、4 （2分）9。設輸入序列為2, 3,4 , 5, 6,利用一個棧能得到序列2, 5, 3,4 , 6嗎?棧可以用單鏈表實現嗎？【山東師范大學1996五、4（2分）10。 試證明：若借助棧由輸入序列 1, 2,，n得到輸出序列為 R,P2,，R（它是輸入 序列的一個排列），則在輸出序列中不可能出現這樣的情形 ：存在著i<j<k,使P<P P。【上 海交通大學 1998 二（15分）11。設一數列的輸入順序為

34、123456,若采用堆棧結構，并以A和D分別表示入棧和出棧操作，試問通過入出棧操作的合法序列.（1）能否得到輸出順序為 325641的序列.（5分）（2） 能否得到輸出順序為 154623的序列。（5分）【北方交通大學1995 一（ 10 分）12。（ 1）什么是遞歸程序？（2）遞歸程序的優、缺點是什么？（3） 遞歸程序在執行時，應借助于什么來完成？( 4) 遞歸程序的入口語句、 出口語句一般用什么語句實現？ 【大連海事大學 1996 二、 4( 4 分)】13。設有下列遞歸算法：FUNCTION vol ( n： integer )： integer ；VAR x :integer:BEGI

35、N IF n=0 THEN vol ：=0ELSE BEGIN read(x) ；vol:=vol(n 1)+x； END；END； 如該函數被調用時，參數 n 值為 4, 讀入的 x 值依次為 5，3， 4， 2,函數調用結束時返回值 vol 為多少?用圖示描述函數執行過程中，遞歸工作棧的變化過程. 【北京工業大 學 1998 四 (10分) 】14。當過程P遞歸調用自身時，過程P內部定義的局部變量在P的2次調用期間是否占用同一數據區？為什么 ?【山東師范大學1999 一、 4 (4 分)】15。試推導出當總盤數為 n 的 Hanoi 塔的移動次數 . 【北京郵電大學 2001 四、3 (

36、5 分)】16。對下面過程寫出調用 P(3)的運行結果。PROCEDURE (pw:integer ); BEGINIF w 0 THENBEGINp(w 1 );writein (w);輸出 W p( w 1 )END; END;【西北大學 2001 三、 7】17。 用一個數組S (設大小為MAX作為兩個堆棧的共享空間。請說明共享方法，棧滿/ 棧空的判斷條件，并用 C或PASCALS計公用的入棧操作 push (i,x )，其中i為0或1,用 于表示棧號， x 為入棧值。【浙江大學 1998 五、2 (7 分)】18。簡述下列程序段的功能 .PROCaigo(VAR S ： stack;

37、k:integer) ;VAR T: stack; temp ： integer ;WHILE NOT empty(S ) DOtemp ：=POP(S); IF temp< kTHEN PUSH(T, temp) ;WHILE NOT empty(T)DO temp:=POP( T); PUSH( S,temp) ;【山東科技大學 2002 一、1(4分)】19。用棧實現將中綴表達式 8-(3+5)*( 56/2) 轉換成后綴表達式, 畫出棧的變化過程圖。 【南京航空航天大學 2001 五 (10 分)】20。 在表達式中 , 有的運算符要求從右到左計算,如 A*B*C 的計算次序應為

38、 (A *(B*C) ),這在由中綴生成后綴的算法中是怎樣實現的?(以* 為例說明)【東南大學 1993一、2(6分)1997 一、1(8分)】21。有遞歸算法如下：FUNCTION sum （ n：integer）:intger；BEGINIF n=0 THEN sum:=0ELSE BEGIN read （ x） ； sum:=sum（ n 1） +x END；END；設初值n=4,讀入 x=4,9,6,2問： （1） 若 x 為局部變量時；該函數遞歸結束后返回調用程序的sum=？ 并畫出在遞歸過程中棧狀態的變化過程；（2） 若x為全程變量遞歸結束時返回調用程序的sum=?【北京郵電大學

39、1997 一 （10 分）】22。畫出對算術表達式 A-B*C/D ET F求值時操作數棧和運算符棧的變化過程.【東南大學 2000 一、 3（6 分）】23. 計算算術表達式的值時， 可用兩個棧作輔助工具 . 對于給出的一個表達式， 從左向右掃描它的字符，并將操作數放入棧S1中,運算符放入棧S2中，但每次掃描到運算符時，要把它同S2的棧頂運算符進行優先級比較，當掃描到的運算符的優先級不高于棧頂運算符的優先級時，取出棧S1的棧頂和次棧頂的兩個元素，以及棧S2的棧頂運算符進行運算將結果放入棧S1中（得到的結果依次用 T1、T2等表示）。為方便比較，假設棧 S2的初始棧頂為？（？ 運算符的優先級低

40、于加、 減、乘、除中任何一種運算） 。現假設要計算表達式 : A-BC/D+E/F。 寫出棧S1和S2的變化過程。【山東科技大學2001 一、4 （7分）】24。 有字符串次序為 3* y-a/yA2,利用棧，給出將次序改為3y* ay2A/ 的操作步驟。 （可用X代表掃描該字符串過程中順序取一個字符進棧的操作，用S代表從棧中取出一個字符加入到新字符串尾的出棧操作.例如，ABC變為BCA的操作步驟為 XXSXSS 【東北大學 2001 一、 4 （ 4 分）】25. 內存中一片連續空間（不妨假設地址從1到m）提供給兩個棧 S1和S2使用，怎樣分配這部分存儲空間，使得對任一個棧，僅當這部分空間全

41、滿時才發生上溢。【東北大學 2000 一、 1 （3 分）】26。將兩個棧存入數組 V1。 .m 應如何安排最好?這時棧空、棧滿的條件是什么?【東 南大學 1998 一、 5】27. 在一個算法中需要建立多個堆棧時可以選用下列三種方案之一，試問：這三種方案之 間相比較各有什么優缺點?（1）分別用多個順序存儲空間建立多個獨立的堆棧;（ 2）多個堆棧共享一個順序存儲空間;（3）分別建立多個獨立的鏈接堆棧。 【北京航空航天大學1998 一、 6（4分）】28在某程序中 , 有兩個棧共享一個一維數組空間SPACEN、 SPACE 0、 SPACE N1 分別是兩個棧的棧底。（1） 對棧1、棧2,試分別

42、寫出（元素 x）入棧的主要語句和出棧的主要語句.（2） 對棧 1、棧 2，試分別寫出棧滿、棧空的條件。【北京理工大學1999 二、 2（8 分）】29。簡述順序存儲隊列的假溢出的避免方法及隊列滿和空的條件 .【山東大學 2000 一、2 （ 4分）】30。舉例說明順序隊的“假溢出”現象 , 并給出解決方案 . 【福州大學 1998 三、 5 （6 分） 】31。怎樣判定循環隊列的空和滿?【燕山大學1999 二、 3（4分）】32. 簡要敘述循環隊列的數據結構，并寫出其初始狀態、隊列空、隊列滿時的隊首指針與 隊尾指針的值。【南京航空航天大學 1995 七 （5 分）】33. 利用兩個棧 sl,s

43、2 模擬一個隊列時， 如何用棧的運算實現隊列的插入 , 刪除以及判隊空 運算。請簡述這些運算的算法思想。 【北京郵電大學 1992一、1】【東南大學1999 一、1 （7 分）】34一個循環隊列的數據結構描述如下：TYPE sequeuetp=RECORDelem : ARRAY1 .MAXSIZE OF elemtp ;front,rear ： 0。 MAXSIZE;END；給出循環隊列的隊空和隊滿的判斷條件， 并且分析一下該條件對隊列實際存儲空間大小的影 響，如果為了不損失存儲空間， 你如何改進循環隊列的隊空和隊滿的判斷條件？ 【西北工業 大學 1999 三 （8 分） 】35。如果用一個

44、循環數組 q0.。m 1表示隊列時，該隊列只有一個隊列頭指針front ,不設隊列尾指針 rear ，而改置計數器 count 用以記錄隊列中結點的個數 .（1） 編寫實現隊列的三個基本運算:判空、入隊、出隊（3 分）（2） 隊列中能容納元素的最多個數是多少?（1 分）【東北大學2002 一、 1】36。給出循環隊列中元素個數的計算式（設隊最大長度為N,隊首指針FRONT隊尾指針REAR）【西北大學 2000 二、7 （5分）】37。順序隊列一般應該組織成為環狀隊列的形式， 而且一般隊列頭或尾其中之一應該特殊處理。例如 , 隊列為 listarray0 。 .n 1, 隊列頭指針為 front

45、, 隊列尾指針為rear ， 則listarray rear 表示下一個可以插入隊列的位置。 請解釋其原因。 【北京大學1999 一、3 （20/3 分） 】38。設一個雙端隊列，元素進入該隊列的次序為a， b， c， d. 求既不能由輸入受限的雙端隊列得到，又不能由輸出受限的雙端隊列得到的輸出序列 . 【中山大學 1999 一、 4 （3 分）】39。若以 1、2、3、4 作為雙端隊列的輸入序列 , 試分別求出以下條件的輸出序列 :（1）能由輸入受限的雙端隊列得到，但不能由輸出受限的雙端隊列得到的輸出序列；（2）能由輸出受限的雙端隊列得到，但不能由輸入受限的雙端隊列得到的輸出序列；（3） 既

46、不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列。【山東科技大學 2001 一、 3 （6分）】40。假設以數組 sq0。 .7存放循環隊列元素，變量 f 指向隊頭元素的前一位置 ,變量 r 指向隊尾元素，如用A和D分別表示入隊和出隊操作，請給出 ：（1） 隊空的初始條件；（2）執行操作序列 YDADAFa4時的狀態，并作必要的說明。【北方交通大學1993四（ 12 分）】41。 設輸入元素為1、2、3、P和A,輸入次序為123PA，如圖（編者略）。元素經過棧后達輸 出序列，當所有元素均到達輸出序列后 ， 有哪些序列可以作為高級語言的變量名。【中山大學 1997 】五 算

47、法設計題1. 設有兩個棧S,S2都采用順序棧方式， 并且共享一個存儲區 O.maxsize-1,為了盡量 利用空間，減少溢出的可能，可采用棧頂相向，迎面增長的存儲方式。試設計 S1, S2有關入棧 和出棧的操作算法。【哈爾濱工業大學2001七（12分）】2. 設從鍵盤輸入一整數的序列：a1, a 2, a 3,，an,試編寫算法實現：用棧結構存儲輸入的整數，當a 1時，將ai進棧；當a= 1時，輸出棧頂整數并出棧。算法應對異常情況（入棧滿等）給出相應的信息。【南京航空航天大學1998 六（10分）】3. 設表達式以字符形式已存入數組 中括號（和）是否配對的 作的基本算法。）【北京科技大學200

48、1九、14. 從鍵盤上輸入一個逆波蘭表達式， 不超過一行，以$符作為輸入結束四種運算例如：234 34+2 * $【山東師范大學1999七 （10分）】5. 假設以I和0分別表示入棧和出棧操作。 棧的初態和終態均為空， 入棧和出棧的操作序列可表示為僅由I和0組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列.（1）下面所示的序列中哪些是合法的？A.I0II0I00III0I0I0D。III00I00（2 ）通過對（1）的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false （假定被判定的操作序列已存入一維數組中）。【武漢大學 2000五、2】6. 設計

49、一個算法，判斷一個算術表達式中的括號是否配對。算術表達式保存在帶頭結點的單循環鏈表中，每個結點有兩個域：ch和link，其中ch域為字符類型。【南京郵電大學2000五】7. 請利用兩個棧 S1和S2來模擬一個隊列。已知棧的三個運算定義如下:PUSH （ ST, x）:元素x入ST棧；P0（ST，x） : ST棧頂元素出棧，賦給變量x;Sempty（ST）:判ST棧是否為空。 那么如何利用棧的運算來實現該隊列的三個運算：en queue:插入一個元素入隊 列；dequeue :刪除一個元素出隊列；queue_empty :判隊列為空。（請寫明算法的思想及 必要的注釋）【西安電子科技大學 2001

50、軟件五（10分）】【上海交通大學1999二（12分）】【河海大學 1998 三（12分）】類似本題的另外敘述有：（1）有兩個長度相同的棧 S1, S2,已知以下入棧、出棧、判棧滿和判棧空操作：PR0CEDUREFUNCTIONFUNCTIONFUNCTI0NEn中， #'為表達式的結束符，試寫出判斷表達式 C語言描述算法：EXYX（E）;（注：算法中可調用棧操（10分）】用偽碼寫出其求值程序。規定：逆波蘭表達式的長度,操作數之間用空格分隔，操作符只可能有+、一、*、/B.10010110C.push(Stack : Stacktype;x : Datatype)； Pop (Stack

51、:Stacktype ) :Datatype ； Full (Stack:Stacktype ) :Boolean ; Empty(Stack : Stacktype)Boolean;現用此二棧構成一個隊列，試寫出下面入隊列、出隊列操作算法：PR0CEDURE EnQueue（x:Datatype）;FUNCTI0N DeQueue Datatype ;【北京郵電大學2000 六（10 分）】8。設結點結構為 （data,link） ，試用一個全局指針 p 和某種鏈接結構實現一個隊列 , 畫出 示意圖 , 并給出入隊 addq 和出隊 deleteq 過程 , 要求它們的時間復雜性都是 O（l ）（不計 new 和 dispose 時間）【東南大學 1996二 （10 分）】9. 假設以帶頭結點的循環鏈表表示隊列， 并且只設一個指針指向隊尾結點， 但不設頭指針， 如圖所示 （編者略），請寫出相應的入隊列和出隊列算法。【西安電子科技大學1999 計應用 六 （ 10分）】10. 如果允許在循環隊列的兩端都可以進行插入和刪除操作。要求 :（1） 寫出循環隊列的類型定義 ;（2） 寫出“從隊尾刪除”和“從隊頭插