第三部分考研真題精選一選擇題1.對(duì)于棧操作數(shù)據(jù)的原則是（）。A.先進(jìn)先出B.后進(jìn)先出C.后進(jìn)后出D.不分順序2.在作進(jìn)棧運(yùn)算時(shí),應(yīng)先判別棧是否(=1\*GB3①),在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否(=2\*GB3②)。當(dāng)棧中元素為n個(gè),作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說(shuō)明該棧的最大容量為(=3\*GB3③)。為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí),應(yīng)將兩棧的(=4\*GB3④)分別設(shè)在這片內(nèi)存空間的兩端,這樣,當(dāng)(=5\*GB3⑤)時(shí)，才產(chǎn)生上溢。=1\*GB3①,=2\*GB3②:A.空B.滿C.上溢D.下溢=3\*GB3③:A.n-1B.nC.n+1D.n/2=4\*GB3④:A.長(zhǎng)度B.深度C.棧頂D.棧底=5\*GB3⑤:A.兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn).B.其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn).C.兩個(gè)棧的棧頂在?？臻g的某一位置相遇.D.兩個(gè)棧均不空,且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底.3.一個(gè)棧的輸入序列為123…n，若輸出序列的第一個(gè)元素是n，輸出第i（1<=i<=n）個(gè)元素是（）。A.不確定B.n-i+1C.iD.n-i4.若一個(gè)棧的輸入序列為1,2,3,…,n，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是（）。A.i-j-1B.i-jC.j-i+1D.不確定的5.若已知一個(gè)棧的入棧序列是1,2,3,…,n，其輸出序列為p1,p2,p3，…，pN,若pN是n，則pi是()。A.iB.n-iC.n-i+1D.不確定6.有六個(gè)元素6，5，4，3，2，1的順序進(jìn)棧，問(wèn)下列哪一個(gè)不是合法的出棧序列？（）A.543612B.453126C.346521D.2341567.設(shè)棧的輸入序列是1，2，3，4,則（）不可能是其出棧序列。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.154329.設(shè)一個(gè)棧的輸入序列是1，2，3，4，5,則下列序列中，是棧的合法輸出序列的是（）。A.51234B.45132C.43125D.3215410.某堆棧的輸入序列為a,b，c，d,下面的四個(gè)序列中，不可能是它的輸出序列的是（）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b11.設(shè)abcdef以所給的次序進(jìn)棧，若在進(jìn)棧操作時(shí)，允許退棧操作,則下面得不到的序列為（）。A．fedcbaB.bcafedC.dcefbaD.cabdef12.設(shè)有三個(gè)元素X，Y，Z順序進(jìn)棧（進(jìn)的過(guò)程中允許出棧），下列得不到的出棧排列是()。A．XYZB.YZXC.ZXYD.ZYX13.輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過(guò)的棧操作為（）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-115.若棧采用順序存儲(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]16.棧在（）中應(yīng)用。A.遞歸調(diào)用B.子程序調(diào)用C.表達(dá)式求值D.A，Ｂ，Ｃ17.一個(gè)遞歸算法必須包括（）。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分18.執(zhí)行完下列語(yǔ)句段后，i值為：（）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á)式是()。A．a(chǎn)bcd*+-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；(*^(-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.僅修改隊(duì)尾指針C.隊(duì)頭、隊(duì)尾指針都要修改D.隊(duì)頭,隊(duì)尾指針都可能要修改24.遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱(chēng)為（）的數(shù)據(jù)結(jié)構(gòu)。A．隊(duì)列B．多維數(shù)組C．棧D.線性表25.假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素,其頭尾指針?lè)謩e為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（）。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ù)是()。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front27.循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為（）。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的值分別為多少？()A.1和5B.2和4C.4和2D.5和129.已知輸入序列為abcd經(jīng)過(guò)輸出受限的雙向隊(duì)列后能得到的輸出序列有（）。A.dacbB.cadbC.dbcaD.bdacE.以上答案都不對(duì)30.若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是()。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=front32.棧和隊(duì)列的共同點(diǎn)是（）。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ì)列序列。①,②: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ì)都是（）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.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)?；驈棗＃绱诉M(jìn)行，則?？諘r(shí)彈出的元素構(gòu)成的序列是以下哪些序列？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ō)法（）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/（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ò)程。（）【上海交通大學(xué)1998=1\*CHINESENUM3一、3（1分）】12.只有那種使用了局部變量的遞歸過(guò)程在轉(zhuǎn)換成非遞歸過(guò)程時(shí)才必須使用棧。（）13.隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。（）14.通常使用隊(duì)列來(lái)處理函數(shù)或過(guò)程的調(diào)用。（）15.隊(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，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)表示，兩棧頂指針為top[1]與top[2]，則當(dāng)棧1空時(shí)，top[1]為_(kāi)______，棧2空時(shí)，top[2]為_(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)將兩棧的_(4)_分別設(shè)在內(nèi)存空間的兩端，這樣只有當(dāng)_(5)_時(shí)才產(chǎn)生溢出?！?.多個(gè)棧共存時(shí)，最好用_______作為存儲(chǔ)結(jié)構(gòu)。9．用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為_(kāi)______。10.順序棧用data[1..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=_______（填C語(yǔ)言，PASCAL語(yǔ)言的考生不填）。14．________又稱(chēng)作先進(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ù)組A[1..M]表示，隊(duì)首、隊(duì)尾指針?lè)謩e是FRONT和TAIL，判定隊(duì)滿的條件為_(kāi)______。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)______。21．表達(dá)式求值是_______應(yīng)用的一個(gè)典型例子。22．循環(huán)隊(duì)列用數(shù)組A[0..m-1]存放其元素值，已知其頭尾指針?lè)謩e是front和rear，則當(dāng)前隊(duì)列的元素個(gè)數(shù)是_______。23．設(shè)Q[0..N-1]為循環(huán)隊(duì)列，其頭、尾指針?lè)謩e為P和R，則隊(duì)Q中當(dāng)前所含元素個(gè)數(shù)為_(kāi)______。四應(yīng)用題1.名詞解釋?zhuān)簵！?.名詞解釋?zhuān)宏?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è)元素，其入棧次序?yàn)椋篈，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個(gè)且D第二個(gè)出棧）的次序有哪幾個(gè)？6.如果輸入序列為123456,試問(wèn)能否通過(guò)棧結(jié)構(gòu)得到以下兩個(gè)序列:435612和135426;請(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,試寫(xiě)出借助一個(gè)?？傻玫降膬蓚€(gè)輸出序列和兩個(gè)不能得到的輸出序列。9.設(shè)輸入序列為2，3，4，5，6，利用一個(gè)棧能得到序列2，5，3，4，6嗎？棧可以用單鏈表實(shí)現(xiàn)嗎？10.試證明：若借助棧由輸入序列1,2,…,n得到輸出序列為P1,P2,…,Pn（它是輸入序列的一個(gè)排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i<j<k,使Pj<Pk<Pi。11.設(shè)一數(shù)列的輸入順序?yàn)?23456，若采用堆棧結(jié)構(gòu)，并以A和D分別表示入棧和出棧操作，試問(wèn)通過(guò)入出棧操作的合法序列。（1）能否得到輸出順序?yàn)?25641的序列。（5分）（2）能否得到輸出順序?yàn)?54623的序列。（5分）12.（1）什么是遞歸程序？（2）遞歸程序的優(yōu)、缺點(diǎn)是什么？（3）遞歸程序在執(zhí)行時(shí)，應(yīng)借助于什么來(lái)完成？（4）遞歸程序的入口語(yǔ)句、出口語(yǔ)句一般用什么語(yǔ)句實(shí)現(xiàn)？13.當(dāng)過(guò)程P遞歸調(diào)用自身時(shí)，過(guò)程P內(nèi)部定義的局部變量在P的2次調(diào)用期間是否占用同一數(shù)據(jù)區(qū)？為什么？14.試推導(dǎo)出當(dāng)總盤(pán)數(shù)為n的Hanoi塔的移動(dòng)次數(shù)。15.用一個(gè)數(shù)組S（設(shè)大小為MAX）作為兩個(gè)堆棧的共享空間。請(qǐng)說(shuō)明共享方法，棧滿/?？盏呐袛鄺l件，并用C或PASCAL設(shè)計(jì)公用的入棧操作push（i，x），其中i為0或1，用于表示棧號(hào)，x為入棧值。16.用棧實(shí)現(xiàn)將中綴表達(dá)式8-(3+5)*(5-6/2)轉(zhuǎn)換成后綴表達(dá)式，畫(huà)出棧的變化過(guò)程圖。17.在表達(dá)式中，有的運(yùn)算符要求從右到左計(jì)算，如A**B**C的計(jì)算次序應(yīng)為(A**(B**C))，這在由中綴生成后綴的算法中是怎樣實(shí)現(xiàn)的?(以**為例說(shuō)明)18.有字符串次序?yàn)?*-y-a/y^2,利用棧，給出將次序改為3y-*ay2^/-的操作步驟。（可用X代表掃描該字符串過(guò)程中順序取一個(gè)字符進(jìn)棧的操作，用S代表從棧中取出一個(gè)字符加入到新字符串尾的出棧操作。例如，ABC變?yōu)锽CA的操作步驟為XXSXSS）19.內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m）提供給兩個(gè)棧S1和S2使用，怎樣分配這部分存儲(chǔ)空間，使得對(duì)任一個(gè)棧，僅當(dāng)這部分空間全滿時(shí)才發(fā)生上溢。20.將兩個(gè)棧存入數(shù)組V[1..m]應(yīng)如何安排最好？這時(shí)棧空、棧滿的條件是什么？21.在一個(gè)算法中需要建立多個(gè)堆棧時(shí)可以選用下列三種方案之一，試問(wèn)：這三種方案之間相比較各有什么優(yōu)缺點(diǎn)？（1）分別用多個(gè)順序存儲(chǔ)空間建立多個(gè)獨(dú)立的堆棧；（2）多個(gè)堆棧共享一個(gè)順序存儲(chǔ)空間；（3）分別建立多個(gè)獨(dú)立的鏈接堆棧。22．在某程序中，有兩個(gè)棧共享一個(gè)一維數(shù)組空間SPACE[N]、SPACE[0]、SPACE[N-1]