PTA第三章栈与队列练习题.doc

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
在用数组表示得循环队列中,front值一定小于等于rear值。 (1分)
T         F
作者: DS课程组
单位: 浙江大学
1-3
若一个栈得输入序列为{1, 2, 3, 4, 5},则不可能得到{3, 4, 1, 2, 5}这样得出栈序列。 (2分)
T         F
作者: 徐镜春
单位: 浙江大学
1-4
If 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
所谓“循环队列”就是指用单向循环链表或者循环数组表示得队列。 (1分)
T         F
作者: DS课程组
单位: 浙江大学
1-6
An algorithm to check for balancing symbols in an expression uses a stack to store the symbols、 (1分)
T         F
2-1
设栈S与队列Q得初始状态均为空,元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队得顺序就是b、d、c、f、e、a、g,则栈S得容量至少就是: (2分)
1. 1
2. 2
3. 3
4. 4
作者: DS课程组
单位: 浙江大学
2-2
若元素a、b、c、d、e、f依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈工作,则不可能得到得出栈序列就是？ (2分)
1. b c a e f d
2. c b d a e f
3. d c e b f a
4. a f e d c b
作者: DS课程组
单位: 浙江大学
2-3
设一个栈得输入序列就是1、2、3、4、5,则下列序列中,就是栈得合法输出序列得就是？ (2分)
1. 3 2 1 5 4
2. 5 1 2 3 4
3. 4 5 1 3 2
4. 4 3 1 2 5
作者: DS课程组
单位: 浙江大学
2-4
令P代表入栈,O代表出栈。则将一个字符串3*a+b/c变为3 a * b c / +得堆栈操作序列就是哪个？(例如将ABC变成BCA得操作序列就是PPOPOO。) (2分)
1 PPPOOOPPOPPOOO
2. POPOPOPPOPPOOO
3. POPPOOPPOPOOPO
4. POPPOOPPOPPOOO
作者: DS课程组
单位: 浙江大学
2-5
设一个堆栈得入栈顺序就是1、2、3、4、5。若第一个出栈得元素就是4,则最后一个出栈得元素必定就是: (2分)
1. 1
2. 3
3. 5
4. 1或者5
作者: DS课程组
单位: 浙江大学
2-6
为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要输出得数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区得逻辑结构应该就是？ (1分)
1. 堆栈
2. 队列
3. 树
4. 图
作者: DS课程组
单位: 浙江大学
2-7
某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作,则不可能得到得出队序列就是: (2分)
1. b a c d e
2. d b a c e
3. e c b a d
4. d b c a e
作者: DS课程组
单位: 浙江大学
2-8
若用大小为6得数组来实现循环队列,且当前front与rear得值分别为0与4。当从队列中删除两个元素,再加入两个元素后,front与rear得值分别为多少？ (2分)
1. 2与0
2. 2与2
3. 2与4
4. 2与6
作者: DS课程组
单位: 浙江大学
2-10
以下不就是栈得基本运算得就是( )。 (2分)
1. 删除栈顶元素
2. 删除栈底元素
3. 判断栈就是否为空
4. 将栈置为空栈
作者: 严冰
单位: 浙江大学城市学院
2-11
在一个链队列中,front与rear分别为头指针与尾指针,则插入一个结点s得操作为( )。 (2分)
1. front=front->next
2. s->next=rear;rear=s
3. rear->next=s;rear=s;
4. s->next=front;front=s;
作者: 杨斌
单位: 枣庄学院
2-12
依次在初始为空得队列中插入元素a,b,c,d以后,紧接着做了两次删除操作,此时得队头元素就是( )。 (2分)
1. a
2. b
3. c
4. d
作者: 杨斌
单位: 枣庄学院
2-13
当用大小为N得数组存储顺序循环队列时,该队列得最大长度为( )。 (2分)
1. N
2. N-1
3. N+1
4. N+2
作者: 杨斌
单位: 枣庄学院
2-14
判断一个循环队列QU(最多元素为MaxSize)为空得条件就是()。 (2分)
1. QU、front == QU、rear
2. QU、front != QU、rear
3. QU、front == (QU、rear + 1) % MaxSize
4. QU、front != (QU、rear + 1) % MaxSize
作者: 严冰
单位: 浙江大学城市学院
2-15
(neuDS)在队列中存取数据元素得原则就是( )。(2分)
1. 先进先出
2. 先进后出
3. 后进先出
4. 没有限制
作者: 徐婉珍
单位: 浙江大学
2-16
循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别就是front与rear,则当前队列中得元素个数就是( )。 (2分)
1. (rear-front+m)%m
2. rear-front
3. rear-front-1
4. rear-front
作者: 杨斌
单位: 枣庄学院
2-17
若以1234作为双端队列得输入序列,则既不能由输入受限得双端队列得到,也不能由输出受限得双端队列得到得就是( )。 (2分)
1. 1234
2. 4132
3. 4231
4. 4213
作者: 杨斌
单位: 枣庄学院
2-18
(neuDS)在链栈中,进行出栈操作时( )。 (2分)
1. 需要判断栈就是否满
2. 需要判断栈就是否为空
3. 需要判断栈元素得类型
4. 无需对栈作任何操作
作者 徐婉珍
单位: 广东东软学院
2-19
(neuDS)在栈中存取数据得原则就是( )。(2分)
1. 先进先出
2. 先进后出
3. 后进后出
4. 没有限制
作者: 徐婉珍
单位: 广东东软学院
2-20
链式栈与顺序栈相比,一个比较明显得优点就是( )。 (2分)
1. 插入操作更加方便
2. 通常不会出现栈满得情况
3. 不会出现栈空得情况
4. 删除操作更加方便
作者: 严冰
单位: 浙江大学城市学院
2-21
若(a-b)*(c+d)就是中序表达式,则其后序表达式就是( )。 (2分)
1. abcd+*-
2. ab-cd+*
3. ab-*cd+
4. a-bcd+*
作者: 严冰
单位: 浙江大学城市学院
2-21
Let P stands 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. PPPOOO
2. POPOPO
3. POPPOO
4. PPOOPO
作者: DS课程组
单位: 浙江大学
2-22
The 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. - + * a b c d
作者: DS课程组
单位: 浙江大学
2-23
现有队列 Q 与栈 S,初始时 Q 中得元素依次就是{ 1, 2, 3, 4, 5, 6 }(1在队头),S 为空。若允许下列3种操作:(1)出队并输出出队元素;(2)出队并将出队元素入栈;(3)出栈并输出出栈元素,则不能得到得输出序列就是:(2分)
1. 1, 2, 5, 6, 4, 3
2. 2, 3, 4, 5, 6, 1
3. 3 4, 5, 6, 1, 2
4. 6, 5, 4, 3, 2, 1
作者: 考研真题
单位: 浙江大学
2-24
Supposed that a, b, c, d, e and f are pushed onto 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 d
2. c b d a e f
3. d c e b f a
4. a f e d c b
作者: DS课程组
单位: 浙江大学
2-25
Given an empty stack 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. 2
2. 3
3. 4
4. 5
作者: Martin Ester
单位: 浙江大学
2-26
Given 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 6
2. 3 4 6 5 2 1
3. 5 4 3 6 1 2
4. 4 5 3 1 2 6
作者: DS课程组
单位: 浙江大学
2-27
下列关于栈得叙述中,错误得就是:(2分)
1. 采用非递归方式重写递归程序时必须使用栈
2. 函数调用时,系统要用栈保存必要得信息
3. 只要确定了入栈次序,即可确定出栈次序
4. 栈就是一种受限得线性表,允许在其两端进行操作
1. 仅 1
2. 仅 1、2、3
3. 仅 1、3、4
4. 仅 2、3、4
2 李文超 61、0 F(2、0) F(1、0) T(2、0) T(2、0) F(1、0) T(1、0) C(2、0) D(2、0) A(2、0) D(2、0) D(2、0) B(1、0) D(2、0) A(2、0) B(2、0) C(2、0) C(2、0) B(2、0) A(2、0) A(2、0) A(2、0) C(2、0) B(2、0) B(2、0) B(2、0) B(2、0) C(3、0) A(2、0) C D(2、0) D(2、0) B(2、0) C(2、0)