數(shù)據(jù)結(jié)構(gòu)第章棧和隊(duì)列習(xí)題課

習(xí)題課第3章棧和隊(duì)列3.1(1)123,132,213,231,321(2)435612不能得到（6出站時(shí)，12必須在站中，只能出站成21，無法得到12）135426可以1S1X2S3S3X4S5S5X4X2X6S6X（1）如果進(jìn)站的車廂序列為123，則可能得到的出站車廂序列是什么?（2）如果進(jìn)站的車廂序列為123456，則能否得到435612和135426出站序列，并請說明為什么不能得到或如何得到。3.4簡述以下算法的功能分析：while循環(huán)將棧中數(shù)據(jù)依次出棧到A數(shù)組for循環(huán)將數(shù)組A中元素依次入棧結(jié)果：將堆棧中的元素逆序（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簡述以下算法的功能分析：第一個(gè)while循環(huán)：將S棧中不等于e的元素放入T棧。最后S為空棧第二個(gè)while循環(huán)：將T棧中元素出棧到S棧

結(jié)果：將堆棧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寫出以下程序段的輸出結(jié)果分析：[隊(duì)列]xy1.[h]ec2.[hr]ec3.[hrc]ec4.[rc]hc5.[rch]hc6.[ch]rc7.[cha]rc結(jié)果：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作為雙端隊(duì)列的輸入序列，分別求出滿足以下條件的輸出序列解：可能的組合（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）能由輸入受限的雙端隊(duì)列得到，但不能由輸出受限的雙端隊(duì)列得到的輸出序列（2）能由輸出受限的雙端隊(duì)列得到，但不能由輸入受限的雙端隊(duì)列得到的輸出序列（3）既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列3.16n節(jié)硬席或軟席車廂調(diào)度成軟席在硬席之前HSSHS=>SSSHH思路：判斷每節(jié)車廂，如果是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帶頭指針的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)，編寫隊(duì)列初始化、入隊(duì)列和出隊(duì)列算法typedefstructQNode{ QElemType data; StructQnode *next;}QNode,*QueuePtr;typedefstruct{ QueuePtr rear;}LinkQueue;StatusInitQueue(LinkQueue&T){//構(gòu)造一個(gè)帶表頭結(jié)點(diǎn)的只有一個(gè)尾指針的空隊(duì)列TT.rear=(QueuePtr)malloc(sizeof(QNode);if(!T.rear)return“ERROR”;T->next=T; returnOK;}3.28帶頭指針的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)，編寫隊(duì)列初始化、入隊(duì)列和出隊(duì)列算法StatusEnQueue(LinkQueue&T,QElemTypee){ //插入元素e為隊(duì)列T的新的隊(duì)尾元素 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帶頭指針的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)，編寫隊(duì)列初始化、入隊(duì)列和出隊(duì)列算法StatusDeQueue(LinkQueue&T,QElemType&e){ //若隊(duì)列不為空，刪除隊(duì)頭元素用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）設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序是bdcfeag，則棧S的容量至少是

A．1

B.2

C.3

D.4

2010一1、若元素a,b,c,d,e,f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行。但不允許連續(xù)三次進(jìn)行退棧工作，則不可能得到的出棧序列是（