數(shù)據(jù)結(jié)構(gòu)第三章考試題庫(含答案

1、第3章棧和隊(duì)列一選擇題1.對于棧操作數(shù)據(jù)的原則是（）。【青島大學(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-1B. nC. n+1D.n/2: A.長度B.深度C.棧頂D.棧底: A.兩個(gè)棧的棧頂同時(shí)到達(dá)棧空間的中心點(diǎn).B.其中一個(gè)棧

2、的棧頂?shù)竭_(dá)?？臻g的中心點(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è)棧的輸入序列為123n，若輸出序列的第一個(gè)元素是n，輸出第i（1=i0) ? x* f(x-1):2);int i;i =f(f(1);A2B. 4C. 8D.無限遞歸19.表達(dá)式a*(b+c)-d的后綴表達(dá)式是()?！灸暇├砉ご髮W(xué)2001一、2（1.5分）】Aabcd*+-B. abc+*d-C. abc*+d-D. -+*abcd20.表達(dá)式3* 2(4+2*2-6*3)-5求值過程中當(dāng)掃描

3、到6時(shí)，對象棧和算符棧為（），其中為乘冪 。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á)式中左，右括號是否配對出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu)B.隊(duì)列C.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)D.?！疚靼搽娮涌萍即髮W(xué)1996一、6（2分）】22.用鏈接方式存儲的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（）?！颈狈浇煌ù髮W(xué)2001一、12（2分）】A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改23.用不帶頭結(jié)點(diǎn)的單鏈表存儲隊(duì)列時(shí),其隊(duì)頭指針指

4、向隊(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ù)組Am存放循環(huán)隊(duì)列的元素,其頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（）?！颈本┕ど檀髮W(xué)2001一、2（3分）】A(rear-front+m)%mBrear-front+1C(front-rear+m)%mD(rear-front)%m2

5、6.循環(huán)隊(duì)列A0.m-1存放其元素值，用front和rear分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素?cái)?shù)是()?！灸暇├砉ご髮W(xué)2001一、5（1.5分）】A. (rear-front+m)%mB. rear-front+1C.rear-front-1D.rear-front27.循環(huán)隊(duì)列存儲在數(shù)組A0.m中，則入隊(duì)時(shí)的操作為（）?！局猩酱髮W(xué)1999一、6（1分）】A. rear=rear+1B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod mD. rear=(rear+1)mod(m+1)28.若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和fro

6、nt的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？()【浙江大學(xué)1999四、1(4分)】A.1和5B.2和4C.4和2D.5和129.已知輸入序列為abcd經(jīng)過輸出受限的雙向隊(duì)列后能得到的輸出序列有（）。A. dacbB. cadbC. dbcaD. bdacE.以上答案都不對【西安交通大學(xué)1996三、3 (3分)】30.若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是()?！疚靼搽娮涌萍即髮W(xué)1996一、5（2分）】A. 1234B. 4132C. 4231D. 421331.最大

7、容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是（）。A. (rear+1) MOD n=frontB. rear=frontCrear+1=frontD. (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ì)列序列。【北

8、方交通大學(xué)1999一、1（5分）】,: 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,4B. 3,2,4,1C. 4,2,3,1D. 4,3,2,1F. 1,2,3,4G. 1,3,2,434.棧和隊(duì)都是（）【南京理工大學(xué)1997一、3（2分）】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，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是

9、e2，e4，e3,e6,e5,e1則棧S的容量至少應(yīng)該是()。A6B. 4C. 3D. 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)行，則棧空時(shí)彈出的元素構(gòu)成的序列是以下哪些序列？ 【哈爾濱工業(yè)大學(xué)2000七（8分）】Ad，e，c，f，b，g，aB. f，e，g，d，a，c，bC. e，f，d，g，b，c，aD. c，d，b，e，f，a，g二判斷題1.消除遞歸不一定需要使用棧，此說法

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

11、，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è)棧可以輸出序列1，5，4，6，2，3。（）【上海海運(yùn)學(xué)院1999一、3（1分）】11.任何一個(gè)遞歸過程都可以轉(zhuǎn)換成非遞歸過程。（）【上海交通大

