棧和隊列習題及答案

1、棧和隊列習題及答案【篇一：棧和隊列練習題答案】xt一、填空題1. 線性表、棧和隊列都是結構，可以在線性表的在棧頂插入和刪除元素；對于隊列只能在隊尾插入和隊首刪除元素。2. 棧是一種特殊的線性表，允許插入和刪除運算的一端稱為。不允許插入和刪除運算的一端稱為棧底。3. 是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。二、判斷正誤（1.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結構。（M2.對于不同的使用者，一個表結構既可以是棧，也可以是隊列，也可以是線性表。正確，都是線性邏輯結構，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。錯，他們都

2、是線性邏輯結構，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（4.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。（5.兩個棧共享一片連續(xù)內存空間時，為提高內存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內存空間的兩端。錯，有可能。三、單項選擇題（b） 1.棧中元素的進出原則是A.先進先出B.后進先出C.棧空則進D.棧滿則出（c） c）2.若已知一個棧的入棧序列是1，2，3，?，n，其輸出序列為p1，p2，p3，?，pn，若p1=n，則pi為A.iB.n-iC.n-i+1D.不確定解釋：當p1=n，即n是最先出棧的，根據(jù)棧的原理，n必定是最后入棧的（事實上題目已經表明了），那

3、么輸入順序必定是1，2，3，?，n，則出棧的序列是n，?，3，2，1。（若不要求順序出棧，則輸出序列不確定）（d） 3.數(shù)組Q：n用來表示一個循環(huán)隊列，f為當前隊列頭元素的前一位置，r為隊尾元素的位置，假定隊列中元素的個數(shù)小于n,計算隊列中元素的公式為(A)rf;(B)(n+fr)%n;(C)n+rf;(D)(n+rf)%ne：1230四、閱讀理解1 .【嚴題集3.3】寫出下列程序段的輸出結果(棧的元素類型void main( )a ); push(s,y); t ); push(s,x);s );selemtype為char)。stacks;charx,y;initstack(s);x=c;

