PTA第三章栈和队列练习题.pdf

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
Ifkeysarepushedontoastackintheorder{1,2,3,4,5},thenitisimpossibletoobtain
theoutputsequence{3,4,1,2,5}.(2分)

TF

作者:徐镜春
单位:浙江大学
1-5
所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。(1分)

TF

作者:DS课程组
单位:浙江大学
1-6
Analgorithmtocheckforbalancingsymbolsinanexpressionusesastacktostorethe
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变为3a*bc/+的堆栈
操作序列是哪个？（例如将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

作