数据结构第3章练习题

1、数据结构第3章练习题1. 栈和队列的共同点是（栈和队列的共同点是（ ） A.都是先进先出都是先进先出 B.都是先进后出都是先进后出 C.只允许在端点处插入和删除元素只允许在端点处插入和删除元素 D.没有共同点没有共同点个元素个元素a、b、c和和d依次入栈，入栈过程中允许元素出栈，假设某一依次入栈，入栈过程中允许元素出栈，假设某一时刻栈的状态是时刻栈的状态是c（栈顶）、（栈顶）、b、a（栈底），则不可能的出栈顺序（栈底），则不可能的出栈顺序是（是（ ）。）。 A. d,c,b,a B. c,b,d,a C. c,a,d,b D. c,d,b,a 3.向一个栈顶指针为向一个栈顶指针为Top的链栈中

2、插入一个的链栈中插入一个p所指结点时，其操作步所指结点时，其操作步骤为（骤为（ ） 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.在顺序循环队列中，队尾指针指向队尾元素的在顺序循环队列中，队尾指针指向队尾元素的( )位置位置A. 前一个前一个 B. 后一个后一个 C. 当前当前 D. 以上都不对以上都不对第第3章练习题章练习题CCCB5. 设有一顺序栈设有一顺序栈S，元素，元素a，b，c，d，e，f依次进栈，如果依次进栈，如果6个个元素出栈的顺序是元素出栈的

3、顺序是b，d，c，f，e，a，则栈的容量至少应该，则栈的容量至少应该是（是（ ） 6.若用一个大小为若用一个大小为6的数组来实现循环队列，且当前的数组来实现循环队列，且当前rear和和front的值分别为的值分别为0和和3，当从队列中删除一个元素，再加入两个元，当从队列中删除一个元素，再加入两个元素后，素后，rear和和front的值分别为的值分别为( )。 A. 1和和5 B. 2和和4 C. 4和和2 D. 5和和17.循环队列循环队列A0.m-1存放其元素值，用存放其元素值，用front和和rear分别表示队分别表示队头和队尾，则当前队列中的元素数是头和队尾，则当前队列中的元素数是( )

4、A.(rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-frontBBA8. 循环队列存储在数组循环队列存储在数组A0.m中，则入队时的操作为中，则入队时的操作为( )A. rear=rear+1 B. rear=(rear+1) % (m-1)C. rear=(rear+1) % m D. rear=(rear+1)%(m+1) 9.判定一个循环队列判定一个循环队列Q（存放元素位置（存放元素位置0MaxSize-1）队满的）队满的条件是（条件是（ ）= B. =(Q.front+1)%MaxSize=(Q.rear+1)%MaxS

5、ize D.Q.front+1=10.用一个大小为用一个大小为N的数组来实现循环队列的数组来实现循环队列Q，则该循环队列为空的，则该循环队列为空的条件是条件是( )。A. = B. Q.rear+1=C. (Q.rear+1)%N= D. (Q.front+1)%N=DCA11.一个队列的入列序列是一个队列的入列序列是1，2，3，4，则队列的输出序列是，则队列的输出序列是（ ）。）。A、4，3，2，1 B、1，2，3，4C、1，4，3，2 D、3，2，4，112.以下代码段是最大长度为以下代码段是最大长度为N的循环队列的循环队列Q的入队操作，请补充完的入队操作，请补充完整。整。Status E

6、nQueue(SqQueue &Q, QElemType e) if( ) return ERROR; /队列满队列满 Q.baseQ.rear=e; ( ); /队尾后移一位队尾后移一位 return OK;(Q.rear+1)%N=;=(Q.rear+1)%N;B13. 设循环顺序队列用数组设循环顺序队列用数组A7（下标从（下标从0开始编号）存放开始编号）存放其元素值，且当前队尾其元素值，且当前队尾rear和队头和队头front的值分别为的值分别为1和和5，当从队列中删除当从队列中删除2个元素，再加入个元素，再加入4个元素后，个元素后，rear的值为的值为（ ），front的值为的值为（

7、），当前队列的长度为，当前队列的长度为（ ）。14.设循环队列的容量为设循环队列的容量为40（序号从（序号从0到到39），现经过一系列的入），现经过一系列的入队和出队运算后，有队和出队运算后，有 front=11，rear=19; front=19，rear=11；问在这两；问在这两种情况下，循环队列中各有元素多少个？种情况下，循环队列中各有元素多少个？505答：答： L=（191140 ）% 40=8 答：答： L=（111940 ）% 40=3215.利用算符优先算法对表达式（利用算符优先算法对表达式（3+5）/2求值，写出求值过程中求值，写出求值过程中操作数栈操作数栈(OPND)和算符栈

8、和算符栈(OPTR)的变化情况。的变化情况。16.写出下列程序段的输出结果（队列中的元素类型写出下列程序段的输出结果（队列中的元素类型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”。17.简述以下算法的功能（栈和队列的元素类型均为简述以下算法的功能（栈和队列的元素类型均为int）void algo3(Queue &Q) Stack S; int d; InitStack(S); while(!Q