文档库

最新最全的文档下载
当前位置:文档库 > 数据结构耿国华课后答案

数据结构耿国华课后答案

数据结构耿国华课后答案

本文由edu_tech贡献

第一章绪论

一、问答题

1. 什么是数据结构?

2. 叙述四类基本数据结构的名称与含义。

3. 叙述算法的定义与特性。

4. 叙述算法的时间复杂度。

5. 叙述数据类型的概念。

6. 叙述线性结构与非线性结构的差别。

7. 叙述面向对象程序设计语言的特点。

8. 在面向对象程序设计中,类的作用是什么?

9. 叙述参数传递的主要方式及特点。

10. 叙述抽象数据类型的概念。

二、判断题(在各题后填写“√”或“×”)

1. 线性结构只能用顺序结构来存放,非线性结构只能用非顺序结构来存放。()

2. 算法就是程序。()

3. 在高级语言(如C或PASCAL)中,指针类型是原子类型。()

三、计算下列程序段中X=X+1的语句频度

for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

for(k=1;k<=j;k++)

x=x+1;

【解答】

i=1时: 1 = (1+1)×1/2 = (1+12)/2

i=2时:1+2 = (1+2)×2/2 = (2+22)/2

i=3时:1+2+3 = (1+3)×3/2 = (3+32)/2

i=n时:1+2+3+……+n = (1+n)×n/2 = (n+n2)/2

x=x+1的语句频度为:

f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2

=[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2

=n(n+1)(n+2)/6

=n3/6+n2/2+n/3

区分语句频度和算法复杂度:

O(f(n)) = O(n3)

四、试编写算法,求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0),并确定算法中的每一语句的执行次数和整个算法的时间复杂度,要求时间复杂度尽可能小,规定算法中不能使用求幂函数。注意:本题中的输入ai(i=0,1,…,n),x 和n,输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一:

(1)通过参数表中的参数显式传递。

(2)通过全局变量隐式传递。

试讨论这两种方法的优缺点,并在本题算法中以你认为较好的一种方式实现输入和输出

【解答】

(1)通过参数表中的参数显式传递

优点:当没有调用函数时,不占用内存,调用结束后形参被释放,实参维持,函数通用性强,移置性强。

缺点:形参须与实参对应,且返回值数量有限。

(2)通过全局变量隐式传递

优点:减少实参与形参的个数,从而减少内存空间以及传递数据时的时间消耗缺点:函数通用性降低,移植性差

算法如下:通过全局变量隐式传递参数

PolyValue()

