第三章栈和队列习题

学号_______姓名_______班级_______成绩_______第三章栈和队列习题一、判断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-12．元素的入栈序列是a,b,c,d，则栈的不可能的输出序列是(A)dcba(B)abcd(C)dcab(D)cbad3．在用数组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-top0Ｂ．ST-top=0Ｃ．ST-topm0Ｄ．ST-top=m011．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为A.r－f;B.（n＋f－r）%n;C.n＋r－F;D.（n＋r－f）%n12．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取出数据打印.该缓冲区应该是一个结构.(A)堆栈(B)队列(C)数组(D)线性表13、判断一个队列QU（最多元素为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==front16．判定一个循环队列（数组仿真，最多元素为MaxSize）为空的条件是？A.front==rearB.front!=rearC.front==(rear+1)%MaxSizeD.front!=(rear+1)%MaxSize17、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？A1和5B2和4C4和2D5和118、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是a6b4c3d2三、填空1．栈和队列都是线性结构，对于栈只能在_____位置插入和删除元素，对于队列只能在_____位置插入元素和位置删除元素。2．用大小为MaxSize的数组仿真一个循环队列，front和rear分别记录该队列前后端的索引值，则该循环队列在某一状态下，队列中的元素个数为。3．在具有n个单元的环状队列中，队满时共有个元素。4．堆栈、队列的建立可使用两种结构：__结构和__结构。5、栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。6．表达式求值是（）应用的一个典型例子。四、简答1．试写出执行函数之后的结果。注：此为环状队列，且每次执行以上一次执行的结果为基础－addqueue（）结果包含“队列数据内容”、“front”、“rear”及边界情况的输出－delqueue（）结果包含“队列数据内容”、“front”、“rear”及输出数据值和边界情况的输出3210（1）addqueue（30）241610rearfront（2）delqueue（）（3）addqueue(30)2．试写出执行函数之后的结果。注：此为堆栈，且每次执行以上一次执行的结果为基础－push（）结果包含“堆栈数据内容”、“top”及边界情况的输出－pop（）结果包含“堆栈数据内容”、“top”及输出数据值和边界情况的输出3210（1）push（30）（2）pop（）（3）push(30)28241610top3．什么是栈？什么是队列？试分别举两个应用实例。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入队。