数据结构习题集答案解析清华大学版 下载本文

得线性表。

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]=p) *top[0]--=x; else cerr<<\p=new ElemType[m]; if(!p) exit(OVERFLOW); top[0]=p+m/2; top[1]=top[0]; stacksize=m;

}else{