12、學(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

13、分）】18.隊(duì)列和棧都是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)行運(yùn)算。（ ）【長沙鐵道學(xué)院1997一、5(1分)】19.棧和隊(duì)列都是線性表，只是在插入和刪除時(shí)受到了一些限制。（）【北京郵電大學(xué)2002一、3(1分)】20.棧和隊(duì)列的存儲方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞?。（）【上海海運(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則不可能的棧輸出序列是_?！局袊嗣翊髮W(xué)2001一、1(2分)】4.設(shè)

14、有一個(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è)棧共享一存儲區(qū)時(shí)，棧利用一維數(shù)組stack(1,n)表示，兩棧頂指針為top1與top2，則當(dāng)棧1空時(shí)，top1為_，棧2空時(shí) ，top2為_，棧滿時(shí)為_?！灸暇├砉ご髮W(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)先判別棧

15、是否_(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í)，最好用_作為存儲結(jié)構(gòu)?！灸暇├砉ご髮W(xué)2001二、7（2分）】9用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為_?！疚髂辖煌ù髮W(xué)2000一、5】10.順序棧用data1.n存儲數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作是_?！竞戏使I(yè)

16、大學(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語言的考生不填）?！疚髂辖煌ù髮W(xué)2000一、7】14_又稱作先進(jìn)先出表?！局貞c大學(xué)2000一、7】15.隊(duì)列的特點(diǎn)是_?！颈本├砉ご髮W(xué)2000二、2（2分）】16隊(duì)列是限制插入只能在表的

17、一端，而刪除在表的另一端進(jìn)行的線性表，其特點(diǎn)是_?！颈狈浇煌ù髮W(xué)2001二、5】17.已知鏈隊(duì)列的頭尾指針分別是f和r，則將值x入隊(duì)的操作序列是_?！竞戏使I(yè)大學(xué)2000三、3（2分）】18區(qū)分循環(huán)隊(duì)列的滿與空，只有兩種方法，它們是_和_。【北京郵電大學(xué)2001二、2（4分）】19設(shè)循環(huán)隊(duì)列用數(shù)組A1.M表示，隊(duì)首、隊(duì)尾指針分別是FRONT和TAIL，判定隊(duì)滿的條件為_?！旧綎|工業(yè)大學(xué)1995一、1（1分）】20.設(shè)循環(huán)隊(duì)列存放在向量sq.data0:M中，則隊(duì)頭指針sq.front在循環(huán)意義下的出隊(duì)操作可表示為_，若用犧牲一個(gè)單元的辦法來區(qū)分隊(duì)滿和隊(duì)空（設(shè)隊(duì)尾指針sq.rear）,則隊(duì)滿的條

18、件為_?！鹃L沙鐵道學(xué)院1997二、4 (4分)】21表達(dá)式求值是_應(yīng)用的一個(gè)典型例子?！局貞c大學(xué)2000一、10】22循環(huán)隊(duì)列用數(shù)組A0.m-1存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列的元素個(gè)數(shù)是_。【廈門大學(xué)2000六、1（16%/3分）】23設(shè)Q0.N-1為循環(huán)隊(duì)列，其頭、尾指針分別為P和R，則隊(duì)Q中當(dāng)前所含元素個(gè)數(shù)為_?！颈本┛萍即髮W(xué)1997一、4】24完善下面算法?！局猩酱髮W(xué)1998四、2（6分）】后綴表達(dá)式求值，表達(dá)式13/25+61的后綴表達(dá)式格式為：13, 25/61, +FUNCcompute(a):real;后綴表達(dá)式存儲在數(shù)組a1.m中。BEGIN

19、setnull(s)；i:=1；ch:=(1)_；WHILE ch DOBEGINCASE ch OF0.9:x:=0;WHILE ch,DOBEGINx:=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;ENDCASEpush(s,x)；i:=i+1；ch:=ai；END;comput:=(3)_；END;25.算術(shù)表達(dá)式求值的流程，其中OPTR為算術(shù)符棧，OPND為操作數(shù)棧，prec

20、ede(oper1，oper2)是比較運(yùn)算符優(yōu)先級別的函數(shù)，operate(opnd1,oper,opnd2)為兩操作數(shù)的運(yùn)算結(jié)果函數(shù)。（#表示運(yùn)算起始和終止符號）【西北工業(yè)大學(xué)1999六、2 (7分)】FUNCTIONexp_reduced:operandtype;INITSTACK(OPTR);PUSH(OPTR#)；INITSTACK(OPND);read(w)；WHILENOT(w=#) AND (GETTOP(OPTR)=#) DOIF NOT w in op THEN PUSH(OPND,w);ELSE CASE precede(GETTOP(OPTR),w)OF:theta:=P

21、OP(OPTR);b:=POP(OPND);a:=POP(OPND);(3)_；ENDC;RETURN(GETTOP(OPND);ENDF;26根據(jù)需要，用適當(dāng)?shù)恼Z句填入下面算法的_中：問題：設(shè)有n件物品，重量分別為w1,w2,w3,wn和一個(gè)能裝載總重量為T的背包。能否從n件物品中選擇若干件恰好使它們的重量之和等于T。若能，則背包問題有解，否則無解。解此問題的算法如下：FUNCTION kanp_stack(VAR stack,w:ARRAY1.n OF real; VAR top:integer; T:real):boolean;w1：n存放n件物品的重量，依次從中取出物品放入背包中，檢查

22、背包重量，若不超過T，則裝入，否則棄之，取下一個(gè)物品試之。若有解則返回函數(shù)值true,否則返回falseBEGINtop:=0;i:=1; i指示待選物品WHILE(1)_ AND(2)_DOIF(3)_ OR(4)_ AND (i0)THENi:=(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)

23、隊(duì)列？【哈爾濱工業(yè)大學(xué)2001三、2（3分）】【河南大學(xué)1998一、4（3分）】4.假設(shè)以S和X分別表示入棧和出棧操作，則對初態(tài)和終態(tài)均為空的棧操作可由S和X組成的序列表示（如SXSX）。（1）試指出判別給定序列是否合法的一般規(guī)則。（2）兩個(gè)不同合法序列（對同一輸入序列）能否得到相同的輸出元素序列？如能得到，請舉列說明?！緰|南大學(xué)1992二 （10分）】5.有5個(gè)元素，其入棧次序?yàn)椋篈，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è)序列

