第三章栈和队列习题

1、一、判断1. 队列中所有的插入操作都发生在表的一端，删除则发生在表的另一端2. 栈具有先进先出的特性3. 队列为先进后出的结构4. 栈用于实现子程序调用5. 栈、队列必须用数组来表示6. 队列用于操作系统中的作业调度7. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。8. 栈和链表是两种不同的数据结构。9. 栈和队列的存储方式既可是顺序方式，也可是链接方式。二、单项选择1循环队列用数组Amaxsize 表示，下面哪个选项表示该循环队列队满(A) rear=maxsize-1 (B) front=(rear+1)%maxsize(C) rear-front=maxsiz

2、e (D) rear-front=maxsize-12元素的入栈序列是a,b,c,d，则栈的不可能的输出序列是(A) dcba (B)abcd (C) dcab (D) cbad3在用数组queuemaxsize仿真队列时(temp为int型变量)，假设队列中至少有一个元素，出队列操作应执行以下(A) temp=queuerear；rear-； (B) rear+； temp=queuerear；(C) temp=queuefront；front-； (D) front+； temp=queuefront；4下列哪种数据结构常用于函数调用(A) 堆栈 (B) 队列 (C) 链表 (D) 数组5

3、编译器中通常以哪种数据结构处理递归程序调用（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（最多元素

4、为m0）为空的条件是ST->top<>0 ST->top=0 ST->top<>m0 ST->top=m011数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为（）rf; （）（nfr）% n; （）nrf （）（nrf）% n12在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取出数据打印.该缓冲区应该是一个 结构.(A) 堆栈 (B)队列 (C)数组 (D)线性表13、判断一个队列QU（最多元

5、素为m0）为空的条件是A. rear- front=m0B. rear- front-1=m0C. front= rearD. front= rear+114、判断一个循环队列QU(最多元素为m0)为满队列的条件是A. front= rearB. front!= rearC. front=( rear+1)%m0D. front!=( rear+1)%m015一个队列（数组仿真，最多元素为MaxSize）下列哪个选项表示了队列空间全部被利用？A. rear front = MaxSizeB. rear front = MaxSize 1C. rear = frontD. rear + 1 =

6、front16判定一个循环队列（数组仿真，最多元素为MaxSize）为空的条件是？ A. front = rear B. front != rearC. front = (rear + 1)%MaxSizeD. front != (rear + 1)%MaxSize17、 若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？A 1和5 B 2和4 C 4和2 D 5和118、 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6

7、个元素出队的序列是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试写出执行函

8、数之后的结果。注：此为环状队列，且每次执行以上一次执行的结果为基础addqueue（）结果包含“队列数据内容”、“front”、“rear”及边界情况的输出 delqueue（）结果包含“队列数据内容”、“front”、“rear”及输出数据值和边界情况的输出3 2 1 0（1） addqueue（30）（2） delqueue（）（3） addqueue(30)2试写出执行函数之后的结果。注：此为堆栈，且每次执行以上一次执行的结果为基础push（）结果包含“堆栈数据内容”、“top”及边界情况的输出pop（）结果包含“堆栈数据内容”、“top”及输出数据值和边界情况的输出3 21 0（1） push（30）（2） pop（）（3） push(30)3什么是栈？什么是队列？试分别举两个应用实例。4顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？5设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 front=11，rear=19; front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？6、计算表达式 6*3/2-5*1，要求绘出堆栈的处理过程7、