棧習(xí)題.doc

一 選擇題1. 對(duì)于棧操作數(shù)據(jù)的原則是（ b ）。A. 先進(jìn)先出 B. 后進(jìn)先出 C. 后進(jìn)后出 D. 不分順序2. 在作進(jìn)棧運(yùn)算時(shí),應(yīng)先判別棧是否( b ),在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否( a )。當(dāng)棧中元素為n個(gè),作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說(shuō)明該棧的最大容量為( c )。為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí),應(yīng)將兩棧的 ( d )分別設(shè)在這片內(nèi)存空間的兩端,這樣,當(dāng)( c )時(shí)，才產(chǎn)生上溢。 , : A. 空 B. 滿 C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 : A. 長(zhǎng)度 B. 深度 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è)棧的棧底.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ú)限遞歸17. 表達(dá)式3* 2(4+2*2-6*3)-5求值過(guò)程中當(dāng)掃描到6時(shí)，對(duì)象棧和算符棧為（d ），其中為乘冪 。A. 3,2,4,1,1；(*(+*- B. 3,2,8；(*- C. 3,2,4,2,2；(*(- D. 3,2,8；(*(- /(第一個(gè)（是棧底，相當(dāng)于#作用)18. 用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)( d )。A僅修改隊(duì)頭指針 B. 僅修改隊(duì)尾指針 C. 隊(duì)頭、隊(duì)尾指針都要修改 D. 隊(duì)頭,隊(duì)尾指針都可能要修改19. 遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（ c ）的數(shù)據(jù)結(jié)構(gòu)。A隊(duì)列 B多維數(shù)組 C棧 D. 線性表20. 假設(shè)以數(shù)組Am存放循環(huán)隊(duì)列的元素,其頭尾指針?lè)謩e為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（a）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m21. 循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A0.m中，則入隊(duì)時(shí)的操作為（ d ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 22. 若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？( b)A. 1和 5 B. 2和4 C. 4和2 D. 5和1 23. 最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是 （ b ）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front24. 棧和隊(duì)列的共同點(diǎn)是（c ）。A. 都是先進(jìn)先出 B. 都是先進(jìn)后出 C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒(méi)有共同點(diǎn)25. 棧的特點(diǎn)是（ b ）,隊(duì)列的特點(diǎn)是（ a ）,棧和隊(duì)列都是（ c ）。若進(jìn)棧序列為1,2,3,4 則（ c ）不可能是一個(gè)出棧序列（不一定全部進(jìn)棧后再出棧）；若進(jìn)隊(duì)列的序列為1,2,3,4 則（ e ）是一個(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,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 E. 1,2,3,4 F. 1,3,2,426. 棧和隊(duì)都是（ c ）A順序存儲(chǔ)的線性結(jié)構(gòu) B. 鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)C. 限制存取點(diǎn)的線性結(jié)構(gòu) D. 限制存取點(diǎn)的非線性結(jié)構(gòu)27. 設(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)該是(c )。/不考慮棧頂指向空的情況A 6 B. 4 C. 3 D. 228. 依次讀入數(shù)據(jù)元素序列a，b，c，d，e，f，g進(jìn)棧,每進(jìn)一個(gè)元素，機(jī)器可要求下一個(gè)元素進(jìn)?；驈棗?，如此進(jìn)行，則?？諘r(shí)彈出的元素構(gòu)成的序列是以下哪些序列？a dAd ，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ō)法（ T ）2. 棧是實(shí)現(xiàn)過(guò)程和函數(shù)等子程序所必需的結(jié)構(gòu)。（ T ）3. 兩個(gè)棧共用靜態(tài)存儲(chǔ)空間，對(duì)頭使用也存在空間溢出問(wèn)題。（ T ）4兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。（ T ）5. 即使對(duì)不含相同元素的同一輸入序列進(jìn)行兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（ F ）6. 若輸入序列為1,2,3,4,5,6,則通過(guò)一個(gè)?？梢暂敵鲂蛄?,2,5,6,4,1. （ T ）7若輸入序列為1，2，3，4，5，6，則通過(guò)一個(gè)?？梢暂敵鲂蛄?，5，4，6，2，3。（ F ）8. 任何一個(gè)遞歸過(guò)程都可以轉(zhuǎn)換成非遞歸過(guò)程。（T）9. 只有那種使用了局部變量的遞歸過(guò)程在轉(zhuǎn)換成非遞歸過(guò)程時(shí)才必須使用棧。（F）10. 循環(huán)隊(duì)列也存在空間溢出問(wèn)題。（ T）三 填空題 1棧是_限制僅在表尾進(jìn)行存取_的線性表，其運(yùn)算遵循_先進(jìn)后出_的原則。2. 一個(gè)棧的輸入序列是：1，2，3則不可能的棧輸出序列是_3 1 2_。3. 設(shè)有一個(gè)空棧，棧頂指針為1000H(十六進(jìn)制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過(guò)PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是2 3 _，而棧頂指針值是_100C_H。設(shè)棧為順序棧，每個(gè)元素占4個(gè)字節(jié)。4在作進(jìn)棧運(yùn)算時(shí)應(yīng)先判別棧是否_滿_;在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否 空_；當(dāng)棧中元素為n個(gè)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明該棧的最大容量為_n+1_。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的空間時(shí)，應(yīng)將兩棧的_棧底_分別設(shè)在內(nèi)存空間的兩端，這樣只有當(dāng)_某一個(gè)棧的棧頂大于另一個(gè)棧的棧頂_時(shí)才產(chǎn)生溢出。5. 多個(gè)棧共存時(shí)，最好用_鏈?zhǔn)絖作為存儲(chǔ)結(jié)構(gòu)。6. 循環(huán)隊(duì)列的引入，目的是為了克服_隊(duì)滿時(shí)再進(jìn)隊(duì)會(huì)發(fā)生溢出（虛假溢出）_。 7區(qū)分循環(huán)隊(duì)列的滿與空，只有兩種方法，它們是_ 做標(biāo)記_和_犧牲一個(gè)存儲(chǔ)單元 _。8用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為_SXSSXSX