embassyPTA第三章栈和队列练习题

2021年1月21日发(作者：blight)
1-1
通过对堆栈
S
操作：
Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)
。输出的序
列为：
123
。

(2
分
)
T




作者
: DS
课程组

单位
:
浙江大学

F
1-2
在用数组表示的循环队列中，
front
值一定小于等 于
rear
值。

(1
分
)
T




作者
: DS
课程组

单位
:
浙江大学

F
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




作者
: DS
课程组

单位
:
浙江大学

F
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
、< br>d
、
c
、
f
、
e
、
a
、< br>g
，则栈
S
的容量至少是：

(2
分
)
1.

2.

3.

4.

1
2
3
4
作者
: DS
课程组

单位
:
浙江大学

2-2
若元素
a
、
b
、
c
、
d
、
e
、
f
依 次进栈，允许进栈、退栈操作交替进行，但不允许
连续三次进行退栈工作，则不可能得到的出栈序列是？

(2
分
)
1.

2.

3.

4.

b c a e f d
c b d a e f
d c e b f a
a f e d c b
作者
: DS
课程组

单位
:
浙江大学

2-3
设一个栈的输入序列是
1
、
2
、
3
、
4
、
5
，则下列序列中，是栈的合法输出序列的
是？

(2
分
)
1.

2.

3.

4.

3 2 1 5 4
5 1 2 3 4
4 5 1 3 2
4 3 1 2 5
作者
: DS
课程组

单位
:
浙江大学

2-4
令
P
代表入 栈，
O
代表出栈。则将一个字符串
3*a+b/c
变为
3 a * b c / +
的堆栈
操作序列是哪个？（例如将
ABC
变成
BCA
的操作序列是
PPOPOO
。）

(2
分
)
1.

2.

3.

4.

PPPOOOPPOPPOOO

POPOPOPPOPPOOO

POPPOOPPOPOOPO

POPPOOPPOPPOOO
作者
: DS
课程组

单位
:
浙江大学

2-5
设一个堆栈的入栈顺序是
1
、
2
、
3、
4
、
5
。若第一个出栈的元素是
4
，则最后一
个出栈的元素必定是：

(2
分
)
1.

2.

3.

4.

1
3
5
1
或者
5
作者
: DS
课程组

单位
:
浙江大学

2-6
为解决计算机主机与打印机之 间速度不匹配问题，
通常设置一个打印数据缓冲区，
主机将要输出的数据依次写入该缓冲区，< br>而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是？

(1
分
)
1.

2.

3.

4.

堆栈

队列

树

图

作者
: DS
课程组

单位
:
浙江大学

2-7
某队列允许在其两端进行入队操作，但仅允许在一端进行 出队操作。若元素
a
、
b
、
c
、
d
、e
依次入此队列后再进行出队操作，则不可能得到的出队序列是：

(2
分
)
1.

2.

3.

4.

b a c d e
d b a c e
e c b a d
d b c a e
作者
: DS
课程组

单位
:
浙江大学

2-8
若用大小为
6
的数组来实现循环队列，且当前
front
和
rear
的值分别为
0
和
4
。
当从队列中删除两个元素，再加入两个元素后，
front
和
rear
的值分别为多少？

(2
分
)
1.

2.

3.

4.

2
和
0
2
和
2
2
和
4
2
和
6
作者
: DS
课程组

单位
:
浙江大学

2-10
以下不是栈的基本运算的是
( )
。

(2
分
)
1.

2.

3.

4.

删除栈顶元素


删除栈底元素

判断栈是否为空

将栈置为空栈

作者
:
严冰

单位
:
浙江大学城市学院

2-11
在一个链队列中，
front
和
rear
分别为头指针和尾指针，则插入一个结点
s
的操
作为（

）。

(2
分
)
1.

2.

3.

4.

front=front->next
s->next=rear;rear=s
rear->next=s;rear=s;
s->next=front;front=s;
作者
:
杨斌

单位
:
枣庄学院

2-12
依次在初始为空的队列中插 入元素
a,b,c,d
以后，紧接着做了两次删除操作，此
时的队头元素是（

）。

(2
分
)
1.

2.

3.

4.

a
b
c
d
作者
:
杨斌

单位
:
枣庄学院

2-13
当用大小为
N
的数组存储顺序循环队列时，该队列的最大长度为（

）。

(2
分
)
1.

2.

3.

4.

N
N-1
N+1
N+2
作者
:
杨斌

单位
:
枣庄学院