学号_______ 姓名_______ 班级_______ 成绩_______
第三章栈和队列习题
一、判断
1.队列中所有的插入操作都发生在表的一端，删除则发生在表的另
一端（）
2.栈具有先进先出的特性（）
3.队列为先进后出的结构（）
4.栈用于实现子程序调用（）
5.栈、队列必须用数组来表示（）
6.队列用于操作系统中的作业调度（）
7.线性表的每个结点只能是一个简单类型，而链表的每个结点可以
是一个复杂类型。
（）
8.栈和链表是两种不同的数据结构。
（）
9.栈和队列的存储方式既可是顺序方式，也可是链接方式。
（）
二、单项选择
1．循环队列用数组A[maxsize] 表示，下面哪个选项表示该循环队列队满
(A) rear==maxsize-1 (B) front==(rear+1)%maxsize
(C) rear-front==maxsize (D) rear-front==maxsize-1 2．元素的入栈序列是a,b,c,d，则栈的不可能的输出序列是
(A) dcba (B)abcd (C) dcab (D) cbad
3．在用数组queue[maxsize]仿真队列时(temp为int型变量)，假设队列中至少有一个元素，出队列操作应执行以下
(A) temp=queue[rear]；rear--；(B) rear++；
temp=queue[rear]；
(C) temp=queue[front]；front--；(D) front++；temp=queue[front]；
4．下列哪种数据结构常用于函数调用
(A) 堆栈 (B) 队列 (C) 链表 (D) 数组
5．编译器中通常以哪种数据结构处理递归程序调用
（A）队列（B）数组（C）堆栈（D）记录
6．下列哪些数据结构可用来实现堆栈
（1）链表（2）数组（3）树（4）图
（A）（2），（3）（B）（2），（4）（C）（1），（4）（D）（1），（2）7．下列哪种数据结构常用于系统程序的作业调度
（A）栈（B）队列（C）链表（D）数组
8．栈和队列的共同点是
（A）都是先进后出（B）都是先进先出
（C）只允许在端点处插入和删除元素（D）没有共同点
9．若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为______
Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定
10．判定一个栈ST（最多元素为m0）为空的条件是
Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0
11．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，
计算队列中元素的公式为
A.r－f;
B.（n＋f－r）% n;
C.n＋r－F;
D.（n＋r－f）% n
12．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个
打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机
则从该缓冲区中取出数据打印.该缓冲区应该是一个结
构.
(A)堆栈 (B)队列 (C)数组 (D)线性表
13、判断一个队列QU（最多元素为m0）为空的条件是。
A. rear- front==m0
B. rear- front-1==m0
C. front== rear
D. front== rear+1
14、判断一个循环队列QU(最多元素为m0)为满队列的条件
是。
A. front== rear
B. front!= rear
C. front==( rear+1)%m0
D. front!=( rear+1)%m0
15．一个队列（数组仿真，最多元素为MaxSize）下列哪个选项表示了队列空间全部被利用？
A.rear – front == MaxSize
B.rear – front == MaxSize –1
C.rear == front
D.rear + 1 == front
16．判定一个循环队列（数组仿真，最多元素为MaxSize）为空的条件是？
A. front == rear
B. front != rear
C. front == (rear + 1)%MaxSize
D. front != (rear + 1)%MaxSize
17、若用一个大小为6的数组来实现循环队列，且当rear和front 的值分别为0和3。
当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？
A 1和5
B 2和4
C 4和2
D 5和1
18、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是
a 6
b 4
c 3
d 2
三、填空
1．栈和队列都是线性结构，对于栈只能在_____ 位置插入和删除元素，对于队列只能在_____ 位置插入元素和位置删除元素。
2．用大小为MaxSize的数组仿真一个循环队列，front和rear分别记录该队列前后端的索引值，则该循环队列在某一状态下，队列中的元素个数为。
3．在具有n个单元的环状队列中，队满时共有个元素。
4．堆栈、队列的建立可使用两种结构： _ _ 结构和 __ 结构。
5、栈是一种特殊的线性表，允许插入和删除运算的一端称为。
不允许插入和删除运算的一端称为。
6．表达式求值是（）应用的一个典型例子。
四、简答
1．试写出执行函数之后的结果。
注：此为环状队列，且每次执行以上一次执行的结果为基础－addqueue（）结果包含“队列数据内容”、“front”、“rear”及边界情况的输出
－delqueue（）结果包含“队列数据内容”、“front”、“rear”及输出数据值和边界情况的输出
2
1
（1）a ddqueue（30）
（2）d elqueue（）
（3）a ddqueue(30)
2．试写出执行函数之后的结果。
注：此为堆栈，且每次执行以上一次执行的结果为基础－push（）结果包含“堆栈数据内容”、“top”及边界情况的输出－pop（）结果包含“堆栈数据内容”、“top”及输出数据值和边界情况的输出
3
2
1
（1）p ush（30）
（2）p op（）
（3）p ush(30)
3．什么是栈？什么是队列？试分别举两个应用实例。
4．顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？
5．设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有
① front=11，rear=19; ② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？
6、计算表达式 6*3/2-5*1，要求绘出堆栈的处理过程
7、假设CQ[0,….10]是一个环状队列，初始状front=rear=1, 画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。
d, e, b, g, h入队；
d, e 出队；
I, j, k, l, m入队；
b出队；
n, o, p, q, r入队。