{ int i,n;

float x,a[],p;

printf(“\nn=”);

scanf(“%f”,&n);

printf(“\nx=”);

scanf(“%f”,&x);

for(i=0;i

scanf(“%f ”,&a[i]); /*执行次数:n次*/

p=a[0];

for(i=1;i<=n;i++)

{ p=p+a[i]*x; /*执行次数:n次*/

x=x*x;}

printf(“%f”,p);

}

算法的时间复杂度:T(n)=O(n)

通过参数表中的参数显式传递

float PolyValue(float a[ ], float x, int n)

{

float p,s;

int i;

p=x;

s=a[0];

for(i=1;i<=n;i++)

{s=s+a[i]*p; /*执行次数:n次*/

p=p*x;}

return(p);

}

算法的时间复杂度:T(n)=O(n)

第二章线性表

2.1描述以下三个概念的区别:头指针,头结点,首元素结点。

2.2填空:

(1)在顺序表中插入或删除一个元素,需要平均移动__一半__元素,具体移动的元素个数与__插入或删除的位置__有关。

(2)在顺序表中,逻辑上相邻的元素,其物理位置______相邻。在单链表中,逻辑上相邻的元素,其物理位置______相邻。

(3)在带头结点的非空单链表中,头结点的存储位置由______指示,首元素结点的存储位置由______指示,除首元素结点外,其它任一元素结点的存储位置由__其直接前趋的next域__指示。

2.3 已知L是无表头结点的单链表,且P结点既不是首元素结点,也不是尾元素结点。按要求从下列语句中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是:_(4)、(1)_。

b. 在P结点前插入S结点的语句序列是:(7)、(11)、(8)、(4)、(1)。

c. 在表首插入S结点的语句序列是:(5)、(12)。

d. 在表尾插入S结点的语句序列是:(11)、(9)、(1)、(6)。

供选择的语句有:

(1)P->next=S;

(2)P->next= P->next->next;

(3)P->next= S->next;

(4)S->next= P->next;

(5)S->next= L;

(6)S->next= NULL;

(7)Q= P;

(8)while(P->next!=Q) P=P->next;

(9)while(P->next!=NULL) P=P->next;

(10)P= Q;

(11)P= L;

(12)L= S;

(13)L= P;

2.4 已知线性表L递增有序。试写一算法,将X插入到L的适当位置上,以保持线性表L的有序性。

Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中

{

if(va.length+1>va.listsize) return ERROR;

va.length++;

for(i=va.length-1;va.elem[i]>x&&i>=0;i--)

va.elem[i+1]=va.elem[i];

va.elem[i+1]=x;

return OK;

}//Insert_SqList

2.5 写一算法,从顺序表中删除自第i个元素开始的k个元素。

[提示]:注意检查i和k的合法性。

(集体搬迁,“新房”、“旧房”)

< 方法1 > 以待移动元素下标m(“旧房号”)为中心,

计算应移入位置(“新房号”):

for ( m= i-1+k; m<= L->last; m++)

L->elem[ m-k ] = L->elem[ m ];

< 方法2 > 同时以待移动元素下标m和应移入位置j为中心:

< 方法2 > 以应移入位置j为中心,计算待移动元素下标:

2.6已知线性表中的元素(整数)以值递增有序排列,并以单链表作存储结构。试写一高效算法,删除表中所有大于mink且小于maxk的元素(若表中存在这样的元素),分析你的算法的时间复杂度(注意:mink和maxk是给定的两个参变量,它们的值为任意的整数)。

Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链

表L中值大于mink且小于maxk的所有元素

{

p=L;

while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素

if(p->next) //如果还有比mink更大的元素

{

q=p->next;

while(q->datanext; //q是第一个不小于maxk的元素

p->next=q;

}

}//Delete_Between

2.7试分别以不同的存储结构实现线性表的就地逆置算法,即在原表的存储空间将线性表(a1, a2..., an)逆置为(an, an-1,..., a1)。

(1)以一维数组作存储结构,设线性表存于a(1:arrsize)的前elenum个分量中。(2)以单链表作存储结构。

[方法1]:在原头结点后重新头插一遍

[方法2]:可设三个同步移动的指针p, q, r,将q的后继r改为p

2.8假设两个按元素值递增有序排列的线性表A和B,均以单链表作为存储结构,请编写算法,将A表和B表归并成一个按元素值递减有序的排列的线性表C,并要求利用原表(即A表和B表的)结点空间存放表C.

[提示]:参P.28 例2-1

< 方法1 >

void merge(LinkList A; LinkList B; LinkList *C)

{ ……

pa=A->next; pb=B->next;

*C=A; (*C)->next=NULL;

while ( pa!=NULL && pb!=NULL )

{ if ( pa->data <= pb->data )

{ smaller=pa; pa=pa->next;

smaller->next = (*C)->next; /* 头插法*/

(*C)->next = smaller;

}

else

{ smaller=pb; pb=pb->next;

smaller->next = (*C)->next;

(*C)->next = smaller;

}

while ( pa!=NULL)

{ smaller=pa; pa=pa->next;

smaller->next = (*C)->next;

(*C)->next = smaller;

}

while ( pb!=NULL)

{ smaller=pb; pb=pb->next;

smaller->next = (*C)->next;

(*C)->next = smaller;

}

< 方法2 >

LinkList merge(LinkList A; LinkList B)

{ ……

LinkList C;

pa=A->next; pb=B->next;

C=A; C->next=NULL;

……

……

return C;

while(pa||pb)

{

if(pa->datadata||!pb)

{

pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表

}

else

{

pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表

}

pre=pc;

}

C=A;A->next=pc; //构造新表头

}//reverse_merge

分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部p c处,最后处理A或B的剩余元素.

2.9假设有一个循环链表的长度大于1,且表中既无头结点也无头指针。已知s 为指向链表某个结点的指针,试编写算法在链表中删除指针s所指结点的前趋结点。

[提示]:设指针p指向s结点的前趋的前趋,则p与s有何关系?

Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s的直接前驱

{

p=s;

while(p->next->next!=s) p=p->next; //找到s的前驱的前驱p

p->next=s;

return OK;

}//Delete_Pre

2.10 已知有单链表表示的线性表中含有三类字符的数据元素(如字母字符、数字字符和其它字符),试编写算法来构造三个以循环链表表示的线性表,使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。

Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型.

{

s=L->next;

A=(CiList*)malloc(sizeof(CiLNode));p=A;

B=(CiList*)malloc(sizeof(CiLNode));q=B;

C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点

while(s)

{

if(isalphabet(s->data))

{

p->next=s;p=s;

}

else if(isdigit(s->data))

{

q->next=s;q=s;

}

else

{

r->next=s;r=s;

}

}//while

p->next=A;q->next=B;r->next=C; //完成循环链表

}//LinkList_Divide

2.11 设线性表A=(a1, a2,…,am),B=(b1, b2,…,bn),试写一个按下列规则合并A、B为线性表C的算法,使得:

C= (a1, b1,…,am, bm, bm+1, …,bn) 当m≤n时;

或者C= (a1, b1,…,an, bn, an+1, …,am) 当m>n时。

线性表A、B、C均以单链表作为存储结构,且C表利用A表和B表中的结点空间构成。注意:单链表的长度值m和n均未显式存储。

[提示]:void merge(LinkList A; LinkList B; LinkList *C)

或:LinkList merge(LinkList A; LinkList B)

void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A 和B的元素间隔排列,且使用原存储空间

{

p=A->next;q=B->next;C=A;

while(p&&q)

{

s=p->next;p->next=q; //将B的元素插入

if(s)

{

t=q->next;q->next=s; //如A非空,将A的元素插入

}

p=s;q=t;

}//while

}//merge1

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

[提示]:注明用头指针还是尾指针。

void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B

{

p=L->next;

A=(PolyNode*)malloc(sizeof(PolyNode));

B=(PolyNode*)malloc(sizeof(PolyNode));

pa=A;pb=B;

while(p!=L)

{

if(p->data.exp!=2*(p->data.exp/2))

{

pa->next=p;pa=p;

}

else

{

pb->next=p;pb=p;

}

p=p->next;

}//while

pa->next=A;pb->next=B;

}//Divide_LinkedPoly

2.13 建立一个带头结点的线性链表,用以存放输入的二进制数,链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算。[提示]:可将低位放在前面。

2.14 设多项式P(x)采用课本中所述链接方法存储。写一算法,对给定的x值,求P(x)的值。

[提示]:float PolyValue(Polylist p; float x) {……}

第三章栈和队列

1.按图3.1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度,回答:

⑴如进站的车厢序列为123,则可能得到的出站车厢序列是什么?

⑵如进站的车厢序列为123456,能否得到435612和135426的出站序列,并说明原因。(即写出以“S”表示进栈、以“X”表示出栈的栈操作序列)。

【解答】

(1)可能得到的出站车厢序列是:123、132、213、231、321。

(2)不能得到435612的出站序列。

因为有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6),此时按照“后进先出”的原则,出栈的顺序必须为X(2)X(1)。

能得到135426的出站序列。

因为有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。

2.设队列中有A、B、C、D、E这5个元素,其中队首元素为A。如果对这个队列重复执行下列4步操作:

(1)输出队首元素;

(2)把队首元素值插入到队尾;

(3)删除队首元素;

(4)再次删除队首元素。

直到队列成为空队列为止,则是否可能得到输出序列:

(1)A、C、E、C、C (2)A、C、E

(3)A、C、E、C、C、C (4)A、C、E、C

[提示]:

A、B、C、D、E (输出队首元素A)

A、B、C、D、E、A (把队首元素A插入到队尾)

B、C、D、E、A (删除队首元素A)

C、D、E、A (再次删除队首元素B)

C、D、E、A (输出队首元素C)

C、D、E、A、C (把队首元素C插入到队尾)

D、E、A、C (删除队首元素C)

E、A、C (再次删除队首元素D)

3.给出栈的两种存储结构形式名称,在这两种栈的存储结构中如何判别栈空与栈满?

4.按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例,画出对下列算术表达式求值时操作数栈和运算符栈的变化过程:

A-B*C/D+E↑F

【解答】

5.试写一个算法,判断依次读入的一个以@为结束符的字母序列,是否为形如…序列1&序列2?模式的字符序列。其中序列1和序列2中都不含字符?&?,且序列2是序列1的逆序列。例如,…a+b&b+a?是属该模式的字符序列,而…1+3&3-1?则不是。

[提示]:

(1)边读边入栈,直到&

(2)边读边出栈边比较,直到……

int IsReverse()//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0 {

InitStack(s);

while((e=getchar())!='&')

push(s,e);

while((e=getchar())!='@')

{

if(StackEmpty(s)) return 0;

if(e!=c) return 0;

}

if(!StackEmpty(s)) return 0;

return 1;

}//IsReverse

6.假设表达式由单字母变量和双目四则运算算符构成。试写一个算法,将一个通常书写形式(中缀)且书写正确的表达式转换为逆波兰式(后缀)。

void NiBoLan(char *str,char *new)//把中缀表达式str转换成逆波兰式new

{

p=str;q=new; //为方便起见,设str的两端都加上了优先级最低的特殊符号

InitStack(s); //s为运算符栈

while(*p)

{

if(*p是字母)) *q++=*p; //直接输出

else

{

c=gettop(s);

if(*p优先级比c高) push(s,*p);

else

{

while(gettop(s)优先级不比*p低)

{

pop(s,c);*(q++)=c;

}//while

push(s,*p); //运算符在栈内遵循越往栈顶优先级越高的原则

}//else

}//else

p++;

}//while

}//NiBoLan //参见编译原理教材

7.假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针),试编写相应的队列初始化、入队列和出队列的算法。

