棧習題.doc

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