第3章棧和隊(duì)列一選擇題1.對(duì)于棧操作數(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ā)生上溢,則說(shuō)明該棧的最大容量為(③)。為了增加內(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.長(zhǎng)度B.深度C.棧頂D.棧底⑤:A.兩個(gè)棧的棧頂同時(shí)到達(dá)棧空間的中心點(diǎn).B.其中一個(gè)棧的棧頂?shù)竭_(dá)棧空間的中心點(diǎn).C.兩個(gè)棧的棧頂在棧空間的某一位置相遇.D.兩個(gè)棧均不空,且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底.【上海海運(yùn)學(xué)院1997二、1(5分)】【上海海運(yùn)學(xué)院1999二、1(5分)】3.一個(gè)棧的輸入序列為123…n,若輸出序列的第一個(gè)元素是n,輸出第i(1<=i<=n)個(gè)元素是()。A.不確定B.n-i+1C.iD.n-i【中山大學(xué)1999一、9(1分)】4.若一個(gè)棧的輸入序列為1,2,3,…,n,輸出序列的第一個(gè)元素是i,則第j個(gè)輸出元素是()。A.i-j-1B.i-jC.j-i+1D.不確定的【武漢大學(xué)2000二、3】5.若已知一個(gè)棧的入棧序列是1,2,3,…,n,其輸出序列為p1,p2,p3,…,pN,若pN是n,則pi是()。A.iB.n-iC.n-i+1D.不確定【南京理工大學(xué)2001一、1(1.5分)】6.有六個(gè)元素6,5,4,3,2,1的順序進(jìn)棧,問(wèn)下列哪一個(gè)不是合法的出棧序列?()A.543612B.453126C.346521D.234156【北方交通大學(xué)2001一、3(2分)】7.設(shè)棧的輸入序列是1,2,3,4,則()不可能是其出棧序列。【中科院計(jì)算所2000一、10(2分)】A.1,2,4,3,B.2,1,3,4,C.1,4,3,2,D.4,3,1,2,E.3,2,1,4,8.一個(gè)棧的輸入序列為12345,則下列序列中不可能是棧的輸出序列的是()。A.23415B.54132C.23145D.15432【南開(kāi)大學(xué)2000一、1】【山東大學(xué)2001二、4(1分)】【北京理工大學(xué)2000一、2(2分)】9.設(shè)一個(gè)棧的輸入序列是1,2,3,4,5,則下列序列中,是棧的合法輸出序列的是()。A.51234B.45132C.43125D.32154【合肥工業(yè)大學(xué)2001一、1(2分)】10.某堆棧的輸入序列為a,b,c,d,下面的四個(gè)序列中,不可能是它的輸出序列的是()。A.a,c,b,dB.b,c,d,aC.c,d,b,aD.d,c,a,b【北京航空航天大學(xué)2000一、3(2分)】【北京郵電大學(xué)1999一、3(2分)】11.設(shè)abcdef以所給的次序進(jìn)棧,若在進(jìn)棧操作時(shí),允許退棧操作,則下面得不到的序列為()。A.fedcbaB.bcafedC.dcefbaD.cabdef【南京理工大學(xué)1996一、9(2分)】12.設(shè)有三個(gè)元素X,Y,Z順序進(jìn)棧(進(jìn)的過(guò)程中允許出棧),下列得不到的出棧排列是()。A.XYZB.YZXC.ZXYD.ZYX【南京理工大學(xué)1997一、5(2分)】13.輸入序列為ABC,可以變?yōu)镃BA時(shí),經(jīng)過(guò)的棧操作為()【中山大學(xué)1999一、8(1分)】A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop14.若一個(gè)棧以向量V[1..n]存儲(chǔ),初始棧頂指針top為n+1,則下面x進(jìn)棧的正確操作是()。A.top:=top+1;V[top]:=xB.V[top]:=x;top:=top+1C.top:=top-1;V[top]:=xD.V[top]:=x;top:=top-1【南京理工大學(xué)1998一、13(2分)】15.若棧采用順序存儲(chǔ)方式存儲(chǔ),現(xiàn)兩棧共享空間V[1..m],top[i]代表第i個(gè)棧(i=1,2)棧頂,棧1的底在v[1],棧2的底在V[m],則棧滿的條件是()。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]【南京理工大學(xué)1999一、14(1分)】16.棧在()中應(yīng)用。【中山大學(xué)1998二、3(2分)】A.遞歸調(diào)用B.子程序調(diào)用C.表達(dá)式求值D.A,B,C17.一個(gè)遞歸算法必須包括()。【武漢大學(xué)2000二、2】A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分18.執(zhí)行完下列語(yǔ)句段后,i值為:()【浙江大學(xué)2000一、6(3分)】intf(intx){return((x>0)?x*f(x-1):2);}inti;i=f(f(1));A.2B.4C.8D.無(wú)限遞歸19.表達(dá)式a*(b+c)-d的后綴表達(dá)式是()。【南京理工大學(xué)2001一、2(1.5分)】A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd20.表達(dá)式3*2^(4+2*2-6*3)-5求值過(guò)程中當(dāng)掃描到6時(shí),對(duì)象棧和算符棧為(),其中^為乘冪。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á)式中左,右括號(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.棧【西安電子科技大學(xué)1996一、6(2分)】22.用鏈接方式存儲(chǔ)的隊(duì)列,在進(jìn)行刪除運(yùn)算時(shí)()。【北方交通大學(xué)2001一、12(2分)】A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改23.用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn),則在進(jìn)行刪除操作時(shí)()。【北京理工大學(xué)2001六、3(2分)】A.僅修改隊(duì)頭指針B.僅修改隊(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.線性表【福州大學(xué)1998一、1(2分)】25.假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素,其頭尾指針?lè)謩e為front和rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為()。【北京工商大學(xué)2001一、2(3分)】A.(rear-front+m)%mB.rear-front+1C.(front-rear+m)%mD.(rear-front)%m26.循環(huán)隊(duì)列A[0..m-1]存放其元素值,用front和rear分別表示隊(duì)頭和隊(duì)尾,則當(dāng)前隊(duì)列中的元素?cái)?shù)是()。【南京理工大學(xué)2001一、5(1.5分)】A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front27.循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中,則入隊(duì)時(shí)的操作為()。【中山大學(xué)1999一、6(1分)】A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.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的值分別為多少?()【浙江大學(xué)1999四、1(4分)】A.1和5B.2和4C.4和2D.5和129.已知輸入序列為abcd經(jīng)過(guò)輸出受限的雙向隊(duì)列后能得到的輸出序列有()。A.dacbB.cadbC.dbcaD.bdacE.以上答案都不對(duì)【西安交通大學(xué)1996三、3(3分)】30.若以1234作為雙端隊(duì)列的輸入序列,則既不能由輸入受限的雙端隊(duì)列得到,也不能由輸出受限的雙端隊(duì)列得到的輸出序列是()。【西安電子科技大學(xué)1996一、5(2分)】A.1234B.4132C.4231D.421331.最大容量為n的循環(huán)隊(duì)列,隊(duì)尾指針是rear,隊(duì)頭是front,則隊(duì)空的條件是()。A.(rear+1)MODn=frontB.rear=frontC.rear+1=frontD.(rear-l)MODn=front【南京理工大學(xué)1999一、16(2分)】32.棧和隊(duì)列的共同點(diǎn)是()。【燕山大學(xué)2001一、1(2分)】A.都是先進(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ì)列序列。【北方交通大學(xué)1999一、1(5分)】①,②: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,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.順序存儲(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.6B.4C.3D.2【南京理工大學(xué)2000一、6(1.5分)】36.用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的()位置。【清華大學(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分)】A.{d,e,c,f,b,g,a}B.{f,e,g,d,a,c,b}C.{e,f,d,g,b,c,a}D.{c,d,b,e,f,a,g}二判斷題1.消除遞歸不一定需要使用棧,此說(shuō)法()【中科院計(jì)算所1998二、2(2分)】【中國(guó)科技大學(xué)1998二、2(2分)】2.棧是實(shí)現(xiàn)過(guò)程和函數(shù)等子程序所必需的結(jié)構(gòu)。()【合肥工業(yè)大學(xué)2000二、2(1分)】3.兩個(gè)棧共用靜態(tài)存儲(chǔ)空間,對(duì)頭使用也存在空間溢出問(wèn)題。()【青島大學(xué)2000四、2(1分)】4.兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí),為提高內(nèi)存利用率,減少溢出機(jī)會(huì),應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。()【上海海運(yùn)學(xué)院1998一、4(1分)】5.即使對(duì)不含相同元素的同一輸入序列進(jìn)行兩組不同的合法的入棧和出棧組合操作,所得的輸出序列也一定相同。()【北京郵電大學(xué)1999二、4(2分)】6.有n個(gè)數(shù)順序(依次)進(jìn)棧,出棧序列有Cn種,Cn=[1/(n+1)]*(2n)!/[(n!)*(n!)]。()【北京郵電大學(xué)1998一、3(2分)】7.棧與隊(duì)列是一種特殊操作的線性表。()【青島大學(xué)2001四、3(1分)】8.若輸入序列為1,2,3,4,5,6,則通過(guò)一個(gè)棧可以輸出序列3,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,則通過(guò)一個(gè)棧可以輸出序列1,5,4,6,2,3。()【上海海運(yùn)學(xué)院1999一、3(1分)】11.任何一個(gè)遞歸過(guò)程都可以轉(zhuǎn)換成非遞歸過(guò)程。()【上海交通大學(xué)1998一、3(1分)】12.只有那種使用了局部變量的遞歸過(guò)程在轉(zhuǎn)換成非遞歸過(guò)程時(shí)才必須使用棧。()【上海交通大學(xué)1998一、4(1分)】13.隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表,是一種先進(jìn)后出型結(jié)構(gòu)。()【上海海運(yùn)學(xué)院1998一、3(1分)】14.通常使用隊(duì)列來(lái)處理函數(shù)或過(guò)程的調(diào)用。()【南京航空航天大學(xué)1997一、5(1分)】15.隊(duì)列邏輯上是一個(gè)下端和上端既能增加又能減少的線性表。()【上海交通大學(xué)1998一、2】16.循環(huán)隊(duì)列通常用指針來(lái)實(shí)現(xiàn)隊(duì)列的頭尾相接。()【南京航空航天大學(xué)1996六、1(1分)】17.循環(huán)隊(duì)列也存在空間溢出問(wèn)題。()【青島大學(xué)2002一、2(1分)】18.隊(duì)列和棧都是運(yùn)算受限的線性表,只允許在表的兩端進(jìn)行運(yùn)算。()【長(zhǎng)沙鐵道學(xué)院1997一、5(1分)】19.棧和隊(duì)列都是線性表,只是在插入和刪除時(shí)受到了一些限制。()【北京郵電大學(xué)2002一、3(1分)】20.棧和隊(duì)列的存儲(chǔ)方式,既可以是順序方式,又可以是鏈?zhǔn)椒绞健?)【上海海運(yùn)學(xué)院1996一、2(1分)1999一、2(1分)】三填空題1.棧是_______的線性表,其運(yùn)算遵循_______的原則。【北京科技大學(xué)1997一、3】2._______是限定僅在表尾進(jìn)行插入或刪除操作的線性表。【燕山大學(xué)1998一、3(1分)】3.一個(gè)棧的輸入序列是:1,2,3則不可能的棧輸出序列是_______。【中國(guó)人民大學(xué)2001一、1(2分)】4.設(shè)有一個(gè)空棧,棧頂指針為1000H(十六進(jìn)制),現(xiàn)有輸入序列為1,2,3,4,5,經(jīng)過(guò)PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后,輸出序列是_______,而棧頂指針值是_______H。設(shè)棧為順序棧,每個(gè)元素占4個(gè)字節(jié)。【西安電子科技大學(xué)1998二、1(4分)】5.當(dāng)兩個(gè)棧共享一存儲(chǔ)區(qū)時(shí),棧利用一維數(shù)組stack(1,n)表示,兩棧頂指針為top[1]與top[2],則當(dāng)棧1空時(shí),top[1]為_(kāi)______,棧2空時(shí),top[2]為_(kāi)______,棧滿時(shí)為_(kāi)______。【南京理工大學(xué)1997三、1(3分)】6.兩個(gè)棧共享空間時(shí)棧滿的條件_______。【中山大學(xué)1998一、3(1分)】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)將兩棧的_(4)_分別設(shè)在內(nèi)存空間的兩端,這樣只有當(dāng)_(5)_時(shí)才產(chǎn)生溢出。【山東工業(yè)大學(xué)1994一、1(5分)】8.多個(gè)棧共存時(shí),最好用_______作為存儲(chǔ)結(jié)構(gòu)。【南京理工大學(xué)2001二、7(2分)】9.用S表示入棧操作,X表示出棧操作,若元素入棧的順序?yàn)?234,為了得到1342出棧順序,相應(yīng)的S和X的操作串為_(kāi)______。【西南交通大學(xué)2000一、5】10.順序棧用data[1..n]存儲(chǔ)數(shù)據(jù),棧頂指針是top,則值為x的元素入棧的操作是_______。【合肥工業(yè)大學(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ì)列的引入,目的是為了克服_______。【廈門大學(xué)2001一、1(14/8分)】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=_______(填C語(yǔ)言,PASCAL語(yǔ)言的考生不填)。【西南交通大學(xué)2000一、7】14.________又稱作先進(jìn)先出表。【重慶大學(xué)2000一、7】15.隊(duì)列的特點(diǎn)是_______。【北京理工大學(xué)2000二、2(2分)】16.隊(duì)列是限制插入只能在表的一端,而刪除在表的另一端進(jìn)行的線性表,其特點(diǎn)是_______。【北方交通大學(xué)2001二、5】17.已知鏈隊(duì)列的頭尾指針?lè)謩e是f和r,則將值x入隊(duì)的操作序列是_______。【合肥工業(yè)大學(xué)2000三、3(2分)】18.區(qū)分循環(huán)隊(duì)列的滿與空,只有兩種方法,它們是______和______。【北京郵電大學(xué)2001二、2(4分)】19.設(shè)循環(huán)隊(duì)列用數(shù)組A[1..M]表示,隊(duì)首、隊(duì)尾指針?lè)謩e是FRONT和TAIL,判定隊(duì)滿的條件為_(kāi)______。【山東工業(yè)大學(xué)1995一、1(1分)】20.設(shè)循環(huán)隊(duì)列存放在向量sq.data[0:M]中,則隊(duì)頭指針sq.front在循環(huán)意義下的出隊(duì)操作可表示為_(kāi)______,若用犧牲一個(gè)單元的辦法來(lái)區(qū)分隊(duì)滿和隊(duì)空(設(shè)隊(duì)尾指針sq.rear),則隊(duì)滿的條件為_(kāi)______。【長(zhǎng)沙鐵道學(xué)院1997二、4(4分)】21.表達(dá)式求值是_______應(yīng)用的一個(gè)典型例子。【重慶大學(xué)2000一、10】22.循環(huán)隊(duì)列用數(shù)組A[0..m-1]存放其元素值,已知其頭尾指針?lè)謩e是front和rear,則當(dāng)前隊(duì)列的元素個(gè)數(shù)是_______。【廈門大學(xué)2000六、1(16%/3分)】23.設(shè)Q[0..N-1]為循環(huán)隊(duì)列,其頭、尾指針?lè)謩e為P和R,則隊(duì)Q中當(dāng)前所含元素個(gè)數(shù)為_(kāi)______。【北京科技大學(xué)1997一、4】24.完善下面算法。【中山大學(xué)1998四、2(6分)】后綴表達(dá)式求值,表達(dá)式13/25+61的后綴表達(dá)式格式為:13,25/61,+FUNCcompute(a):real;后綴表達(dá)式存儲(chǔ)在數(shù)組a[1..m]中。BEGINsetnull(s);i:=1;ch:=(1)______;WHILEch<>’@’DOBEGINCASEchOF‘0’..‘9’:x:=0;WHILEch<>’,’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:=a[i];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)算起始和終止符號(hào))【西北工業(yè)大學(xué)1999六、2(7分)】FUNCTIONexp_reduced:operandtype;INITSTACK(OPTR);PUSH(OPTR"#");INITS