void InitCiQueue(CiQueue &Q)//初始化循环链表表示的队列Q

{

Q=(CiLNode*)malloc(sizeof(CiLNode));

Q->next=Q;

}//InitCiQueue

void EnCiQueue(CiQueue &Q,int x)//把元素x插入循环链表表示的队列Q,Q指向队尾元素, Q->next指向头结点,Q->next->next指向队头元素

{

p=(CiLNode*)malloc(sizeof(CiLNode));

p->data=x;

p->next=Q->next; //直接把p加在Q的后面

Q=p; //修改尾指针

}

Status DeCiQueue(CiQueue &Q,int x)//从循环链表表示的队列Q头部删除元素x

{

if(Q==Q->next) return INFEASIBLE; //队列已空

p=Q->next->next;

x=p->data;

Q->next->next=p->next;

free(p);

return OK;

}//DeCiQueue

8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满,请编写与此结构相应的入队与出队算法。[提示]:

初始状态:front==0, rear==0, tag==0

队空条件:front==rear, tag==0

队满条件:front==rear, tag==1

其它状态:front !=rear, tag==0(或1、2)

入队操作:

…(入队)

if (front==rear) tag=1;(或直接tag=1)

出队操作:

…(出队)

tag=0;

[问题]:如何明确区分队空、队满、非空非满三种情况?

