PTA第三章棧和隊列練習習題

1、1-1通過對堆棧S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。輸出的序列為：123。 (2分)T         F作者: DS課程組單位: 浙江大學1-2在用數(shù)組表示的循環(huán)隊列中，front值一定小于等于rear值。 (1分)T         F作者: DS課程組單位: 浙江大學1-3若一個棧的輸入序列為1, 2, 3, 4, 5，則不可能得到3, 4, 1, 2, 5這樣的出棧序列。 (2分)T      

2、   F作者: 徐鏡春單位: 浙江大學1-4If keys are pushed onto a stack in the order 1, 2, 3, 4, 5, then it is impossible to obtain the output sequence 3, 4, 1, 2, 5. (2分)T         F作者: 徐鏡春單位: 浙江大學1-5所謂“循環(huán)隊列”是指用單向循環(huán)鏈表或者循環(huán)數(shù)組表示的隊列。 (1分)T         F作者: DS課程組單位: 浙江大學1-6An algor

3、ithm to check for balancing symbols in an expression uses a stack to store the symbols. (1分)T         F2-1設棧S和隊列Q的初始狀態(tài)均為空，元素a、b、c、d、e、f、g依次進入棧S。若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是b、d、c、f、e、a、g，則棧S的容量至少是： (2分)1. 12. 23. 34. 4作者: DS課程組單位: 浙江大學2-2若元素a、b、c、d、e、f依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三次進行退

4、棧工作，則不可能得到的出棧序列是 (2分)1. b c a e f d2. c b d a e f3. d c e b f a4. a f e d c b作者: DS課程組單位: 浙江大學2-3設一個棧的輸入序列是1、2、3、4、5，則下列序列中，是棧的合法輸出序列的是 (2分)1. 3 2 1 5 42. 5 1 2 3 43. 4 5 1 3 24. 4 3 1 2 5作者: DS課程組單位: 浙江大學2-4令P代表入棧，O代表出棧。則將一個字符串3*a+b/c變?yōu)? a * b c / +的堆棧操作序列是哪個（例如將ABC變成BCA的操作序列是PPOPOO。） (2分)1. PPPOOO

5、PPOPPOOO 2. POPOPOPPOPPOOO 3. POPPOOPPOPOOPO 4. POPPOOPPOPPOOO作者: DS課程組單位: 浙江大學2-5設一個堆棧的入棧順序是1、2、3、4、5。若第一個出棧的元素是4，則最后一個出棧的元素必定是： (2分)1. 12. 33. 54. 1或者5作者: DS課程組單位: 浙江大學2-6為解決計算機主機與打印機之間速度不匹配問題，通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結構應該是 (1分)1. 堆棧2. 隊列3. 樹4. 圖作者: DS課程組單位: 浙江大學2-7

6、某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作。若元素a、b、c、d、e依次入此隊列后再進行出隊操作，則不可能得到的出隊序列是： (2分)1. b a c d e2. d b a c e3. e c b a d4. d b c a e作者: DS課程組單位: 浙江大學2-8若用大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前front和rear的值分別為0和4。當從隊列中刪除兩個元素，再加入兩個元素后，front和rear的值分別為多少 (2分)1. 2和02. 2和23. 2和44. 2和6作者: DS課程組單位: 浙江大學2-10以下不是棧的基本運算的是( )。 (2分)1. 刪除棧頂元素

7、 2. 刪除棧底元素3. 判斷棧是否為空4. 將棧置為空棧作者: 嚴冰單位: 浙江大學城市學院2-11在一個鏈隊列中，front和rear分別為頭指針和尾指針，則插入一個結點s的操作為（ ）。 (2分)1. front=front->next2. s->next=rear;rear=s3. rear->next=s;rear=s;4. s->next=front;front=s;作者: 楊斌單位: 棗莊學院2-12依次在初始為空的隊列中插入元素a,b,c,d以后，緊接著做了兩次刪除操作，此時的隊頭元素是（ ）。 (2分)1. a2. b3. c4. d作者: 楊斌單位:

