数据结构第3章栈与队列习题

第3章栈与队列习题一、单选1、有6个元素6、5、4、3、2、1顺序进栈，（C）是非法的出栈序列。A、543612B、453126C、346512D、2341562、设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D）。A、51234B、45132C、43125D、321543、进栈序列为a，b，c，则通过入、出栈可能得到的a，b，c的不同排列个数是（B）。A、4B、5C、6D、74、栈在（D）中应用。A、递归调用B、子程序调用C、表达式求值D、以上全对5、表达式a*(b+c)-d的后缀表达式是(B)。A、abcd*+-B、abc+*d-C、abc*+d-D、-+*abcd6、设计一个判别表达式中左，右括号是否配对出现的算法，采用（D）数据结构最佳。A、线性表的顺序存储结构B、队列C、线性表的链式存储结构D、栈7、用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时(D)。A、仅修改队头指针B、仅修改队尾指针C、队头、队尾指针都要修改D、队头、队尾指针都可能要修改8、递归过程或函数调用时，处理参数及返回地址，要用一种称为（C）的数据结构。A、队列B、多维数组C、栈D、线性表9、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（A）。A、(rear-front+m)%mB、rear-front+1C、(front-rear+m)%mD、(rear-front)%m10、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是(A)。A、(rear-front+m)%mB、rear-front+1C、rear-front-1D、rear-front11、循环队列存储在数组A[0..m]中，则入队时的操作为（D）。A、rear=rear+1B、rear=(rear+1)mod(m-1)C、rear=(rear+1)modmD、rear=(rear+1)mod(m+1)12、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？(A)A、1和5B、2和4C、4和2D、5和113、栈和队列的共同点是（C）。A、都是先进先出B、都是先进后出C、只允许在端点处插入和删除元素D、没有共同点14、栈和队都是（C）。A、顺序存储的线性结构B、链式存储的非线性结构C、限制存取点的线性结构D、限制存取点的非线性结构15、栈的操作原则是（C）。A、顺序进出B、后进后出C、后进先出D、先进先出16、下面术语中，与数据的存储结构无关的是（B）。A、循环队列B、栈C、顺序栈D、顺序表17、栈和队列具有相同的（B）。A、抽象数据类型B、逻辑结构C、存储结构D、运算18、（B）不是栈的基本运算。A、删除栈顶元素B、删除栈底元素C、入栈D、栈置空19、递归算法必须包括（B）。A、递归部分B、终止条件和递归部分C、迭代部分D、终止条件和迭代部分20、表达式3*2^(4+2*2–6*3)–5在求值过程在，当扫描到6时，数字栈中内容为（B）。A、3,2,4,1,1B、3,2,8C、3,2,4,2,2D、以上都不对21、设栈S和队列Q初始状态为空，元素a1，a2，a3，a4，a5和a6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素的出队序列是a2，a4，a3，a6，a5和a1，则栈S的容量至少是（C）。A、6B、4C、3D、2二、算法阅读与设计1、简述下面算法的功能（假设栈中元素类型为整数类型）。假设从键盘上输入一批整数，依次为：786345309134–1，写出下面算法的输出结果。structstack{elemtypestack[stackmaxsize];inttop;};voidmain(){stacka;initstack(a);intx;scanf(x);while(x!=–1){push(a,x);scanf(x);}while(!stackempty(a))printf(“%d\n”,pop(a));}功能：把整数依次输入栈，再输出，实现逆序排列结果：-1,34,91,30,45,63,782、L为带头结点的单链表，表中元素为整数。利用栈判断L是否是对称的。structstack{elemtypestack[stackmaxsize];inttop;};voidmain(){stacka;initstack(a);int*P;p=h-next;while(p!=0){push(a,*p);p=p-next;}while(!stackempty(a)){if(pop(a)!=*p){printf(“No”);break;}p=p-next;}3、假设将循环队列定义为：以rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。给出此循环队列的队满条件，并给出相应的入队和出队算法。typedefcharQElemType;typedefstruct{QElemTypeelem[MAXQSIZE];intlength;intrear;}Queue;StatusEnCQueue(Queue&Q,QElemTypex){if(Q.length==MAXQSIZE){returnERROR;}if(MAXQSIZE-1!=Q.rear){++Q.rear;Q.elem[Q.rear]=x;}else{Q.rear=0;Q.elem[Q.rear]=x;}++Q.length;returnOK;}StatusDeCQueue(Queue&Q,QElemType&x){if(!Q.length){returnERROR;}if(Q.rear+1=Q.length){x=Q.elem[Q.rear+1-Q.length];}else{x=Q.elem[MAXQSIZE+Q.rear+1-Q.length];}--Q.length;returnOK;}