搜索
一选择题1.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（A）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m2.循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素是(A)。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front3.循环队列存储在数组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)4.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？(B)A.1和5B.2和4C.4和2D.5和15.用单链表表示的链式队列的队头在链表的（A）位置。A．链头B．链尾C．链中二判断题1.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（×）2.通常使用队列来处理函数或过程的调用。（×）3.队列逻辑上是一个下端和上端既能增加又能减少的线性表。（√）4.循环队列通常用指针来实现队列的头尾相接。（×）5.循环队列也存在空间溢出问题。（√）6.队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（×）7.栈和队列都是线性表，只是在插入和删除时受到了一些限制。（√）三应用题1.简要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满时的队首指针与队尾指针的值。解：typedefstructnode{elemtypeelemcq[m];//m为队列最大可能的容量。intfront,rear;//front和rear分别为队头和队尾指针。}cqnode;cqnodecq;(1)初始状态cq.front=cq.rear=0;(2)队列空cq.front==cq.rear;(3)队列满(cq.rear+1)%m==cq.front;2.设一个双端队列，元素进入该队列的次序为a，b，c，d。求既不能由输入受限的双端队列得到,又不能由输出受限的双端队列得到的输出序列。答：既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是dbca分析：4个输入受限有：cdba，dacb，dabd，dcab4个输出受限有：cdba，dacb，dbac，dcab既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是dbca。3.若以1、2、3、4作为双端队列的输入序列，试分别求出以下条件的输出序列：（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；（3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。答：4个输入受限有：4321，4123，4132，43124个输出受限有：4321，4123，4213，4312（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；答：4个输出受限有：4321，4123，4213，43124个输入受限有：4321，4123，4132，4312（3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。答：输出受限与输入受限都得不到4231。试题分析：若以1234作为双端队列的输入序列.问:能由输入受限的双端队列得到,但是不能由输出受限的双端队列得到的输出序列是什么?双端队列确是好像两个栈底靠在一起的栈，但这两个栈底又是互通的。它确是很灵活，因此不可能出现的出队的序列只可能是四个车厢都已经入队的情况，因为如果队列中只有1个或2个或3个都是能调度过来的，但当4个都进去之后就受一定限制了，对于输入受限的双端队列此时队列中车厢的排列必定是1234,因此尽管两头都能出去，也不可能出现是42**这样的出队序列，而对于输出受限的双端队列，无论怎么进去，在队列中也形不成4132和4231这样的序列。4.假设以数组sq[0..7]存放循环队列元素,变量f指向队头元素的前一位置,变量r指向队尾元素，如用A和D分别表示入队和出队操作，请给出：（1）队空的初始条件;（2）执行操作序列A3D1A5D2A1D2A4时的状态,并作必要的说明。答：（1）队空的初始条件：f=r=0；（2）执行操作A3后，r=3；//A3表示三次入队操作执行操作D1后，f=1；//D1表示一次出队操作执行操作A5后，r=0；执行操作D2后，f=3；执行操作A1后，r=1；执行操作D2后，f=5；执行操作A4后，按溢出处理。因为执行A3后，r=4，这时队满，若再执行A操作，则出错。四、算法设计题1.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列和出队列算法答：本题用类C语言编写入队和出队算法。（1）voidEnQueue(LinkedListrear,ElemTypex)//rear是带头结点的循环链队列的尾指针，本算法将元素x插入到队尾。{s=(LinkedList)malloc(sizeof(LNode));//申请结点空间s-data=x;s-next=rear-next;//将s结点链入队尾rear-next=s;rear=s;//rear指向新队尾}（2）voidDeQueue(LinkedListrear)//rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素；否则给出出错信息。{if(rear-next==rear){printf(“队空\n”);exit(0);}s=rear-next-next;//s指向队头元素，rear-next-next=s-next;//队头元素出队。printf(“出队元素是”，s-data);if(s==rear)rear=rear-next;//空队列free(s);}2.如果允许在循环队列的两端都可以进行插入和删除操作。要求：（1）写出循环队列的类型定义；（2）写出“从队尾删除”和“从队头插入”的算法。答：[题目分析]用一维数组v[0..M-1]实现循环队列，其中M是队列长度。设队头指针front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队空，(rear+1)%m=front为队满。约定队头端入队向下标大的方向发展，队尾端入队向下标大的方向发展。（1）#defineM队列可能达到的最大长度typedefstruct{elemtpdata[M];intfront,rear;}cycqueue;（2）elemtpdelqueue(cycqueueQ)//Q是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，否则给出出错信息。{if(Q.front==Q.rear){printf(“队列空”);exit(0);}Q.rear=(Q.rear-1+M)%M;//修改队尾指针。return(Q.data[(Q.rear+1+M)%M]);//返回出队元素。}//从队尾删除算法结束voidenqueue(cycqueueQ,elemtpx)//Q是顺序存储的循环队列，本算法实现“从队头插入”元素x。{if(Q.rear==(Q.front-1+M)%M){printf(“队满”;exit(0);)Q.data[Q.front]=x;//x入队列Q.front=(Q.front+1+M)%M;//修改队头指针。}//结束从队头插入算法。3、已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量，使用Pascal或C语言编写一个算法，将队列Q中的所有元素逆置。栈的ADT函数有：makeEmpty(s:stack);置空栈push(s:stack;value:datatype);新元素value进栈pop(s:stack):datatype;出栈，返回栈顶值isEmpty(s:stack):Boolean;判栈空否队列的ADT函数有：enqueue(q:queue:value:datatype);元素value进队deQueue(q:queue):datatype;出队列，返回队头值isEmpty(q:queue):boolean;判队列空否答：[题目分析]根据队列先进先出和栈后进先出的性质，先将非空队列中的元素出队，并压入初始为空的栈中。这时栈顶元素是队列中最后出队的元素。然后将栈中元素出栈，依次插入到初始为空的队列中。栈中第一个退栈的元素成为队列中第一个元素，最后退栈的元素（出队时第一个元素）成了最后入队的元素，从而实现了原队列的逆置。voidInvert(queueQ)//Q是一个非空队列，本算法利用空栈S和已给的几个栈和队列的ADT函数，将队列Q中的元素逆置。{makempty(S);//置空栈while(!isEmpty(Q))//队列Q中元素出队{value=deQueue(Q);push(S,value);}//将出队元素压入栈中while(!isEmpty(S))//栈中元素退栈{value=pop(S);enQueue(Q,value);}//将出栈元素入队列Q}//算法invert结束