第3章 栈和队列

第三章栈和队列基本概念1、栈的定义、特点2、顺序栈和链栈的进栈和退栈操作；栈空和栈满的判定条件3、队列的定义和特点4、循环队列、链队列的出队和入队操作、判定队列为空、队列为满的条件一、选择题1、一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（）。A.a,b,c,d,eB.d,e,c,b,aC.d,c,e,a,bD.e,d,c,b,a2、判断一个循环队列Q（最多n个元素）为满的条件是（）。A.Q-rear==Q-frontB.Q-rear==Q-front+1C.Q-front==(Q-rear+1)%nD.Q-front==(Q-rear-1)%n3、设计一个判别表达式中括号是否配对的算法，采用（）数据结构最佳。A.顺序表B.链表C.队列D.栈4、带头结点的单链表head为空的判定条件是（）。A.head==NULLB.head-next==NULLC.head-next!=NULLD.head!=NULL5、一个栈的输入序列为：1,2,3,4，则栈的不可能输出的序列是（）。A.1243B.2134C.1432D.4312E.32146、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。A.1和5B.2和4C.4和2D.5和1大小为6的数组：下标从0-5;从前面出队，从后面入队front(前面)=3rear(后面)=0当出队列中删除一个元素，也就是出队，即front+1:=4再插入两个元素，即rear+2=27、队列的插入操作是在（）。A.队尾B.队头C.队列任意位置D.队头元素后8、循环队列的队头和队尾指针分别为front和rear，则判断循环队列为空的条件是（）。A.front==rearB.front==0C.rear==0D.front=rear+19、一个顺序栈S，其栈顶指针为top，则将元素e入栈的操作是（）。A.*S-top=e;S-top++;B.S-top++;*S-top=e;C.*S-top=eD.S-top=e;10、表达式a*(b+c)-d的后缀表达式是（）。A.abcd+-B.abc+*d-C.abc*+d-D.-+*abcd11、将递归算法转换成对应的非递归算法时，通常需要使用（）来保存中间结果。A.队列B.栈C.链表D.树12、栈的插入和删除操作在（）。A.栈底B.栈顶C.任意位置D.指定位置13、五节车厢以编号1，2，3，4，5顺序进入铁路调度站（栈），可以得到（）的编组。A.3，4，5，1，2B.2，4，1，3，5C.3，5，4，2，1D.1，3，5，2，414、判定一个顺序栈S（栈空间大小为n）为空的条件是（）。A.S-top==0B.S-top!=0C.S-top==nD.S-top!=n15、在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（）。A.front=front-nextB.s-next=rear;rear=sC.rear-next=s;rear=s;D.s-next=front;front=s;16、一个队列的入队序列是1，2，3，4，则队列的出队序列是（）。A.1，2，3，4B.4，3，2，1C.1，4，3，2D.3，4，1，217、依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（）。A.aB.bC.cD.d18、正常情况下，删除非空的顺序存储结构的堆栈的栈顶元素，栈顶指针top的变化是（）。A.top不变B.top=0C.top=top+1D.top=top-119、判断一个循环队列Q（空间大小为M）为空的条件是（A）。A.Q-front==Q-rearB.Q-rear-Q-front-1==MC.Q-front+1=Q-rearD.Q-rear+1=Q-front20、设计一个判别表达式中左右括号是否配对出现的算法，采用（C）数据结构最佳。A.线性表的顺序存储结构B.队列C.栈D.线性表的链式存储结构21、当用大小为N的数组存储顺序循环队列时，该队列的最大长度为（C）。A.NB.N+1C.N-1D.N-222、队列的删除操作是在（A）。A.队首B.队尾C.队前D.队后23、若让元素1，2，3依次进栈，则出栈次序不可能是（C）。A.3，2，1B.2，1，3C.3，1，2D.1，3，224、循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（A）。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front25、在解决计算机主机和打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（B）结构。A.堆栈B.队列C.数组D.线性表26、栈和队列都是（C）。A.链式存储的线性结构B.链式存储的非线性结构C.限制存取点的线性结构D.限制存取点的非线性结构27、在一个链队列中，假定front和rear分别为队头指针和队尾指针，删除一个结点的操作是（A）。A.front=front-nextB.rear=rear-nextC.rear-next=frontD.front-next=rear28、队和栈的主要区别是（D）。A.逻辑结构不同B.存储结构不同C.所包含的运算个数不同D.限定插入和删除的位置不同2.栈结构通常采用的两种存储结构是____。A.顺序存储结构和链式存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构4.判定一个顺序栈ST（最多元素为m0）为空的条件是____。A.top!=0B.top==0C.top!=m0D.top==m0-15.判定一个顺序栈ST（最多元素为m0）为栈满的条件是____。A.top！=0B.top==0C.top！=m0D.top==m0-17.向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行____。(不带空的头结点)A.HS—＞next=s;B.s—＞next=HS—＞next;HS—＞next=s;C.s—＞next=HS;HS=s;D.s—＞next=HS;HS=HS—＞next;8.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行____。(不带空的头结点)A.x=HS;HS=HS—＞next;B.x=HS—＞data;C.HS=HS—＞next;x=HS—＞data;D.x=HS—＞data;HS=HS—＞next;10.判定一个循环队列QU（最多元素为m0）为空的条件是____。A.rear-front==m0B.rear-front-1==m0C.front==rearD.front==rear+111.判定一个循环队列QU（最多元素为m0,m0==Maxsize-1）为满队列的条件是____。A.((rear-front)+Maxsize)%Maxsize==m0B.rear-front-1==m0C.front==rearD.front==rear+113.栈和队列的共同点是____。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点二、填空题1、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是。答案：3设栈长度为s，起始为0因为栈后进先出，队列先进先出。又因为元素E1.。E6是顺序入栈，那么分析过程如下：按照出栈过程分析，因为给定出栈顺序：E2,E4,E3,E6,E5,E1,E2要进栈，所以E1必须进栈，进栈顺序：E1,E2，所以s为2下面E2出栈，打印出E2，剩余结果为E4,E3,E6,E5,E1,因为E2出栈了，所以当前栈容量为2，但是只是用了1个，存放E1，下面继续E3进栈，E4进栈，此时s为3，根据出栈结果，那么E4出栈，E3出栈，此时栈容量为3但是只有E1在栈中，剩余结果为E6,E5,E1,同理，E5进栈，E6进栈，此时栈被填满，容量为3，后E6出栈，E5出栈，E1出栈，栈空，容量为3.所以S的容量至少为3.2、一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和rear，则循环队列中元素的个数为：。答案：(rear-front+M)%M3、在具有n个元素的循环队列中，队满时具有个元素。答案：n-14、设循环队列的容量为70，现经过一系列的入队和出队操作后，front为20，rear为11，则队列中元素的个数为。答案：61元素数量=(rear+max-front)当frontrear(front+max-rear)当rearfront5、已知循环队列的存储空间大小为20，且当前队列的头指针和尾指针的值分别为8和3，且该队列的当前的长度为____15___。20+3-8三、判断题1、栈和队列都是受限的线性结构。2、在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种随机存取结构。3、以链表作为栈的存储结构，出栈操作必须判别栈空的情况。四、程序分析填空题1、已知栈的基本操作函数：intInitStack(SqStack*S);//构造空栈intStackEmpty(SqStack*S);//判断栈空intPush(SqStack*S,ElemTypee);//入栈intPop(SqStack*S,ElemType*e);//出栈函数conversion实现十进制数转换为八进制数，请将函数补充完整。voidconversion(){InitStack(S);scanf(“%d”,&N);while(N){（1）;N=N/8;}while(（2）){Pop(S,&e);printf(“%d”,e);}}//conversion答案：（1）Push(S,N%8)（2）!StackEmpty(S)2、写出算法的功能。intfunction(SqQueue*Q,ElemType*e){if(Q-front==Q-rear)returnERROR;*e=Q-base[Q-front];Q-front=(Q-front+1)%MAXSIZE;returnOK;}若循环队列非空，队头元素出队列且返回其值，否则返回空元素。3、阅读算法f2,并回答下列问题：（1）设队列Q=（1，3，5，2，4，6）。写出执行算法f2后的队列Q;（2）简述算法f2的功能。voidf2(Queue*Q){DataTypee;if(!QueueEmpty(Q)){e=DeQueue(Q);f2(Q);EnQueue(Q,e);}}答案：（1）6,4,2,5,3,1（2）将队列倒置五、综合题1、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列算法（用函数实现）。rear答案：voidEnQueue(Lnode*rear,ElemTypee){Lnode*new;New=(Lnode*)malloc(sizeof(Lnode));If(!new)returnERROR;new-data=e;new-next=rear-next;rear-next=new;rear=new;}2、已知Q是一个非空队列，S是一个空栈。编写算法，仅用队列和栈的ADT函数和少量工作变量，将队列Q的所有元素逆置。栈的ADT函数有：voidmakeEmpty(SqStacks);置空栈voidpush(SqStacks,ElemTypee);元素e入栈ElemTypepop(SqStacks);出栈，返回栈顶元素intisEmpty(SqStacks);