第3章练习题
1. 栈和队列的共同点是（ C） A.都是先进先出 B.都是先进后出 C.只允许在端点处插入和删除元素 D.没有共同点 2.4个元素a、b、c和d依次入栈，入栈过程中允许元素出 栈，假设某一时刻栈的状态是c（栈顶）、b、a（栈 底），则不可能的出栈顺序是（ C ）。 A. d,c,b,a B. c,b,d,a C. c,a,d,b D. c,d,b,a 3.向一个栈顶指针为Top的链栈中插入一个p所指结点时， 其操作步骤为（ ） C A.Top->next=p; B.p->next=Top->next;Top->next=p; C.p->next=Top;Top=p; D.p->next=Top;Top=Top->next; 4.在顺序循环队列中，队尾指针指向队尾元素的( B )位置 A. 前一个 B. 后一个 C. 当前 D. 以上都不对
16.简述以下算法的功能（栈和队列的元素类型均为 int） void algo3(Queue &Q){ Stack S; int d; 答：利用栈做辅助，将队列 中的数据元素进行逆置。 InitStack(S); while(!QueueEmpty(Q)){ DeQueue (Q,d); Push(S,d); }; while(!StackEmpty(S)){ Pop(S,d); EnQueue (Q,d); } }
8. 循环队列存储在数组A[0..m]中，则入队时的操作为(D ) A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 9.判定一个循环队列Q（存放元素位置0~MaxSize-1）队 满的条件是（ C ） A.Q.front==Q.rear B. Q.rear==(Q.front+1)%MaxSize C.Q.front==(Q.rear+1)%MaxSize D.Q.front+1==Q.rear 10.用一个大小为N的数组来实现循环队列Q，则该循环 队列为空的条件是( A )。 A. Q.front==Q.rear B. Q.rear+1==Q.front C. (Q.rear+1)%N==Q.front D. (Q.front+1)%N==Q.rear
13. 设循环顺序队列用数组A[7]（下标从0开始编号）存 放其元素值，且当前队尾rear和队头front的值分别为1 和5，当从队列中删除2个元素，再加入4个元素后， rear的值为（5 ），front的值为（ 0 ），当前队列的长 度为（ 5）。 14.设循环队列的容量为40（序号从0到39），现经过一 系列的入队和出队运算后，有 ① front=11，rear=19; ② front=19，rear=11；问在 这两种情况下，循环队列中各有元素多少个？
答：① L=（19－11＋40 ）% 40=8
答：② L=（11－19＋40 ）% 40=32
15.写出下列程序段的输出结果（队列中的元素类型 QElem Type为char）。 void main( ){ Queue Q; Init Queue (Q); Char x=’e’; y=’c’; EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q, y); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,’a’); while(!QueueEmpty(Q)){ DeQueue (Q,y); printf(y); }; printf(x); 答：输出为“char”。 }
11.一个队列的入列序列是1，2，3，4，则队列的输出序 列是（B）。 A、4，3，2，1 B、 1， 2， 3， 4 C、1，4，3，2 D、 3 ， 2 ， 4 ， 1 12.以下代码段是最大长度为N的循环队列Q的入队操作， 请补充完整。 Status EnQueue(SqQueue &Q, QElemType e) { if( ) return ERROR; //队列满 Q.base[Q.rear]=e; ( ); //队尾后移一位 (Q.rear+1)%N==Q.front; return OK; Q.rear=(Q.，b，c，d，e，f依次进栈，如 果6个元素出栈的顺序是b，d，c，f，e，a，则栈的容 量至少应该是（ B ） A.2 B.3 C.5 D.6 6.若用一个大小为6的数组来实现循环队列，且当前rear 和front的值分别为0和3，当从队列中删除一个元素， 再加入两个元素后，rear和front的值分别为( B )。 A. 1和5 B. 2和4 C. 4和2 D. 5和1 7.循环队列A[0..m-1]存放其元素值，用front和rear分别表 示队头和队尾，则当前队列中的元素数是(A ) A.(rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front