9.简述以下算法的功能(其中栈和队列的元素类型均为int):

(1)void proc_1(Stack S)

{ int i, n, A[255];

n=0;

while(!EmptyStack(S))

{n++; Pop(&S, &A[n]);}

for(i=1; i<=n; i++)

Push(&S, A[i]);

}

将栈S逆序。

(2)void proc_2(Stack S, int e)

{ Stack T; int d;

InitStack(&T);

while(!EmptyStack(S))

{ Pop(&S, &d);

if (d!=e) Push( &T, d);

}

while(!EmptyStack(T))

{ Pop(&T, &d);

Push( &S, d);

}

}

删除栈S中所有等于e的元素。

(3)void proc_3(Queue *Q)

{ Stack S; int d;

InitStack(&S);

while(!EmptyQueue(*Q))

{

DeleteQueue(Q, &d);

Push( &S, d);

}

while(!EmptyStack(S))

{ Pop(&S, &d);

EnterQueue(Q,d)

}

}

将队列Q逆序。

第四章串

1. 设s=?I AM A STUDENT?, t=?GOOD?, q=?WORKER?。给出下列操作的结果:StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1);

StrIndex(s,?A?,4); StrReplace(s,?STUDENT?,q);

StrCat(StrCat(sub1,t), StrCat(sub2,q));

[参考答案]

StrLength(s)=14;

SubString(sub1,s,1,7) sub1=?I AM A?;

SubString(sub2,s,7,1) sub2=? ?;

StrIndex(s,4,?A?)=6;

StrRepl ace(s,?STUDENT?,q); s=?I AM A WORKER?;

StrCat(StrCat(sub1,t),StrCat(sub2,q)) sub1=?I AM A GOOD WORKER?。

2. 编写算法,实现串的基本操作StrReplace(S,T,V)。

StrCat(S,T);SubString(Sub,S,pos,len)。

