栈和队列答案.doc

《栈和队列答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、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简述栈和线性

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);}pri

3、ntf(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(!

4、StackEmpty(T)){Pop(T,d);Push(S,d);}}解：(1)栈中的数据元素逆置(2)如果栈中存在元素e，将其从栈中清除3.5假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。解：任何前n个序列中S的个数一定大

5、于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、.6试证明：若借助栈由输入序列12…n得到的输出序列为(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i

7、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

8、#-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#