數(shù)據(jù)結(jié)構(gòu)堆棧與隊(duì)列習(xí)題

1、第4-5章 棧和隊(duì)列一 選擇題1. 對(duì)于棧操作數(shù)據(jù)的原則是（ ）?！厩鄭u大學(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-1 B. n C. n+1 D. n/2 : A. 長(zhǎng)度 B.

2、 深度 C. 棧頂 D. 棧底 : A. 兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn).B. 其中一個(gè)棧的棧頂?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);A2 B. 4 C. 8 D. 無(wú)限遞歸19. 表達(dá)式a*(b+c)-d的后綴表達(dá)式是( )?！灸暇├砉ご髮W(xué) 2001 一、2（1.5分）】Aa

3、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；(*(-【青島大學(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í)

4、（ ）?！颈狈浇煌ù髮W(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í)( )?！颈本├砉ご髮W(xué) 2001 六、3（2分）】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. 線性表【福州大學(xué) 1998 一、1（2分）】25. 假設(shè)以數(shù)組Am存放循環(huán)隊(duì)列的元素

5、,其頭尾指針?lè)謩e為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ ）?！颈本┕ど檀髮W(xué) 2001 一、2（3分）】A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m26. 循環(huán)隊(duì)列A0.m-1存放其元素值，用front和rear分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素?cái)?shù)是( )。【南京理工大學(xué) 2001 一、5（1.5分）】A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front27. 循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A0.m中，則入隊(duì)時(shí)的操作為（ ）?！局?/p>

6、山大學(xué) 1999 一、6（1分）】A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. 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和 5 B. 2和4 C. 4和2 D. 5和1 29. 已知輸入序列為abcd 經(jīng)過(guò)輸出受限的雙向隊(duì)列后能得到的輸出序列有（ ）。 A. dacb B. cadb C

7、. dbca D. bdac E. 以上答案都不對(duì) 【西安交通大學(xué) 1996 三、3 (3分)】30. 若以1234作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是( )。【西安電子科技大學(xué) 1996 一、5（2分）】A. 1234 B. 4132 C. 4231 D. 4213 31. 最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是 （ ）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front【南京理工大學(xué) 19

8、99 一、16（2分）】32. 棧和隊(duì)列的共同點(diǎn)是（ ）?！狙嗌酱髮W(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)

9、的非線性結(jié)構(gòu), : A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 F. 1,2,3,4 G. 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 6 B. 4 C. 3 D. 2【南京理工大學(xué) 2000 一、6（1.5分

10、）】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，a B. f，e，g，d，a，c，bC. 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. 棧是

11、實(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!)。（

12、 ）【北京郵電大學(xué) 1998 一、3（2分）】7. 棧與隊(duì)列是一種特殊操作的線性表。（ ）【青島大學(xué) 2001 四、3 （1分）】8. 若輸入序列為1,2,3,4,5,6,則通過(guò)一個(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，則通過(guò)一個(gè)棧可以輸出序列1，5，4，6，2，3。（ ）【上海海運(yùn)學(xué)院 1999 一、3（1分）】11. 任何一個(gè)遞歸過(guò)程都可以轉(zhuǎn)換成非遞歸過(guò)程。（）【上海交通大學(xué) 1998一

13、、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)題。（

14、）【青島大學(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)算遵循_的原則?！颈本┛萍即髮W(xué) 1997 一、3】2_是限定僅在表尾進(jìn)行插入或刪除操作的線性表?！狙嗌酱髮W(xué) 1998 一、3 （1分）】3. 一個(gè)棧的輸入序列是：1，2，

15、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é)?！疚靼搽娮涌萍即髮W(xué) 1998 二、1（4分）】5. 當(dāng)兩個(gè)棧共享一存儲(chǔ)區(qū)時(shí)，棧利用一維數(shù)組stack(1,n)表示，兩棧頂指針為top1與top2，則當(dāng)棧1空時(shí)，top1為_(kāi)，棧2空時(shí) ，top2為_(kāi)，棧滿時(shí)為_(kāi)。【南京理工大學(xué) 1997 三、1（3分）】6兩個(gè)棧共享空間時(shí)棧滿的條件_?！局猩酱髮W(xué) 19

16、98 一、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)?！灸暇├砉ご髮W(xué) 2001 二、7（2分）】9用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為_(kāi)。【西南交通大學(xué) 2000 一

17、、5】10. 順序棧用data1.n存儲(chǔ)數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作是_?！竞戏使I(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ì)列的引入，目的是為了克服_?！緩B門(mén)大學(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ǔ)言的考生不填）?！疚髂辖煌ù髮W(xué) 2000 一、7】14_又稱(chēng)作先進(jìn)先出表。【重慶大學(xué) 2000 一、7】15. 隊(duì)列的特點(diǎn)是_?！颈本├砉ご髮W(xué) 2000 二、2（2分）】16隊(duì)列是限制插入只能在表的一端，而刪除在表的另一端進(jìn)行的線性表，其特點(diǎn)是_?！颈狈浇煌ù髮W(xué) 2001 二、5】17. 已知鏈隊(duì)列的頭尾指針?lè)謩e是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ì)尾指針?lè)謩e是FRONT和TAIL，判定隊(duì)滿的條件為_(kāi)?！旧綎|工業(yè)大學(xué) 1995 一、1（1分）】20. 設(shè)循環(huán)隊(duì)列存放在