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},thenitisimpossibleto

obtaintheoutputsequence{3,4,1,2,5}.(2分)

TF

作者:徐镜春
单位:浙江大学

1-5

所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。(1分)

TF
.

作者:DS课程组
单位:浙江大学

1-6

Analgorithmtocheckforbalancingsymbolsinanexpressionusesastacktostore

thesymbols.(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的数组存