栈和队列答案

3.1若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答：(1)如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？(2)如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以‘S’表示进栈和以‘X’表示出栈的栈操作序列）。解：(1)123231321213132(2)可以得到135426的出站序列，但不能得到435612的出站序列。因为4356出站说明12已经在栈中，1不可能先于2出栈。3.2简述栈和线性表的差别。解：线性表是具有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或删除操作的线性表。3.3写出下列程序段的输出结果（栈的元素类型SElemType为char）。voidmain(){StackS;charx,y;InitStack(S);x=‘c’;y=‘k’;Push(S,x);Push(S,‘a’);Push(S,y);Pop(S,x);Push(S,‘t’);Push(S,x);Pop(S,x);Push(S,‘s’);while(!StackEmpty(S)){Pop(S,y);printf(y);}printf(x);}解：stack3.4简述以下算法的功能（栈的元素类型SElemType为int）。(1)statusalgo1(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]);}(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);}}解：(1)栈中的数据元素逆置(2)如果栈中存在元素e，将其从栈中清除3.5假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。解：任何前n个序列中S的个数一定大于X的个数。设两个合法序列为：T1=S……X……S……T2=S……X……X……假定前n个操作都相同，从第n+1个操作开始，为序列不同的起始操作点。由于前n个操作相同，故此时两个栈（不妨为栈A、B）的存储情况完全相同，假设此时栈顶元素均为a。第n+1个操作不同，不妨T1的第n+1个操作为S，T2的第n+1个操作为X。T1为入栈操作，假设将b压栈，则T1的输出顺序一定是先b后a；而T2将a退栈，则其输出顺序一定是先a后b。由于T1的输出为……ba……，而T2的输出顺序为……ab……，说明两个不同的合法栈操作序列的输出元素的序列一定不同。3.6试证明：若借助栈由输入序列12…n得到的输出序列为nppp21(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着ijk使jpkpip。解：这个问题和3.1题比较相似。因为输入序列是从小到大排列的，所以若jpkpip，则可以理解为通过输入序列jpkpip可以得到输出序列ipjpkp，显然通过序列123是无法得到312的，参见3.1题。所以不可能存在着ijk使jpkpip。3.7按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例，并仿照教科书3.2节例3-2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A-B×C/D+E↑F解：BC=GG/D=HA-H=IE^F=JI+J=K步骤OPTR栈OPND栈输入字符主要操作1#A-B*C/D+E^F#PUSH(OPND,A)2#A-B*C/D+E^F#PUSH(OPTR,-)3#-AB*C/D+E^F#PUSH(OPND,B)4#-AB*C/D+E^F#PUSH(OPTR,*)5#-*ABC/D+E^F#PUSH(OPND,C)6#-*ABC/D+E^F#Operate(B,*,C)7#-AG/D+E^F#PUSH(OPTR,/)8#-/AGD+E^F#PUSH(OPND,D)9#-/AGD+E^F#Operate(G,/,D)10#-AH+E^F#Operate(A,-,H)11#I+E^F#PUSH(OPTR,+)12#+IE^F#PUSH(OPND,E)13#+IE^F#PUSH(OPTR,^)14#+^IEF#PUSH(OPND,F)15#+^IEF#Operate(E,^,F)16#+IJ#Operate(I,+,J)17#K#RETURN3.8试推导求解n阶梵塔问题至少要执行的move操作的次数。解：12n3.9试将下列递推过程改写为递归过程。voidditui(intn){inti;i=n;while(i1)couti--;}解：voidditui(intj){if(j1){coutj;ditui(j-1);}return;}3.10试将下列递归过程改写为非递归过程。voidtest(int&sum){intx;cinx;if(x==0)sum=0;else{test(sum);sum+=x;}coutsum;}解：voidtest(int&sum){Stacks;InitStack(s);intx;do{cinx;Push(s,x);}while(x0);while(!StackEmpty(s)){Pop(s,x);sum+=x;coutsumendl;}DestoryStack(s);}3.11简述队列和堆栈这两种数据类型的相同点和差异处。解：栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。3.12写出以下程序段的输出结果（队列中的元素类型QElemType为char）。voidmain(){QueueQ;InitQueue(Q);charx=‘e’,y=‘c’;EnQueue(Q,‘h’);EnQueue(Q,‘r’);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,‘a’);While(!QueueEmpty(Q)){DeQueue(Q,y);couty;}coutx;}解：char3.13简述以下算法的功能（栈和队列的元素类型均为int）。voidalgo3(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);}while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}解：队列逆置3.14若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列：(1)能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。(2)能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。(3)既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。3.15假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。解：classDStack{ElemType*top[2];ElemType*p;intstacksize;intdi;public:DStack(intm){p=newElemType[m];if(!p)exit(OVERFLOW);top[0]=p+m/2;top[1]=top[0];stacksize=m;}~DStack(){deletep;}voidPush(inti,ElemTypex){di=i;if(di==0){if(top[0]=p)*top[0]--=x;elsecerrStackoverflow!;}else{if(top[1]p+stacksize-1)*++top[1]=x;elsecerrStackoverflow!;}}ElemTypePop(inti){di=i;if(di==0){if(top[0]top[1])return*++top[0];elsecerrStackempty!;}else{if(top[1]top[0])return*top[1]--;elsecerrStackempty!;}returnOK;}};//链栈的数据结构及方法的定义typedefstructNodeType{ElemTypedata;NodeType*next;}NodeType,*LinkType;typedefstruct{LinkTypetop;intsize;}Stack;voidInitStack(Stack&s){s.top=NULL;s.size=0;}voidDestroyStack(Stack&s){LinkTypep;while(s.top){p=s.top;s.top=p-next;deletep;s.size--;}}voidClearStack(Stack&s){LinkTypep;while(s.top){p=s.top;s.top=p-next;deletep;s.size--;}}intStackLength(Stacks){returns.size;}StatusStackEmpty(Stacks){if(s.size==0)returnTRUE;elsereturnFALSE;}StatusGetTop(Stacks,ElemType&e){if(!s.top)returnERROR;else{e=s.top-data;returnOK;}}StatusPush(Stack&s,ElemTypee){LinkTypep;p=newNodeType;if(!p)exit(OVERFLOW);p-next=s.top;s.top=p;p-data=e;s.size++;returnOK;}StatusPop(Stack&s,ElemType&e){LinkTypep;if(s.top){e=s.top-data;p=s.top;s.top=p-next;deletep;s.size--;}returnOK;}//从栈顶到栈底用Visit()函数遍历栈中每个数据元素voidStackTraverse(Stacks,Status(*Visit)(ElemTypee)){LinkTypep;p=s.top;while(p)Visit(p-data);}3.16假设如题3.1所属火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）等待调度，试编写算法，输出对这n节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都被调整到硬席车厢之前。解：intmain(){Stacks;charBuffer[80];inti=0,j=0;InitStack(s);cout请输入硬席(H)和软席车厢(S)序列：;cinBuffer;coutBufferendl;while(Buffer[i]){if(Buffer[i]