《数据结构》习题集答案(C语言版)严蔚敏 下载本文

内容发布更新时间 : 2024/3/29 19:47:12星期一 下面是文章的全部内容请认真阅读。

p->exp=p2->exp; p++; k++; p2++; j++; }

L.last=k; return OK; }

在2.41至2.42题中,稀疏多项式采用的循环链表存储结构LinkedPoly定义为

typedef struct PolyNode { PolyTerm data;

struct PolyNode *next; } PolyNode, *PolyLink;

typedef PolyLink LinkedPoly;

2.41 试以循环链表作稀疏多项式的存储结构,编写求其导函数的方法,要求利用原多项式中的结点空间存放其导函数多项式,同时释放所有无用结点。

解:

Status PolyDifferential(LinkedPoly &L) {

LinkedPoly p,q,pt; q=L;

p=L->next; while(p!=L){

if(p->data.exp==0){ pt=p;

p=p->next; q->next=p; free(pt); } else{

p->data.coef=p->data.coef*p->data.exp; p->data.exp--; q=p;

p=p->next; } }

return OK; }

2.42 试编写算法,将一个用循环链表表示的稀疏多项式分解成两个多项式,使这两个多项式中各自仅含奇次项或偶次项,并要求利用原链表中的结点空间构成这两个链表。

解:

// 将单链表L划分成2个单循环链表

Status ListDivideInto2CL(LinkedPoly &L,LinkedPoly &L1)

精选

{ }

LinkedPoly p,p1,q,pt; q=L;

p=L->next; p1=L1;

while(p!=L){

if(p->data.exp%2==0){ pt=p;

p=p->next; q->next=p;

pt->next=p1->next; p1->next=pt; p1=p1->next; } else{ q=p;

p=p->next; } }

return OK;

第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得到的输出序列为p1p2?pn(它是输入序列的一个排列),则在输出序列中不可能出现这样的情形:存在着i

pj

解:这个问题和3.1题比较相似。因为输入序列是从小到大排列的,所以若

pj

显然通过序列123是无法得到312的,参见3.1题。所以不可能存在着i

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^FPUSH(OPND,A) # 2 # A -B*C/D+E^F# PUSH(OPTR,-) 3 #- A B*C/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操作的次数。 解:2n?1

3.9 试将下列递推过程改写为递归过程。 void ditui(int n)

精选

{

int i; i = n;

while(i>1) cout<

void ditui(int j) {

if(j>1){ cout<

return; }

3.10 试将下列递归过程改写为非递归过程。 void test(int &sum) { int x; cin>>x; if(x==0) sum=0; else { test(sum); sum+=x; } cout<

解:

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<

DestoryStack(s);

精选