4、y=k;push(s,x);push(s,pop(s,x);push(s,pop(s,x);push(s,while(!stackempty(s)pop(s,y);printf(y);printf(x);答：輸出為“stack”。2 .【嚴題集3.12】寫出下列程序段的輸出結果(隊列中的元素類型qelemtype為char)。voidmain()queueq;initqueue(q);charx=e;y=c;r ); enqueue (q, y);a );enqueue(q,h);enqueue(q,dequeue(q,x);enqueue(q,x);dequeue(q,x);enqueue(

5、q,while(!queueempty(q)dequeue(q,y);printf(y);printf(x);答：輸出為“char”。3 .【嚴題集3.13】簡述以下算法的功能(棧和隊列的元素類型均為int)。voidalgo3(queueq)stacks;intd;initstack(s);while(!queueempty(q)dequeue(q,d);push(s,d);while(!stackempty(s)pop(s,d);enqueue(q,d);答：該算法的功能是：利用堆棧做輔助，將隊列中的數(shù)據(jù)元素進行逆置。【篇二：第3章棧和隊列歷屆考研題目】選擇題1. 對于棧操作數(shù)據(jù)的原則是（

6、）?！厩鄭u大學2001五、2（2分）】a.先進先出b.后進先出c.后進后出d.不分順序2. 在作進棧運算時,應先判別棧是否（）,在作退棧運算時應先判別棧是否（）。當棧中元素為n個,作進棧運算時發(fā)生上溢,則說明該棧的最大容量為（）。為了增加內存空間的利用率和減少溢出的可能性,由兩個棧共享一片連續(xù)的內存空間時,應將兩棧的（）分別設在這片內存空間的兩端，這樣，當（）時，才產生上溢。,:a.空b.滿c.上溢d.下溢 :a.n-1b.nc.n+1d.n/2 :a.長度b.深度c.棧頂d.棧底 :a.兩個棧的棧頂同時到達?？臻g的中心點.b. 其中一個棧的棧頂?shù)竭_棧空間的中心點.c. 兩個棧的棧頂在?？臻g的

7、某一位置相遇.d. 兩個棧均不空,且一個棧的棧頂?shù)竭_另一個棧的棧底.【上海海運學院1997二、1（5分）】【上海海運學院1999二、1（5分）】3. 一個棧的輸入序列為123?n，若輸出序列的第一個元素是n，輸出第i（1=i=n）個元素是（）。a.不確定b.n-i+1c.id.n-i【中山大學1999一、9（1分）】4. 若一個棧的輸入序列為1,2,3,?,n，輸出序列的第一個元素是i，則第j個輸出元素是（）。a.i-j-1b.i-jc.j-i+1d.不確定的【武漢大學2000二、3】5. 若已知一個棧的入棧序列是1,2,3,?,n，其輸出序列為p1,p2,p3，?，pn,若pn是n，則pi是

8、（）。a. ib.n-ic.n-i+1d.不確定【南京理工大學2001一、1（1.5分）】b. 有六個元素6，5，4，3，2，1的順序進棧，問下列哪一個不是合法的出棧序列？（）a.543612b.453126c.346521d.234156【北方交通大學2001一、3（2分）】7. 設棧的輸入序列是1，2，3，4,則（）不可能是其出棧序列?！局锌圃河嬎闼?000一、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. 一個棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是（）。a.23415b.54132c.2314

9、5d.15432【南開大學2000一、1】【山東大學2001二、4（1分）】【北京理工大學2000一、2（2分）】9. 設一個棧的輸入序列是1，2，3，4，5,則下列序列中，是棧的合法輸出序列的是（）。a.51234b.45132c.43125d.32154【合肥工業(yè)大學2001一、1（2分）】10.某堆棧的輸入序列為a,b,c,d,下面的四個序列中，不可能是它的輸出序列的是（）。a.a，c，b，db.b,c，d，ac.c,d，b,ad.d,c，a，b【北京航空航天大學2000一、3（2分）】【北京郵電大學1999一、3（2分）】11. 設abcdef以所給的次序進棧，若在進棧操作時，允許退棧

10、操作則下面得不到的序列為（）。afedcbab.bcafedc.dcefbad.cabdef【南京理工大學1996一、9（2分）】12. 設有三個元素x，y，z順序進棧（進的過程中允許出棧），下列得不到的出棧排列是（）。axyzb.yzxc.zxyd.zyx【南京理工大學1997一、5（2分）】13. 輸入序列為abc，可以變?yōu)閏ba時，經過的棧操作為（）【中山大學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

11、,pop,pop14. 若一個棧以向量v1.n存儲，初始棧頂指針top為n+1，則下面x進棧的正確操作是（）。atop:=top+1;vtop:=xb.vtop:=x;top:=top+1c.top:=top-1;vtop:=xd.vtop:=x;top:=top-1【南京理工大學1998一、13（2分）】15. 若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間v1.m，topi代表第i個棧（i=1,2）棧頂，棧1的底在v1，棧2的底在vm，則棧滿的條件是（）。a.|top2-top1|=0b.top1+1=top2c.top1+top2=md.top1=top2【南京理工大學1999一、14（1分）

12、】16. 棧在（）中應用。【中山大學1998二、3（2分）】a.遞歸調用b.子程序調用c.表達式求值d.a,B,C17. 一個遞歸算法必須包括（）。【武漢大學2000二、2】a.遞歸部分b.終止條件和遞歸部分c.迭代部分d.終止條件和迭代部分18. 執(zhí)行完下列語句段后，i值為：（）【浙江大學2000一、6（3分）】intf（intx）return（x0）?x*f（x-1）:2）;inti;i=f（f（1）;a2b.4c.8d.無限遞歸19. 表達式a*（b+c）-d的后綴表達式是（）?！灸暇├砉ご髮W2001一、2（1.5分）】aabcd*+-b.abc+*d-c.abc*+d-d.-+*abc

13、d20.表達式3*2八（4+2*2-6*3）-5求值過程中當掃描到6時，對象棧和算符棧為（），其中八為乘窯。a.3,2,4,1,1;（*八（+*-b.3,2,8;（*八-c.3,2,4,2,2;（*A（-d.3,2,8;（*A（-【青島大學2000五、5（2分）】21. 設計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（）數(shù)據(jù)結構最佳。a線性表的順序存儲結構b.隊列c.線性表的鏈式存儲結構d.?！疚靼搽娮涌萍即髮W1996一、6（2分）】22. 用鏈接方式存儲的隊列，在進行刪除運算時（）?！颈狈浇煌ù髮W2001一、12（2分）】a.僅修改頭指針b.僅修改尾指針c.頭、尾指針都要修改d.頭、

14、尾指針可能都要修改23. 用不帶頭結點的單鏈表存儲隊列時,其隊頭指針指向隊頭結點,其隊尾指針指向隊尾結點，則在進行刪除操作時（）?！颈本├砉ご髮W2001六、3（2分）】a僅修改隊頭指針b.僅修改隊尾指針c.隊頭、隊尾指針都要修改d.隊頭,隊尾指針都可能要修改24. 遞歸過程或函數(shù)調用時，處理參數(shù)及返回地址，要用一種稱為（）的數(shù)據(jù)結構。a隊列b多維數(shù)組c棧d.線性表【福州大學1998一、1（2分）】25. 假設以數(shù)組am存放循環(huán)隊列的元素,其頭尾指針分別為front和rear，則當前隊列中的元素個數(shù)為（）。【北京工商大學2001一、2（3分）】a（rear-front+m）%mbrear-fro

15、nt+1c（front-rear+m）%md（rear-front）%m26. 循環(huán)隊列a0.m-1存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數(shù)是（）。【南京理工大學2001一、5（1.5分）】a.（rear-front+m）%mb.rear-front+1c.rear-front-1d.rear-front27. 循環(huán)隊列存儲在數(shù)組a0.m中，則入隊時的操作為（）?！局猩酱髮W1999一、6（1分）】a.rear=rear+1b.rear=（rear+1）mod（m-1）c.rear=（rear+1）modmd.rear=（rear+1）mod（m+1）28.

16、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？（）【浙江大學1999四、1（4分）】a.1和5b.2和4c.4和2d.5和129. 已知輸入序列為abcd經過輸出受限的雙向隊列后能得到的輸出序列有（）。a.dacbb.cadbc.dbcad.bdace.以上答案都不對【西安交通大學1996三、3（3分）】30. 若以1234作為雙端隊列的輸入序列，則既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列是（）?！疚靼搽娮涌萍即髮W1996一、5（2分）】a.1234

17、b.4132c.4231d.421331. 最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（）。a.（rear+1）modn=frontb.rear=frontcrear+1=frontd.（rear-l）modn=front【南京理工大學1999一、16（2分）】32. 棧和隊列的共同點是（）?！狙嗌酱髮W2001一、1（2分）】a.都是先進先出b.都是先進后出c.只允許在端點處插入和刪除元素d.沒有共同點33. 棧的特點是（）,隊列的特點是（）,棧和隊列都是（）。若進棧序列為1,2,3,4則（）不可能是一個出棧序列（不一定全部進棧后再出棧）；若進隊列的序列為1,

18、2,3,4則（）是一個出隊列序列。【北方交通大學1999一、1（5分）】,:a.先進先出b.后進先出c.進優(yōu)于出d.出優(yōu)于進：a.順序存儲的線性結構b.鏈式存儲的線性結構c.限制存取點的線性結構d.限制存取點的非線性結構,: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. 棧和隊都是（）【南京理工大學1997一、3（2分）】a順序存儲的線性結構b.鏈式存儲的非線性結構c.限制存取點的線性結構d.限制存取點的非線性結構35. 設棧s和隊列q的初始狀態(tài)為空，元素e1，e2，e3，e4,e5和e6依次通過棧s,一個元素出棧后即進隊列q

19、,若6個元素出隊的序列是e2，e4，e3,e6,e5,e1則棧s的容量至少應該是（）。a6b.4c.3d.2【南京理工大學2000一、6（1.5分）】36. 用單鏈表表示的鏈式隊列的隊頭在鏈表的（）位置?！厩迦A大學1998一、1（2分）】a鏈頭b鏈尾c鏈中37. 依次讀入數(shù)據(jù)元素序列a,b,c,d,e,f,g進棧，每進一個元素，機器可要求下一個元素進?；驈棗＃绱诉M行，則棧空時彈出的元素構成的序列是以下哪些序列？【哈爾濱工業(yè)大學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. 消除遞歸不一定需

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

21、依次）進棧，出棧序列有cn種，cn=1/（n+1）*（2n）!/（n!）*（n!）。（）【北京郵電大學1998一、3（2分）】7. 棧與隊列是一種特殊操作的線性表。（）【青島大學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，則通過一個?？梢暂敵鲂蛄?，5，4，6，2，3。（）【上海海運學院1999一、3（1分）】11. 任何一個遞歸過程

22、都可以轉換成非遞歸過程。（）【上海交通大學1998一、3（1分）】12. 只有那種使用了局部變量的遞歸過程在轉換成非遞歸過程時才必須使用棧。（）【上海交通大學1998一、4（1分）】13. 隊列是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。（）【上海海運學院1998一、3（1分）】14. 通常使用隊列來處理函數(shù)或過程的調用。（）【南京航空航天大學1997一、5（1分）】15. 隊列邏輯上是一個下端和上端既能增加又能減少的線性表。（）【上海交通大學1998一、2】16. 循環(huán)隊列通常用指針來實現(xiàn)隊列的頭尾相接。（）【南京航空航天大學1996六、1（1分）】17. 循環(huán)隊列

23、也存在空間溢出問題。（）【青島大學2002一、2（1分）】18. 隊列和棧都是運算受限的線性表，只允許在表的兩端進行運算。（）【長沙鐵道學院1997一、5（1分）】19. 棧和隊列都是線性表，只是在插入和刪除時受到了一些限制。（）【北京郵電大學2002一、3（1分）】20. 棧和隊列的存儲方式，既可以是順序方式，又可以是鏈式方式。（）【上海海運學院1996一、2（1分）1999一、2（1分）】三填空題1. 棧是的線性表，其運算遵循的原則?！颈本┛萍即髮W1997一、3】2. 是限定僅在表尾進行插入或刪除操作的線性表?！狙嗌酱髮W1998一、3（1分）】3. 一個棧的輸入序列是：1，2，3則不可能的

24、棧輸出序列是?！局袊嗣翊髮W2001一、1（2分）】4. 設有一個空棧，棧頂指針為1000h（十六進制），現(xiàn)有輸入序列為1，2，3，4，5，經過push,push,pop,push,pop,push,push之后，輸出序列是，而棧頂指針值是h。設棧為順序棧，每個元素占4個字節(jié)?！疚靼搽娮涌萍即髮W1998二、1（4分）】5. 當兩個棧共享一存儲區(qū)時，棧利用一維數(shù)組stack（1,n）表示，兩棧頂指針為top1與top2，則當棧1空時，top1為，棧2空時，top2為，棧滿時為?！灸暇├砉ご髮W1997三、1（3分）】6兩個棧共享空間時棧滿的條件?！局猩酱髮W1998一、3（1分）】7 在作進棧運算時

25、應先判別棧是否_（1）_;在作退棧運算時應先判別棧是否_（2）_；當棧中元素為n個，作進棧運算時發(fā)生上溢，則說明該棧的最大容量為_（3）_。為了增加內存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的空間時，應將兩棧的_（4）_分別設在內存空間的兩端，這樣只有當_（5）_時才產生溢出?！旧綎|工業(yè)大學1994一、1（5分）】8 .多個棧共存時，最好用作為存儲結構?！灸暇├砉ご髮W2001二、7（2分）】9 用s表示入棧操作，x表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應的s和x的操作串為。【西南交通大學2000一、5】10 .順序棧用data1.n存儲數(shù)據(jù)，棧頂指

26、針是top,則值為x的元素入棧的操作是?！竞戏使I(yè)大學2001三、2（2分）】11表達式23+（12*3-2）/4+34*5/7）+108/9的后綴表達式是?！局猩酱髮W1998一、4（1分）】12. 循環(huán)隊列的引入，目的是為了克服?！緩B門大學2001一、1（14/8分）】【篇三：（棧和隊列）（復習題）】1 棧的特點是簡稱隊列的特點是，簡稱d的線性表。a先進先出b后進先出clifodfifo2 棧和隊列的共同點是。a都是先進后出b都是先進先出c只允許在端點處插入和刪除元素d沒有共同點3 一個棧的進棧序列是a，b，c，d，e，則棧的不可能的輸出序列是c。aedcbabdecbacdceabdabcde4 設有一個棧，元素依次進棧的順序為a、b、c、d、e。下列是可能的出棧序列。ad,b,c,a,ebb,c,d,e,a