PTA第三章栈和队列练习题.docx
《PTA第三章栈和队列练习题.docx》由会员分享，可在线阅读，更多相关《PTA第三章栈和队列练习题.docx（22页珍藏版）》请在冰点文库上搜索。
PTA第三章栈和队列练习题
1-1
通过对堆栈 S 操作：
Push（S,1）, Push（S,2）, Pop（S）, Push（S,3）, Pop（S）, Pop（S）。
输出的
序列为：
123。
（2 分）
TF
作者:
DS 课程组
单位:
浙江大学
1-2
在用数组表示的循环队列中，front 值一定小于等于 rear 值。
（1 分）
TF
作者:
DS 课程组
单位:
浙江大学
1-3
若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。
（2 分）
TF
作者:
徐镜春
单位:
浙江大学
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 分）
TF
作者:
徐镜春
单位:
浙江大学
1-5
所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。
（1 分）
TF
作者:
DS 课程组
单位:
浙江大学
1-6
An algorithm to check for balancing symbols in an expression uses a stack to store the
symbols. （1 分）
TF
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.bcaefd
2.cbdaef
3.dcebfa
4.afedcb
作者:
DS 课程组
单位:
浙江大学
2-3
设一个栈的输入序列是 1、2、3、4、5，则下列序列中，是栈的合法输出序列
的是？
（2 分）
1.32154
2.51234
3.45132
4.43125
作者:
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.bacde
2.dbace
3.ecbad
4.dbcae
作者:
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.bcaefd
2.cbdaef
3.dcebfa
4.afedcb
作者:
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.234156
2.346521
3.543612
4.453126
作者:
DS 课程组
单位:
浙江大学
2-27
下列关于栈的叙述中，错误的是：
（2 分）
1. 采用非递归方式重写递归程序时必须使用栈
2. 函数调用时，系统要用栈保存必要的信息
3. 只要确定了入栈次序，即可确定出栈次序
4. 栈是一种受限的线性表，允许在其两端进行操作
1.仅 1
2.仅 1、2、3
3.仅 1、3、4
4.仅 2、3、4
201712190218李文超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）CD（2.0）D（2.0）B（2.0）C（2.0）
升级会员 