8、 棗莊學院2-13當用大小為N的數(shù)組存儲順序循環(huán)隊列時，該隊列的最大長度為（ ）。 (2分)1. N2. N-13. N+14. N+2作者: 楊斌單位: 棗莊學院2-14判斷一個循環(huán)隊列QU（最多元素為MaxSize）為空的條件是（）。 (2分)1. = 2. != 3. = + 1) % MaxSize4. != + 1) % MaxSize作者: 嚴冰單位: 浙江大學城市學院2-15(neuDS)在隊列中存取數(shù)據(jù)元素的原則是（ ）。(2分)1. 先進先出 2. 先進后出3. 后進先出4. 沒有限制作者: 徐婉珍單位: 浙江大學2-16循環(huán)隊列用數(shù)組A0，m-1存放其元素值，已知其頭尾指針

9、分別是front和rear，則當前隊列中的元素個數(shù)是（ ）。 (2分)1. (rear-front+m)%m2. rear-front3. rear-front-14. rear-front作者: 楊斌單位: 棗莊學院2-17若以1234作為雙端隊列的輸入序列，則既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的是（ ）。 (2分)1. 12342. 41323. 42314. 4213作者: 楊斌單位: 棗莊學院2-18(neuDS)在鏈棧中，進行出棧操作時( )。 (2分)1. 需要判斷棧是否滿2. 需要判斷棧是否為空3. 需要判斷棧元素的類型4. 無需對棧作任何操作作者:

10、徐婉珍單位: 廣東東軟學院2-19(neuDS)在棧中存取數(shù)據(jù)的原則是（ ）。(2分)1. 先進先出2. 先進后出3. 后進后出4. 沒有限制作者: 徐婉珍單位: 廣東東軟學院2-20鏈式棧與順序棧相比，一個比較明顯的優(yōu)點是（ ）。 (2分)1. 插入操作更加方便2. 通常不會出現(xiàn)棧滿的情況3. 不會出現(xiàn)?？盏那闆r4. 刪除操作更加方便作者: 嚴冰單位: 浙江大學城市學院2-21若(a-b)*(c+d)是中序表達式，則其后序表達式是（ ）。 (2分)1. abcd+*-2. ab-cd+*3. ab-*cd+4. a-bcd+*作者: 嚴冰單位: 浙江大學城市學院2-21Let P stand

11、s for push and O for pop. When using a stack to convert the infix expression 3*2+8/4 into a postfix expression, the stack operation sequence is: (3分)1. PPPOOO2. POPOPO3. POPPOO4. PPOOPO作者: DS課程組單位: 浙江大學2-22The postfix expression of a*(b+c)-d is: (2分)1. a b c + * d -2. a b c d * + -3. a b c * + d -4.

12、 - + * a b c d作者: DS課程組單位: 浙江大學2-23現(xiàn)有隊列 Q 與棧 S，初始時 Q 中的元素依次是 1, 2, 3, 4, 5, 6 （1在隊頭），S 為空。若允許下列3種操作：（1）出隊并輸出出隊元素；（2）出隊并將出隊元素入棧；（3）出棧并輸出出棧元素，則不能得到的輸出序列是：(2分)1. 1, 2, 5, 6, 4, 32. 2, 3, 4, 5, 6, 13. 3, 4, 5, 6, 1, 24. 6, 5, 4, 3, 2, 1作者: 考研真題單位: 浙江大學2-24Supposed that a, b, c, d, e and f are pushed ont

13、o a stack in the given order. Assume that pushing and popping can be done alternatively, but no consecutive three poppings are allowed. Then among the following, the impossible popping sequence is: (2分)1. b c a e f d2. c b d a e f3. d c e b f a4. a f e d c b作者: DS課程組單位: 浙江大學2-25Given an empty stack

14、S and an empty queue Q. Push elements 1, 2, 3, 4, 5, 6, 7 one by one onto S. If each element that is popped from S is enqueued onto Q immediately, and if the dequeue sequence is 4, 5, 7, 6, 3, 2, 1, then the minimum size of S must be: (2分)1. 22. 33. 44. 5作者: Martin Ester單位: 浙江大學2-26Given the pushing sequence of a stack as 6, 5, 4, 3, 2, 1. Among the following, the impossible popping sequence is: (2分)1. 2 3 4 1 5 62. 3 4 6 5 2 13. 5 4