课程课件作业chapter3答案.pptxVIP

1复习题栈和队列具有相同的______。 A.抽象数据类型 B.逻辑结构 C.存储结构 D.运算若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次退栈工作，则不可能得到的出栈序列是_______。 A.dcebfa B.cbdaef C.bcaefd D.afedcbBD

2复习题已知一个栈的进栈序列是1,2,3,…,n，其输出序列是p1,p2,p3,…,pn，若p1=n，则pi的值是____。 A.i B.n-i C.n-i+1 D.不确定设n个元素的进栈序列是1,2,3,…,n，其输出序列是p1,p2,p3,…,pn，若p1=3，则p2的值是____。A.一定是2 B.一定是1 C.不可能是1 D.以上都不对CC

3复习题经过以下队列运算后，队头的值是______。InitQueue(Q);EnQueue(Q,a);EnQueue(Q,b);EnQueue(Q,c);DeQueue(Q,e); A.a B.b C.1 D.0设循环队列中数组的下标是0~N-1，其头尾指针分别为f和r，则其元素个数为______。 A.r-f B.r-f-1 C.(r-f)%N+1 D.(r–f+N)%NBD

4复习题若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是______。 A.1和5B.2和4C.4和2 D.5和1判定一个循环队列Q(存放元素位置0~QueueSize-1)队满的条件是______。 A.Q.front==Q.rear B.Q.front+1==Q.rear C.Q.front==(Q.rear+1)%QueueSizeD.Q.rear==(Q.front+1)%QueueSizeBC

5复习题假设用Q[0..M]实现循环队列，Q[f]、Q[r]分别为队头元素的前一个位置和队尾元素位置。若用(r+1)%(M+1)==f作为队满的标志，则______。 A.可用f==r作为队空的标志B.可用fr作为队空的标志C.可用(f+1)%(M+1)==r作为队空的标志D.队列中最多可以有M+1个元素A

6复习题最不适合用做链队列的链表是______。 A.只带队头指针的非循环双链表B.只带队头指针的循环双链表C.只带队尾指针的循环双链表D.只带队尾指针的循环单链表A

7复习题设栈S和队列Q的初始状态为空，元素e1~e6依次通过栈S，每个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是______。 A.5 B.4 C.3 D.2C

8复习题若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则最多只能执行______次入队操作。 若用Q[1]~Q[100]作为循环队列的存储空间，Q[f]、r分别表示队头元素和下一个插入位置，则当f=70,r=20时，队列中共有_____个元素。m50

9复习题判断以下叙述的正确性。顺序栈中元素值的大小是有序的。在n个元素进栈以后，它们的出栈顺序和进栈顺序一定正好相反。栈顶元素和栈底元素有可能是同一个元素。若用s[1]~s[m]表示顺序栈的存储空间，则对栈的进栈和出栈操作最多只能进行m次。栈是一种对进栈、出栈操作的次序作了限制的线性表。(?)(?)(?)(?)(?)

10复习题判断以下叙述的正确性。n个元素入队的顺序和出队的顺序总是一致的。若采用“队头指针和队尾指针的值相等”作为循环队列为空的标志，则在设置一个空队列时，只需将队头指针和队尾指针赋同一个值，不管什么值（只要在其取值范围内）都可以。无论是顺序队列，还是链队列，插入和删除运算的时间复杂度都是O(1)。若用不带头结点的非循环单链表来表示链式队列，则可以用“队头指针和队尾指针的值相等”作为队空的标志。(?)(?)(?)(?)

11复习题假设以不带头结点的单循环链表表示队列，并且只设一个指针rear指向队尾结点，但不设头指针，请写出相应的队初始化、入队和判断队空的算法。

12复习