第三章栈和队列习题

学号_______ 姓名_______ 班级_______ 成绩_______

第三章栈和队列习题

一、 判断

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 0

（1） addqueue（30）

24 16 10 3 front rear

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库第三章栈和队列习题在线全文阅读。