int String_Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数

{

for(n=0,i=1;i<=S[0]-T[0]+1;i++)

{

for(j=i,k=1;T[k]&&S[j]==T[k];j++,k++);

if(k>T[0]) //找到了与T匹配的子串:分三种情况处理

{

if(T[0]==V[0])

for(l=1;l<=T[0];l++) //新子串长度与原子串相同时:直接替换

S[i+l-1]=V[l];

else if(T[0]

{

for(l=S[0];l>=i+T[0];l--)

S[l+V[0]-T[0]]=S[l];

for(l=1;l<=V[0];l++)

S[i+l-1]=V[l];

}

else //新子串长度小于原子串时:先将后部左移

{

for(l=i+V[0];l<=S[0]+V[0]-T[0];l++)

S[l]=S[l-V[0]+T[0]];

for(l=1;l<=V[0];l++)

S[i+l-1]=V[l];

}

S[0]=S[0]-T[0]+V[0];

i+=V[0];n++;

}//if

}//for

return n;

}//String_Replace

3. 假设以块链结构表示串,块的大小为1,且附设头结点。

试编写算法,实现串的下列基本操作:

StrAsign(S,chars);StrCopy(S,T);StrCompare(S,T);StrLength(S);StrCat(S,T);SubStr ing(Sub,S,pos,len)。

[说明]:用单链表实现。

StrAsign(S,chars);StrCopy(S,T);StrCompare(S,T);StrLength(S);

typedef struct{

char ch;

LStrNode *next;

} LStrNode,*LString; //链串结构

void StringAssign(LString &s,LString t)//把串t赋值给串s

{

s=malloc(sizeof(LStrNode));

for(q=s,p=t->next;p;p=p->next)

{

r=(LStrNode*)malloc(sizeof(LStrNode));

r->ch=p->ch;

q->next=r;q=r;

}

q->next=NULL;

}//StringAssign

void StringCopy(LString &s,LString t)//把串t复制为串s.与前一个程序的区别在于,串s业已存在.

{

for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next)

{

p->ch=q->ch;pre=p;

}

while(q)

{

p=(LStrNode*)malloc(sizeof(LStrNode));

p->ch=q->ch;

pre->next=p;pre=p;

}

p->next=NULL;

}//StringCopy

char StringCompare(LString s,LString t)//串的比较,s>t时返回正数,s=t时返回0,s

{

for(p=s->next,q=t->next;p&&q&&p->ch==q->ch;p=p->next,q=q->next);

if(!p&&!q) return 0;

else if(!p) return -(q->ch);

else if(!q) return p->ch;

else return p->ch-q->ch;

}//StringCompare

int StringLen(LString s)//求串s的长度(元素个数)

{

for(i=0,p=s->next;p;p=p->next,i++);

return i;

}//StringLen

LString * Concat(LString s,LString t)//连接串s和串t形成新串,并返回指针

{

p=malloc(sizeof(LStrNode));

for(q=p,r=s->next;r;r=r->next)

{

q->next=(LStrNode*)malloc(sizeof(LStrNode));

q=q->next;

q->ch=r->ch;

}//for //复制串s

for(r=t->next;r;r=r->next)

{

q->next=(LStrNode*)malloc(sizeof(LStrNode));

q=q->next;

q->ch=r->ch;

}//for //复制串t

q->next=NULL;

return p;

}//Concat

LString * Sub_String(LString s,int start,int len)//返回一个串,其值等于串s从start位置起长为len的子串

{

p=malloc(sizeof(LStrNode));q=p;

for(r=s;start;start--,r=r->next); //找到start所对应的结点指针r

for(i=1;i<=len;i++,r=r->next)

{

q->next=(LStrNode*)malloc(sizeof(LStrNode));

q=q->next;

q->ch=r->ch;

} //复制串t

q->next=NULL;

return p;

}//Sub_String

4.叙述以下每对术语的区别:空串和空格串;串变量和串常量;主串和子串;串变量的名字和串变量的值。

char StrCompare(Stringtype s,Stringtype t)//串的比较,s>t时返回正数,s=t时返回0,s

{

for(i=1;i<=s[0]&&i<=t[0]&&s[i]==t[i];i++);

if(i>s[0]&&i>t[0]) return 0;

else if(i>s[0]) return -t[i];

else if(i>t[0]) return s[i];

else return s[i]-t[i];

}//StrCompare

