数据结构第章栈和队列习题课

习题课第3章栈和队列3.1(1)123,132,213,231,321(2)435612不能得到（6出站时，12必须在站中，只能出站成21，无法得到12）135426可以1S1X2S3S3X4S5S5X4X2X6S6X（1）如果进站的车厢序列为123，则可能得到的出站车厢序列是什么?（2）如果进站的车厢序列为123456，则能否得到435612和135426出站序列，并请说明为什么不能得到或如何得到。3.4简述以下算法的功能分析：while循环将栈中数据依次出栈到A数组for循环将数组A中元素依次入栈结果：将堆栈中的元素逆序（1）statusalgol(StackS){intI,n,A[255];n=0;while(!Stackempty(S)){n++;Pop(S,A[n]);}for(i=1;i<=n;i++)Push(S,A[i]);}3.4简述以下算法的功能分析：第一个while循环：将S栈中不等于e的元素放入T栈。最后S为空栈第二个while循环：将T栈中元素出栈到S栈

结果：将堆栈S中不等于e的元素逆序（2）statusalgo2(StackS,inte){StackT;intd;InitStack(T);while(!StackEmpty(S)){Pop(S,d);if(d!=e)Push(T,d);}while(!Stackempty(T)){Pop(T,d);Push(S,d);}}3.12写出以下程序段的输出结果分析：[队列]xy1.[h]ec2.[hr]ec3.[hrc]ec4.[rc]hc5.[rch]hc6.[ch]rc7.[cha]rc结果：charVoidmain(){QueueQ;InitQueue(Q);charx=‘e’,y=‘c’;EnQueue(Q,’h’); //1EnQueue(Q,’r’); //2EnQueue(Q,y); //3DeQueue(Q,x); //4Enqueue(Q,x); //5DeQueue(Q,x); //6EnQueue(Q,’a’); //7 while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);}printf(x);}3.14以1234作为双端队列的输入序列，分别求出满足以下条件的输出序列解：可能的组合（24种）1234，1243，1324，1342，1423，1432，2134，2143，2314，2341，2413，2431，3124，3142，3214，3241，3412，3421，4123，4132，4213，4231，4312，4321输入受限不能得到:42134231输出受限不能得到:41324231都不能得到:4231(1)4213(2)4132(3)4231（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列（3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列3.16n节硬席或软席车厢调度成软席在硬席之前HSSHS=>SSSHH思路：判断每节车厢，如果是H的只入栈，如果是S则入栈后出栈InitStack(T);while(入口有车厢e){if(e==‘H’)push(T,e);else{push(T,e);pop(T,e);}}While(!EmptyStack(T))pop(T,e);

3.28带头指针的循环链表表示队列，并且只设一个指针指向队尾结点，编写队列初始化、入队列和出队列算法typedefstructQNode{ QElemType data; StructQnode *next;}QNode,*QueuePtr;typedefstruct{ QueuePtr rear;}LinkQueue;StatusInitQueue(LinkQueue&T){//构造一个带表头结点的只有一个尾指针的空队列TT.rear=(QueuePtr)malloc(sizeof(QNode);if(!T.rear)return“ERROR”;T->next=T; returnOK;}3.28带头指针的循环链表表示队列，并且只设一个指针指向队尾结点，编写队列初始化、入队列和出队列算法StatusEnQueue(LinkQueue&T,QElemTypee){ //插入元素e为队列T的新的队尾元素 p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW); p->data=e;p->next=T.rear->next; T.rear->next=p; T.rear=p; returnOK:}//EnQueue3.28带头指针的循环链表表示队列，并且只设一个指针指向队尾结点，编写队列初始化、入队列和出队列算法StatusDeQueue(LinkQueue&T,QElemType&e){ //若队列不为空，删除队头元素用e返回，并返回OK //否则返回ERROR if(T.rear==T.rear->next)returnERROR; p=T.rear->next->next; e=p->data;T.rear->next->next=p->next; if(T.rear==p)T.rear=T.rear->next; free(p); returnOK;}2009（一、2）设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是

A．1

B.2

C.3

D.4

2010一1、若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（