得线性表。
3、3 写出下列程序段得输出结果（栈得元素类型SElemType为char）。
void main() { } 解：stack
3、4 简述以下算法得功能（栈得元素类型SElemType为int）。
(1) status algo1(Stack S) {
} { }
Stack T; int d; InitStack(T);
while(!StackEmpty(S)){ }
while(!StackEmpty(T)){ }
Pop(T,d); Push(S,d); Pop(S,d);
if(d!=e) Push(T,d); int i,n,A[255]; n=0;
while(!StackEmpty(S)) { n++; Pop(S,A[n]); } for(i=1;i<=n;i++) Push(S,A[i]); Stack S; char x,y; InitStack(S); x= ‘c’; y= ‘k’; Push(S,x);
Push(S, ‘a’);
Push(S,y);
Pop(S,x); Push(S, ‘t’); Pop(S,x); Push(S, ‘s’);
while(!StackEmpty(S)) { Pop(S,y); printf(y); } printf(x);
Push(S,x);
(2) status algo2(Stack S,int e)
解：(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得到得输出序列为则在输出序列中不可能出现这样得情形：存在着i p1p2?pn(它就是输入序列得一个排列)， pj 解：这个问题与3、1题比较相似。因为输入序列就是从小到大排列得，所以若理解为通过输入序列 pjpkpi可以得到输出序列pipjpk，显然通过序列123就是无法得到312得， pj 3、7 按照四则运算加、减、乘、除与幂运算(↑)优先关系得惯例，并仿照教科书3、2节例3-2得格式，画出对下列算术表达式求值时操作数栈与运算符栈得变化过程：遠聂构纣粮頰帅。 A-B×C/D+E↑F OPND栈 A A A B A B A B C A G A G A G D A H I I I E I E I E F I J K 输入字符 A-B*C/D+E^F# -B*C/D+E^F# B*C/D+E^F# *C/D+E^F# C/D+E^F# /D+E^F# /D+E^F# D+E^F# +E^F# +E^F# +E^F# E^F# ^F# F# # # # 主要操作 PUSH(OPND,A) PUSH(OPTR,-) PUSH(OPND,B) PUSH(OPTR,*) PUSH(OPND,C) Operate(B,*,C) PUSH(OPTR,/) PUSH(OPND,D) Operate(G,/,D) Operate(A,-,H) PUSH(OPTR,+) PUSH(OPND,E) PUSH(OPTR,^) PUSH(OPND,F) Operate(E,^,F) Operate(I,+,J) RETURN 解：BC=G G/D=H A-H=I E^F=J I+J=K 步骤 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 OPTR栈 # # #- #- #-* #-* #- #-/ #-/ #- # #+ #+ #+^ #+^ #+ # 3、8 试推导求解n阶梵塔问题至少要执行得move操作得次数。 解：2n?1 3、9 试将下列递推过程改写为递归过程。 void ditui(int n) { int i; i = n; } 解： while(i>1) cout< void ditui(int j) { } 3、10 试将下列递归过程改写为非递归过程。 void test(int &sum) { } 解： void test(int &sum) { } 3、11 简述队列与堆栈这两种数据类型得相同点与差异处。 解：栈就是一种运算受限得线性表，其限制就是仅允许在表得一端进行插入与删除运算。 Stack s; InitStack(s); int x; do{ cin>>x; Push(s,x); int x; cin>>x; if(x==0) sum=0; else { } cout< test(sum); sum+=x; if(j>1){ } return; cout< }while(x>0); while(!StackEmpty(s)){ } DestoryStack(s); Pop(s,x); sum+=x; cout< 队列也就是一种运算受限得线性表，其限制就是仅允许在表得一端进行插入，而在表得另一端进行删除。 3、12 写出以下程序段得输出结果（队列中得元素类型QElemType为char）。 void main() { } 解：char 3、13 简述以下算法得功能（栈与队列得元素类型均为int）。 void algo3(Queue &Q) { } 解：队列逆置 3、14 若以1234作为双端队列得输入序列，试分别求出满足以下条件得输出序列： (1) 能由输入受限得双端队列得到，但不能由输出受限得双端队列得到得输出序列。 (2) 能由输出受限得双端队列得到，但不能由输入受限得双端队列得到得输出序列。 Stack S; int d; InitStack(S); while(!QueueEmpty(Q)) { } while(!StackEmpty(S)) { } Pop(S, d); EnQueue(Q, d); DeQueue(Q, d); Push(S, d); Queue Q; InitQueue(Q); char x= ‘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)) { } cout< DeQueue(Q,y); cout< (3) 既不能由输入受限得双端队列得到，也不能由输出受限得双端队列得到得输出序列。 3、15 假设以顺序存储结构实现一个双向栈，即在一维数组得存储空间中存在着两个栈，它们得栈底分别设在数组得两个端点。试编写实现这个双向栈tws得三个操作：初始化inistack(tws)、入栈push(tws,i,x)与出栈pop(tws,i)得算法，其中i为0或1，用以分别指示设在数组两端得两个栈，并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。轂頑籁連該鴻诽。 解： class DStack{ ElemType *top[2]; ElemType *p; int stacksize; int di; public: DStack(int m) { } ~DStack(){delete p;} void Push(int i,ElemType x) { } ElemType Pop(int i) { di=i; if(di==0){ } return OK; if(top[0] if(top[1]>top[0]) return *top[1]--; else cerr<<\di=i; if(di==0){ } else{ } if(top[1] }else{