关注公众号凡花花的小窝，收获更多的考研计算机专业编程相关的资料 第3章 栈和队列 3.1 若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答： (1) 如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？ (2) 如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以 ‘S’表示进栈和以 ‘X’表示出栈的栈操作序列）。 　　解：(1) 123 231 321 213 132 (2) 可以得到135426的出站序列，但不能得到435612的出站序列。因为4356出站说明12已经在栈中，1不可能先于2出栈。 3.2 简述栈和线性表的差别。 　　解：线性表是具有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或删除操作的线性表。 3.3 写出下列程序段的输出结果（栈的元素类型SElemType为char）。 void main() { 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’); Push(S,x); Pop(S,x); Push(S, ‘s’); while(!StackEmpty(S)) { Pop(S,y); printf(y); } printf(x); } 　　解：stack 3.4 简述以下算法的功能（栈的元素类型SElemType为int）。 (1) status algo1(Stack S) { 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]); } (2) status algo2(Stack S,int e) { Stack T; int d; 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得到的输出序列为(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i<j<k使<<。 　　解：这个问题和3.1题比较相似。因为输入序列是从小到大排列的，所以若<<，则可以理解为通过输入序列可以得到输出序列，显然通过序列123是无法得到312的，参见3.1题。所以不可能存在着i<j<k使<<。 3.7 按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例，并仿照教科书3.2节例3-2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程： A-B×C/D+E↑F 　　解：BC=G G/D=H A-H=I E^F=J I+J=K 步骤 OPTR栈 OPND栈 输入字符 主要操作 1

A-B*C/D+E^F# PUSH(OPND,A) 2

A -BC/D+E^F# PUSH(OPTR,-) 3 #- A BC/D+E^F# PUSH(OPND,B) 4 #- A B C/D+E^F# PUSH(OPTR,) 5 #-* A B C/D+E^F# PUSH(OPND,C) 6 #-* A B C /D+E^F# Operate(B,*,C) 7 #- A G /D+E^F# PUSH(OPTR,/) 8 #-/ A G D+E^F# PUSH(OPND,D) 9 #-/ A G D +E^F# Operate(G,/,D) 10 #- A H +E^F# Operate(A,-,H) 11

I +E^F# PUSH(OPTR,+) 12 #+ I E^F# PUSH(OPND,E) 13 #+ I E ^F# PUSH(OPTR,^) 14 #+^ I E F# PUSH(OPND,F) 15 #+^ I E F

Operate(E,^,F) 16 #+ I J

Operate(I,+,J) 17

K

RETURN 3.8 试推导求解n阶梵塔问题至少要执行的move操作的次数。 　　解： 3.9 试将下列递推过程改写为递归过程。 void ditui(int n) { int i; i = n; while(i>1) cout<<i–; } 　　解： void ditui(int j) { if(j>1){ cout<<j; ditui(j-1); } return; } 3.10 试将下列递归过程改写为非递归过程。 void test(int &sum) { int x; cin>>x; if(x0) sum=0; else { test(sum); sum+=x; } cout<<sum; } 　　解： void test(int &sum) { Stack s; InitStack(s); int x; do{ cin>>x; Push(s,x); }while(x>0); while(!StackEmpty(s)){ Pop(s,x); sum+=x; cout<<sum<<endl; } DestoryStack(s); } 3.11 简述队列和堆栈这两种数据类型的相同点和差异处。 　　解：栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。 队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。 3.12 写出以下程序段的输出结果（队列中的元素类型QElemType为char）。 void main() { 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)) { DeQueue(Q,y); cout<<y; } cout<<x; } 　　解：char 3.13 简述以下算法的功能（栈和队列的元素类型均为int）。 void algo3(Queue &Q) { Stack S; int d; 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，用以分别指示设在数组两端的两个栈，并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。 　　解： class DStack{ ElemType *top[2]; ElemType *p; int stacksize; int di; public: DStack(int m) { p=new ElemType[m]; if(!p) exit(OVERFLOW); top[0]=p+m/2; top[1]=top[0]; stacksize=m; } ~DStack(){delete p;} void Push(int i,ElemType x) { di=i; if(di0){ if(top[0]>=p) *top[0]–=x; else cerr<<“Stack overflow!”; } else{ if(top[1]<p+stacksize-1) *++top[1]=x; else cerr<<“Stack overflow!”; } } ElemType Pop(int i) { di=i; if(di==0){ if(top[0]<top[1]) return *++top[0]; else cerr<<“Stack empty!”; }else{ if(top[1]>top[0]) return *top[1]–; else cerr<<“Stack empty!”; } return OK; } };

// 链栈的数据结构及方法的定义 typedef struct NodeType{ ElemType data; NodeType *next; }NodeType,*LinkType; typedef struct{ LinkType top; int size; }Stack;

void InitStack(Stack &s) { s.top=NULL; s.size=0; }

void DestroyStack(Stack &s) { LinkType p; while(s.top){ p=s.top; s.top=p->next; delete p; s.size–; } }

void ClearStack(Stack &s) { LinkType p; while(s.top){ p=s.top; s.top=p->next; delete p; s.size–; } }

int StackLength(Stack s) { return s.size; }

Status StackEmpty(Stack s) { if(s.size==0) return TRUE; else return FALSE; }

Status GetTop(Stack s,ElemType &e) { if(!s.top) return ERROR; else{ e=s.top->data; return OK; } }

Status Push(Stack &s,ElemType e) { LinkType p; p=new NodeType; if(!p) exit(OVERFLOW); p->next=s.top; s.top=p; p->data=e; s.size++; return OK; }

Status Pop(Stack &s,ElemType &e) { LinkType p; if(s.top){ e=s.top->data; p=s.top; s.top=p->next; delete p; s.size–; } return OK; } // 从栈顶到栈底用Visit()函数遍历栈中每个数据元素 void StackTraverse(Stack s,Status (*Visit)(ElemType e)) { LinkType p; p=s.top; while§ Visit(p->data); } 3.16 假设如题3.1所属火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）等待调度，试编写算法，输出对这n节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都被调整到硬席车厢之前。 　　解： int main() { Stack s; char Buffer[80]; int i=0,j=0; InitStack(s); cout<<“请输入硬席(H)和软席车厢(S)序列：”; cin>>Buffer; cout<<Buffer<<endl; while(Buffer[i]){ if(Buffer[i]‘S’){ Buffer[j]=Buffer[i]; j++; } else Push(s,Buffer[i]); i++; } while(Buffer[j]){ Pop(s,Buffer[j]); j++; } cout<<Buffer<<endl; return 0; } 3.17 试写一个算法，识别一次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’则不是。 　　解： BOOL Symmetry(char a[]) { int i=0; Stack s; InitStack(s); ElemType x; while(a[i]!=’&’ && a[i]){ Push(s,a[i]); i++; } if(a[i]) return FALSE; i++; while(a[i]){ Pop(s,x); if(x!=a[i]){ DestroyStack(s); return FALSE; } i++; } return TRUE; } 3.18 试写一个判别表达式中开、闭括号是否配对出现的算法。 　　解： BOOL BracketCorrespondency(char a[]) { int i=0; Stack s; InitStack(s); ElemType x; while(a[i]){ switch(a[i]){ case ‘(’: Push(s,a[i]); break; case ‘[’: Push(s,a[i]); break; case ‘)’: GetTop(s,x); if(x’(’) Pop(s,x); else return FALSE; break; case ‘]’: GetTop(s,x); if(x==’[’) Pop(s,x); else return FALSE; break; default: break; } i++; } if(s.size!=0) return FALSE; return TRUE; }