棧習(xí)題.doc

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