24、:4 3 5 6 1 2和1 3 5 4 2 6;請說明為什么不能或如何才能得到?！疚錆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è)不能得到的輸出序列?！颈本┛萍即髮W(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得到輸出序列

25、為P1,P2,Pn（它是輸入序列的一個(gè)排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著ijk,使PjPk0 THENBEGINp(w-1);writeln(w);輸出Wp(w-1）END；END；【西北大學(xué)2001三、7】17.用一個(gè)數(shù)組S（設(shè)大小為MAX）作為兩個(gè)堆棧的共享空間。請說明共享方法，棧滿/?？盏呐袛鄺l件，并用C或PASCAL設(shè)計(jì)公用的入棧操作push（i，x），其中i為0或1，用于表示棧號，x為入棧值?！菊憬髮W(xué)1998五、2 (7分)】18.簡述下列程序段的功能。PROCalgo(VAR S : stack;k:integer);VART: stack; temp: inte

26、ger;WHILE NOTempty(S) DOtemp:=POP(S); IF tempkTHEN PUSH(T,temp);WHILE NOTempty(T)DOtemp:=POP(T);PUSH(S,temp);【山東科技大學(xué)2002一、1（4分）】19.用棧實(shí)現(xiàn)將中綴表達(dá)式8-(3+5)*(5-6/2)轉(zhuǎn)換成后綴表達(dá)式，畫出棧的變化過程圖?！灸暇┖娇蘸教齑髮W(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.

27、有遞歸算法如下：FUNCTIONsum (n:integer):intger;BEGINIF n=0 THEN sum:=0ELSE 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.畫出對算術(shù)表達(dá)式A-B*C/D-EF求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程?！緰|南大學(xué)2000一、3（6分）】23.計(jì)算算術(shù)表達(dá)式的值時(shí)，可用兩個(gè)棧作輔助工

28、具。對于給出的一個(gè)表達(dá)式，從左向右掃描它的字符，并將操作數(shù)放入棧S1中，運(yùn)算符放入棧S2中，但每次掃描到運(yùn)算符時(shí)，要把它同S2的棧頂運(yùn)算符進(jìn)行優(yōu)先級比較，當(dāng)掃描到的運(yùn)算符的優(yōu)先級不高于棧頂運(yùn)算符的優(yōu)先級時(shí)，取出棧S1的棧頂和次棧頂?shù)膬蓚€(gè)元素，以及棧S2的棧頂運(yùn)算符進(jìn)行運(yùn)算將結(jié)果放入棧S1中（得到的結(jié)果依次用T1、T2等表示）。為方便比較，假設(shè)棧S2的初始棧頂為（運(yùn)算符的優(yōu)先級低于加、減、乘、除中任何一種運(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/y2,利用棧，給出將次序改為3y-*ay

29、2/-的操作步驟。（可用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使用，怎樣分配這部分存儲空間，使得對任一個(gè)棧，僅當(dāng)這部分空間全滿時(shí)才發(fā)生上溢?！緰|北大學(xué)2000一、1 (3分)】26.將兩個(gè)棧存入數(shù)組V1.m應(yīng)如何安排最好？這時(shí)棧空、棧滿的條件是什么？【東南大學(xué)1998一、5】27.在一個(gè)算法中需要建立多個(gè)堆棧時(shí)可以選用下列三種方案之一，試問：這三種方案之間相比較各有什么優(yōu)缺

30、點(diǎn)？（1）分別用多個(gè)順序存儲空間建立多個(gè)獨(dú)立的堆棧；（2）多個(gè)堆棧共享一個(gè)順序存儲空間；（3）分別建立多個(gè)獨(dú)立的鏈接堆棧?！颈本┖娇蘸教齑髮W(xué)1998一、6（4分）】28在某程序中，有兩個(gè)棧共享一個(gè)一維數(shù)組空間SPACEN、SPACE0、SPACEN-1分別是兩個(gè)棧的棧底。（1）對棧1、棧2，試分別寫出（元素x）入棧的主要語句和出棧的主要語句。（2）對棧1、棧2，試分別寫出棧滿、?？盏臈l件?！颈本├砉ご髮W(xué)1999二、2（8分）】29.簡述順序存儲隊(duì)列的假溢出的避免方法及隊(duì)列滿和空的條件?！旧綎|大學(xué)2000一、2 (4分)】30.舉例說明順序隊(duì)的“假溢出”現(xiàn)象，并給出解決方案?！靖Ｖ荽髮W(xué)1998三

31、、5 (6分)】31.怎樣判定循環(huán)隊(duì)列的空和滿？【燕山大學(xué)1999二、3（4分）】32.簡要敘述循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，并寫出其初始狀態(tài)、隊(duì)列空、隊(duì)列滿時(shí)的隊(duì)首指針與隊(duì)尾指針的值?！灸暇┖娇蘸教齑髮W(xué)1995七（5分）】33.利用兩個(gè)棧sl,s2模擬一個(gè)隊(duì)列時(shí)，如何用棧的運(yùn)算實(shí)現(xiàn)隊(duì)列的插入，刪除以及判隊(duì)空運(yùn)算。請簡述這些運(yùn)算的算法思想?！颈本┼]電大學(xué)1992一、1】【東南大學(xué)1999一、1（7分）】34一個(gè)循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)描述如下：TYPE sequeuetp=RECORDelem：ARRAY1.MAXSIZE OF elemtp；front，rear：0.MAXSIZE；END；給出循環(huán)隊(duì)列的隊(duì)

32、空和隊(duì)滿的判斷條件，并且分析一下該條件對隊(duì)列實(shí)際存儲空間大小的影響，如果為了不損失存儲空間，你如何改進(jìn)循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿的判斷條件？【西北工業(yè)大學(xué)1999三(8分)】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分）【東北大學(xué)2002一、1】36.給出循環(huán)隊(duì)列中元素個(gè)數(shù)的計(jì)算式(設(shè)隊(duì)最大長度為N,隊(duì)首指針FRONT，隊(duì)尾指針REAR)【西北大學(xué)2000二、7 (5分)】37.順序隊(duì)列

33、一般應(yīng)該組織成為環(huán)狀隊(duì)列的形式，而且一般隊(duì)列頭或尾其中之一應(yīng)該特殊處理。例如，隊(duì)列為listarray0.n-1，隊(duì)列頭指針為front，隊(duì)列尾指針為rear， 則listarray rear表示下一個(gè)可以插入隊(duì)列的位置。請解釋其原因。【北京大學(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ì)列得到的輸出序列；

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

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

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

37、OOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（2）通過對（1）的分析，寫出一個(gè)算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。【武漢大學(xué)2000五、2】6.設(shè)計(jì)一個(gè)算法，判斷一個(gè)算術(shù)表達(dá)式中的括號是否配對。算術(shù)表達(dá)式保存在帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)域：ch和link，其中ch域?yàn)樽址愋??！灸暇┼]電大學(xué)2000五】7.請利用兩個(gè)棧S1和S2來模擬一個(gè)隊(duì)列。已知棧的三個(gè)運(yùn)算定義如下：PUSH(ST,x):元素x入ST棧；POP(ST,x)：ST棧頂元素出棧，賦給變量x；Sempty(ST)：

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

39、(Stack:Stacktype):Boolean;FUNCTIONEmpty(Stack:Stacktype)Boolean;現(xiàn)用此二棧構(gòu)成一個(gè)隊(duì)列，試寫出下面入隊(duì)列、出隊(duì)列操作算法：PROCEDUREEnQueue(x:Datatype);FUNCTIONDeQueue: 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)鏈

40、表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針，如圖所示（編者略），請寫出相應(yīng)的入隊(duì)列和出隊(duì)列算法。【西安電子科技大學(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），請給出這種隊(duì)列的入隊(duì)和出隊(duì)操作的實(shí)現(xiàn)過程?！旧綎|科技大學(xué)2002一、2（6分）】12.雙端隊(duì)列（duque）是一個(gè)可以在任一端進(jìn)行插入和刪除的線性表?，F(xiàn)采用一個(gè)一維數(shù)組作為雙端隊(duì)列的數(shù)據(jù)存儲結(jié)構(gòu)，使用類PASCAL語言描述如下：CONST maxsize=32;數(shù)組中可