5.已知:S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作,将S转换为T.

int HString_Replace(HString &S,HString T,HString V)//堆结构串上的置换操作,返回置换次数

{

for(n=0,i=0;i<=S.length-T.length;i++)

{

for(j=i,k=0;k

if(k==T.length) //找到了与T匹配的子串:分三种情况处理

{

if(T.length==V.length)

for(l=1;l<=T.length;l++) //新子串长度与原子串相同时:直接替换

S.ch[i+l-1]=V.ch[l-1];

else if(T.length

{

for(l=S.length-1;l>=i+T.length;l--)

S.ch[l+V.length-T.length]=S.ch[l];

for(l=0;l

S[i+l]=V[l];

}

else //新子串长度小于原子串时:先将后部左移

{

for(l=i+V.length;l

S.ch[l]=S.ch[l-V.length+T.length];

for(l=0;l

S[i+l]=V[l];

}

S.length+=V.length-T.length;

i+=V.length;n++;

}//if

}//for

return n;

}//HString_Replace

6.S和T是用结点大小为1的单链表存储的两个串,设计一个算法将串S中首次与T匹配的子串逆置。

7.S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T,及从第k个字符删除len个字符。

以下算法用定长顺序串:

8.写下列算法:

(1)将顺序串r中所有值为ch1的字符换成ch2的字符。

(2)将顺序串r中所有字符按照相反的次序仍存放在r中。

(3)从顺序串r中删除其值等于ch的所有字符。

(4)从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置。

(5)从顺序串r中删除所有与串r1相同的子串。

9.写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。

[提示]:(1)用静态顺序串(2)先移位,后复制

10.写算法,实现顺序串的基本操作StrCompare(s,t)。

11.写算法,实现顺序串的基本操作StrReplace(&s,t,v)。

[提示]:

(1)被替换子串定位(相当于第9题中i)

(2)被替换子串后面的字符左移或右移(为替换子串准备房间)

(3)替换子串入住(复制)

(4)重复上述,直到……

实习题

1.一、已知串S和T,试以以下两种方式编写算法,求得所有包含在S中而不包含在T中的字符构成的新串R,以及新串R中每个字符在串S中第一次出现的位置。

(1)利用CONCA T、LEN、SUB和EQUAL四种基本运算来实现。

(2)以顺序串作为存储结构来实现。

void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r

{

StrAssign(r,'');

for(i=1;i<=Strlen(s);i++)

{

StrAssign(c,SubString(s,i,1));

for(j=1;j

if(i==j)

{

for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1));k++); //判断当前字符是否包含在t中if(k>Strlen(t)) StrAssign(r,Concat(r,c));

}

}//for

}//String_Subtract

第五章数组和广义表

1.假设有6行8列的二维数组A,每个元素占用6个字节,存储器按字节编址。已知A的基地址为1000,计算:

(1)数组A共占用多少字节;(288)

(2)数组A的最后一个元素的地址;(1282)

(3)按行存储时,元素A36的地址;(1126)

(4)按列存储时,元素A36的地址;(1192)

[注意]:本章自定义数组的下标从1开始。

2.设有三对角矩阵(aij)n×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中,使得B[k]= aij ,求:

(1)用i,j表示k的下标变换公式;

(2)用k表示i,j的下标变换公式。

i = k/3 + 1, j = k%3 + i - 1 = k%3 + k/3

或:

i = k/3 + 1, j = k - 2×( k/3 )

3. 假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法,另设三元组表C存放结果矩阵。

void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C)//三元组表示的稀疏矩阵加法{

C.mu=A.mu;C.nu=A.nu;C.tu=0;

pa=1;pb=1;pc=1;

for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法

{

while(A.data[pa].i

while(B.data[pb].i

while(A.data[pa].i==x&&B.data[pb].i==x)//

行列值都相等的元素

{

if(A.data[pa].j==B.data[pb].j)

{

ce=A.data[pa].e+B.data[pb].e;

if(ce) //和不为0

{

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j;

C.data[pc].e=ce;

pa++;pb++;pc++;

}

}//if

else if(A.data[pa].j>B.data[pb].j)

{

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j;

C.data[pc].e=B.data[pb].e;

pb++;pc++;

}

else

{

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j;

C.data[pc].e=A.data[pa].e

pa++;pc++;

}

}//while

while(A.data[pa]==x) //插入A中剩余的元素(第x行)

{

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j;

C.data[pc].e=A.data[pa].e

pa++;pc++;

}

while(B.data[pb]==x) //插入B中剩余的元素(第x行)

{

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j;

C.data[pc].e=B.data[pb].e;

pb++;pc++;

}

}//for

C.tu=pc;

}//TSMatrix_Add

4.在稀疏矩阵的快速转置算法5.2中,将计算position[col]的方法稍加改动,使算法只占用一个辅助向量空间。

5.写一个在十字链表中删除非零元素aij的算法。

[提示]:“删除”两次,释放一次。

6.画出下面广义表的两种存储结构图示:

((((a), b)), ((( ), d), (e, f)))

7.求下列广义表运算的结果:

(1)HEAD[((a,b),(c,d))];

(2)TAIL[((a,b),(c,d))];

(3)TAIL[HEAD[((a,b),(c,d))]];

(4)HEAD[TAIL[HEAD[((a,b),(c,d))]]]; b

(5)TAIL[HEAD[TAIL[((a,b),(c,d))]]]; (d)

实习题

若矩阵Am×n中的某个元素aij是第i行中的最小值,同时又是第j列中的最大值,则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵,试编写算法求出矩阵中的所有马鞍点。

void Get_Saddle(int A[m][n])//求矩阵A中的马鞍点

{

for(i=0;i

{

for(min=A[i][0],j=0;j

if(A[i][j]

for(j=0;j

if(A[i][j]==min) //判断这个(些)最小值是否鞍点

{

for(flag=1,k=0;k

if(min

if(flag)

printf("Found a saddle element!\nA[%d][%d]=%d",i,j,A[i][j]);

}

}//for

}//Get_Saddle

第六章数和二叉树

1.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

2.对题1所得各种形态的二叉树,分别写出前序、中序和后序遍历的序列。

3.已知一棵度为k的树中有n1个度为1的结点,n2个度为2的结点,……,nk个度为k 的结点,则该树中有多少个叶子结点?

[提示]:参考P.116 性质3

∵n=n0 + n1 + …… + nk

B=n1 + 2n2 + 3n3 + …… + knk

n= B + 1

∴n0 + n1 + …… + nk = n1 + 2n2 + 3n3 + …… + knk + 1

∴n0 = n2 + 2n3 + …… + (k-1)nk + 1

4.假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请画出该二叉树。

[提示]:参考P.148

6.已知二叉树有50个叶子结点,则该二叉树的总结点数至少应有多少个?

[提示]:一个叶子结点,总结点数至多有多少个?可压缩一度结点。

7.给出满足下列条件的所有二叉树:

a)前序和中序相同

b)中序和后序相同

c)前序和后序相同

[提示]:去异存同。

a)D L R 与L D R 的相同点:D R,如果无L,则完全相同, 如果无LR,…。

b)L D R 与L R D 的相同点:L D,如果无R,则完全相同。

c)D L R 与L R D 的相同点:D,如果无L R,则完全相同。

(如果去D,则为空树)

7.n个结点的K叉树,若用具有k个child域的等长链结点存储树的一个结点,则空的Child 域有多少个?

[提示]:参考P.119

8.画出与下列已知序列对应的树T:

树的先根次序访问序列为GFKDAIEBCHJ;

树的后根次序访问序列为DIAEKFCJHBG。

[提示]:

(1)先画出对应的二叉树

(2)树的后根序列与对应二叉树的中序序列相同

9.假设用于通讯的电文仅由8个字母组成,字母在电文中出现的频率分别为:

0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10

(1)请为这8个字母设计哈夫曼编码,

(2)求平均编码长度。

10.已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点的指针,是否可不用递归且不用栈来完成?请简述原因.

[提示]:无右子的“左下端”

11. 画出和下列树对应的二叉树:

12.已知二叉树按照二叉链表方式存储,编写算法,计算二叉树中叶子结点的数目。13.编写递归算法:对于二叉树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间。

[提示]:

[方法1]:(1)按先序查找;(2)超前查看子结点(3)按后序释放;

void DelSubTree(BiTree *bt, DataType x)

{

if ( *bt != NULL && (*bt) ->data==x )

{ FreeTree(*bt);

*bt =NULL;

}

else DelTree( *bt, x)

void DelTree(BiTree bt, DataType x)

{ if ( bt )

{ if (bt->LChild && bt->LChild->data==x)

{ FreeTree(bt->LChild);

bt->LChild=NULL;