《算法与数据结构》习题集及答案

《算法与数据结构》习题集及答案

习题1

1-1.数据的逻辑结构为：MyDS={D,R},其中:

D={a,b,c,,d,e,f}

R={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<b,c>,<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,

<d,e>,<d,f>,<e,f>}

请画出它的结构图。它是线性结构吗？哪些结点是开始结点？哪些结点是终端结点？

答案：

它不是线性结构，a结点是开始结点，f结点是终端结点。

1-2.试说明基本数据类型、数据结构和抽象数据类型的联系与差异。

答案：

数据结构所研究内容的着重点主要体现在三个方面：

第一是数据间的逻辑关系，即数据元素之间的关系。

第二是数据的存储关系，即数据在计算机中的存储结构。

第三是算法，即定义在数据对象上的操作的实现策略，是对操作的描述。

因此，简单说来，数据结构所研究的问题是如何将现实世界中的事物合理描述为计算机

世界中所研究的对象，并根据研究对象的特点，分析对象之间的关系、存储结构和操作的学

科。

基本数据类型（DataType）：数据是按照数据结构分类的，具有相同数据结构的数据

属同一类。同一类数据的全体称为一个数据类型。在程序设计高级语言中，数据类型用来说

明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。

高级语言中都有基本数据类型。例如在C、C++和Java语言中，有基本类型int（整型）、float

（浮点型）和char（字符型），有构造类型数组、结构、联合、指针、枚举型和自定义等。

抽象数据类型即不论其内部结构如何变化，只要数学特性不变，都不影响抽象数据类型

外部的使用。是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取

决于抽象数据类型的逻辑特性，与它在计算机内部如何表示和实现无关。

1-3.为什么要引入抽象数据类型概念，它有什么特点？

答案：引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类

型和运算在程序中的引用隔开，使它们相互独立。

抽象数据类型的定义仅取决于抽象数据类型的逻辑特性，与它在计算机内部如何表示和实现

无关，即不论其内部结构如何变化，只要数学特性不变，都不影响抽象数据类型外部的使用。

1-4.请用抽象数据类型描述法描述一个随身听，再用C、C++或Java描述。

答案：

随身听可用来放歌，也可以快进和快退，还可以停止，所以随身听的抽象数据类型至少

应该包括放歌键、快进键、快退键和停止键；随身听的ADT描述为：

ADTRadio{

Data开始键begin

Data快进键kuaijin

Data快退键kuaitui

Data停止键stop

Operations

Constructor

Initialvalues:开始值，快进值，快退值，停止值

Process:将开始值赋给begin；将快进值赋给kuaijin；将快退值赋给kuaitui；

将停止值赋给stop；

Process:计算开始键的值

Output:返回开始键的值

KUAIJIN

Process:计算快进键的值

Output:返回快进键的值

KUAITUI

Process:计算快退键的值

Output:返回快退键的值

STOP

Process:计算停止键的值

Output:返回停止键的值

}//Radio

classRadio{

intbegin,kuaijin,kuaitui,stop;

Radio(intbeginO,intkuaijinO,intkuaituiO,intstopO)

{begin=beginO;kuaijin=kuaijinO;kuaitui=kuaituiO;stop=stopO;}

IntBEGIN(){returnbegin;}

IntKUAIJIN(){returnkuaijin;}

IntKUAITUI(){returnkuaitui;}

IntSTOP(){returnstop;}

};//Radio

1-5.试说明数据的逻辑结构、存储结构和算法三者之间的关系。

答案：1个数学模型可用多个不同的数据逻辑结构表示；数据逻辑结构是对数学模型的实现；

1个数据逻辑结构可有多种不同的存储结构；存储结构是对逻辑结构实现；算法是基于逻辑

结构对操作的实现；函数是基于存储结构对算法的实现，是程序；

逻辑结构直接影响到算法的效率，有时存储结构会影响到算法的基本操作及算法的实现,

从而影响到算法的效率。设计与选择合理的相互吻合的逻辑结构、存储结构与算法是十分重

要的问题，也是我们学习本课程的目的之一。因此，设计选择好的数据逻辑结构、数据存储

结构和算法，既可以支持好的解决问题的方案，又可开发出好的程序。

1-6.请给出下列函数的大0和Q表示：

1-7.

100n+n2-2nVn,nlogn+2n=-n,Vn+log2n,Vnlogn2-5n

答案：

(1)0(n2)(2)0(nL5)(3)0(n,/2)(4)0(n,/2logn2)

1-8.设计一个算法判断给定整数数组是否排好序。分析你的算法的时间复杂度。

intpanduan(inta[],intn){

if(a[0]<a[l]){

for(inti=l,i<n-l,i++){

if(a[i]<a[i+l])continue;

else{cout。”此给定整数数组没有排好序”<<endl;

break;

)

)

cout«M此给定整数数组已经排好序”<〈endl;

)

else{

for(inti=l,i<n-l,i++)

{if(a[i]>a[i+l])continue;

else{cout«>,此给定整数数组没有排好序”。endl;

break;

)

}

cout<<”此给定整数数组已经排好序”"endl;

答案:此算法的时间复杂度为：T(n)=0(n)

1-9.设计一个算法求整数集合中的最大数和最小数。分析你的算法的时间复杂度。

voidmaxmin(inta[n]){

intmax=a[0];

intmin=a[0];

for(inti=l;i<n;i++){

if(a[i]>max)

max=a[i];

if(a[i]<min)

min=a[i];

)

cout<X"此整数集合中的最大数为："<Xmax〈〈endl;

cout<<“此整数集合中的最小数为："<<min〈<endl;

}

答案:此算法的时间复杂度为:T(n)=0(2(n-l))=0(n)

1-10.设计一个排序算法，并分析你的算法的时间复杂度。

voidsort(inta[],intn){

intmin,t;

for(inti=0;i<n-l;i++){〃对数组进行交换排序

t=i;

for(intj=i+l;j<n;j++)〃寻找最小元素

if(x[j]<x[t])t=j;

if(t!=i)

{min=x[i];x[i]=x[t];x[t]=min;}

〃交换数组元素，将最小元素放入x[i]中

)

答案：此算法的时间复杂度为：T(n)=0(n?)

习题2

2-1.描述以下三个概念的区别：头指针、头结点、首结点(第一个元素结点)。在单链表中

设置头结点的作用是什么？

答案：头指针指向链表中第一个结点的存储位置，在没有头结点的链表中，头指针指向链表

中的首结点，

有头结点的链表中，头指针指向链表中的头结点。

为了便于实现插入和删除操作，可以在单链表的首结点之前增设一个结点，称之为头结

点。

2-3.用单链表表示两个集合A和B,实现两个集合的并操作A=AUB。

答案：voidList::Union(ListListLA,ListListLB,ListListLC){〃求并集

inty=LA.First();〃取LA中的第一个元素

while(y!=-l){

LC.Insert(y);〃从LA中取元素放到LC

y=LA.Next();}

intx=LB.First();

while(x!=-l){

intk=LA.Find(x);

if(k==-1)

LC.Insert(x);

x=LB.Next();

2-4.已知二维数组A…采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的

存储地址为Loe®),请写出求Loc(a”)的计算公式。如果采用列优先顺序存放呢？

答案:行优先顺序存放时Loc(aQ=Loc(an)+(i-l)*m*K+(j-l)*K

列优先顺序存放时LocLoc(ah)+(j-1)*m*K+(i-1)*K

2-5.在链表类的实现中增加一个成员函数实现对表中元素置逆的操作(设原链表为a。，ab

an-2)a„,;则置逆后的序列为a””a.,.2,a„a。)。对于有n个元素的线性表，你的算法的

运行时间应为0(n)。

答案：算法描述：设head是头指针，把链表中的每一个结点以头插法插入到链表的第一个，

即可把把原链表的方向改过来，即置逆过来。且时间复杂度为0(n)。

Node*LinlList::invert(){

Node*p=head->next,*q;

head->next=NULL;

while(p){

q=p->next;

p->1ink=head->link;

head->link=p;

P=q；

}

returnhead;

2-6.请编写26个字母按特定字母值插入或删除的完整程序(表中的字母按从小到大的顺序排

歹U),可自行选用顺序存储或链表结构。

答案：voiddelete(chara){

charc[26];

for(inti=0;i<26;i++)

if(cLi]==a)

c[i]==，'；

}

2-7.用2.1.3中给出多项式定义及两个多项式相加的算法思想，实现多项式类中AddPloyn

算法(先实现Create来创建多项式)。

答案：voidCreate(intn){

for(i=n;i>0;i--){

p=newNode();

if(p==NULL)exit;〃创建结点不成功，返回

cin>>p->coef;

cin»p->expn;

p->next=head->next;

head->next=p;

)

size=n;

}//Create

voidPolynList::AddPolyn(PolynListB){〃求两多项式A(x)与B(x)的和

//qa和%分别指向A和B的首结点

PNode*qa=head;PNode*qb=B.head;

while(qa!=NULL&&qb!=NULL)

switch(compare(qa.expn,qb,.expn)){〃比较对应项的指数

case,二':if(qa.coef+qb.coef!=0)qa.coef=qa.coef+qb.coef;

delete(qb.len());

elsedelete(qa.len());delete(qb.len());

qa=qa->next;qb=qb->next;break;

case，>，:floatcoef=GetElem(qb.len());

intexpn=GetElem(qb.len());

Insert(coef,expn,qa.len());

qb=qb->next;break;

case':qa=qa->next

)

while(qb!=NULL)

{qa->next=qb;

qb=qb->next;}

2-8.给出一个5X8的矩阵，其中正好有9个非0元素，并且在每一行和每一列中至少有一个

非0元素。对于这个稀疏矩阵，画出其相应的十字链表。

答案：

2-10.设计一个算法，将数组A(0..nT)中的元素循环右移k位，假设原数组序列为a。，ab

an-2,an-1;移动后的序列为4.k,…，E,a%…,an-k-l0要求只用一个元素大小

的附加存储，元素移动或交换次数为0(n)。

答案：voidyouyi(inta[],intn,intk){

inti=0,m=0,p=a[n-k];

while(m<n)

{q=a[i];

a[i]=p;

i=(i+i*k)%n;

P=q；

m++;

}

)

2-11.已知主串s='ADBADABBAABADABBADADA',模式串pat='ADABBADADA'0写出模式串的

nextval函数值，并由此画出KMP算法匹配的全过程。

答案：模式串的nextval函数值为12,(具体过程略)

习题3

3-1.答案：

(1)输出结果为：9

3

22

8

(2)换一道题

输出结果为：Stack

3-2.答案：

(1)开出车站的顺序有14种可能。所有可能的出栈序列为：

1,2,3,4

1,2,4,3

1,3,2,4

1,3,4,2

1,4,3,2

2,1,3,4

2,1,4,3

2,3,4,1

2,4,3,1

2,3,1,4

3,2,1,4

3,2,4,1

3,4,2,1

4,3,2,1

(2)

算法如下：

constintMaxStackSize=4;〃栈中能容纳最大元素个数

classStack{

intStackList[MaxStackSize];

intpath[];〃存放输出序列

inttop;

intcurp;〃标识path口中当前元素的位置

public:

Stack(){〃构造函数，初始化一个空栈

StackList=newDataType[MaxStackSize];

top=-l;

}//Stack

boolIsEmpty(){〃判断栈是否为空

if(top==-l)

returntrue;

else

returnfalse;

}//IsEmpty

boolIsFull(){〃判断栈是否已满

if(top==MaxStackSize-1)

returntrue;

else

returnfalse;

}//IsFull

voidPush(intx){〃入栈

StackList[++top]=x;

}//Push

intPop(){〃出栈

returnStackList[top-];

}//Pop

process(inttop,intpath口,intcurp)〃处理整数序列中top位置的元素

{intm,i,x;

if(top<MaxStackSize)〃编号top的元素x进栈时递归

{Push(x);//x进栈

process(top+1,path,curp);

Pop();〃出栈以恢复环境

)

if(!IsEmpty())〃编号top的元素x出栈时递归

{m=Pop();

path[curp]=m;〃将m输出到path中

curp++;

process(top,path,curp);

Push(m);〃进栈以恢复环境

if(top>=MaxStackSize&&IsEmpty())〃输出一种可能的方案

{for(i=0;i<curp;i++)

cout<<path[curp];

)

cout<<”«endl;

)

)

3-3.答案：

(1)GetHead[(a,b,c)]=(a)

(2)GetTai1[(a,b,c,d)]=(b,c,d)

(3)GetHead[((a,b),(c,d))]=(a,b)

(4)GetHead[GetTai1[((a,b),(c,d))]]=(c,d)

(5)GetTai1[GetHead[GetTai1[((a,b),(c.d))]]]=(d)

3-4.答案：

(1)头尾表示法:

之，一旦元素出队列时，front==rear时，需置tag为“0”，以便使下一次进行入队列或出

队列操作时，可由标志位tag的值来区别队列当时的状态是“满”，还是“空”。

算法如下：

循环队列中入队算法如下：

voidEnter(DataTypeitem)〃带tag域的循环队列入队算法

{if(front==rear&&tag==l)〃tag域的值为0表示空，1表示满

return0;

rear=(rear+1)%MaxQSize;

SeqQueue[rear]=item;

if(front==rear)

tag=l；〃队列满

)

循环队列中出队算法如下：

DataTypeLeave()〃带tag域的循环队列出队算法

{if(front==rear&&tag==0)〃tag域的值为0表示空，1表示满

return0;

front=(front+l)%MaxQSize;

if(front==rear)

tag=0；〃队空

returnSeqQueue[front];

)

这种算法因为不要预留一个空的存储单元作为判断队满的条件，因此在空间上能充分利用，

但在插入和删除时每次都要检查标志tag,同时在操作完成时，还要检查头、尾指针是否重

合，若是，则给tag重新赋值，故时间开销多。故当队中每个元素占用的空间较多时，还是

舍标志的方法较为适合。

3-6.答案：

(1)S1为空的条件是：topl=-l；

S2为空的条件是topl=MaxDualStackSiz2)

(2)S1和S2为满的条件是：topl==top2T

(3)实现DualStack,其声明如下。

constintMaxDualStackSize

classDualStack{

private:

inttopi,top2;

DataTypestackStorge[MaxDualStackSize];

public:

DualStack();

voidpush(DataTypeelt,intn);〃往栈n中压入elt

if(topl==top2-l)〃栈满

cout«w栈满”

if(n==l)//elt入栈1

(

topl++;

stackStorge[topl]=elt;

)

if(n==2)〃elt入栈2

(

top2一;

stackStorge[top2]=elt;

)

)

DataTypePop(intn);〃从栈n中弹出元素

(

intx;

if(n==l)

{if(top==-l)

cout«w栈空！”《endl;

else

{x=stackStorge[topi];

topi一;}

¥

elseif(n==2)

{if(top2==MaxDualStackSize)

cout«>>栈空！"<<endl;

else

{x=stackStorge[top2];

top2++;

}

)

elsecout«w不存在该栈！"<<endl;

returnx;

}

DataTypeGetTop(intn);〃取栈n的顶元素

intx;

if(n==l)

{if(top==-l)

cout«"栈空！”«endl;

else

{x=stackStorge[topl];

)

}

elseif(n==2)

{if(top2==MaxDualStackSize)

cout«"栈空！"<<endl;

else

{x=stackStorge[top2];

}

elsecout<<”不存在该栈！”<<endl;

returnx;

)

boolStackEmpty(intn);〃栈n为空否

(

if(n==l)

return(topl==-l);

else

return(top2==MaxDualStackSize);

I

boolStackFull();〃栈n已满否

(

returntop2==topl+l

)

voidClearStack(intn);//清空栈n

if(n==l)

topl=-l；

elseif(n==2)

top2=MaxDua1StackSize;

)

);

3-7.答案：

这里使用栈的一些堇本操作

push(st,x):>：元素x进栈st

pop(st,x)：出栈元素赋给x

IsEmpty(st)：判断栈st是否为空

intEnter(stack&sl,stacks2,DataTypex)

(

if(sl->top==m-l)〃队列上溢出

return0;

else

(

push(si,x);

return1;

)

)

intLeave(stack&sl,stacks2,DataTypex)

(

DataTypey;

while(!IsEmpty(si))〃将si的所有元素退栈后进入s2

(

pop(si,y);

push(s2,y);

)

pop(s2,x);〃将s2的栈顶元素退栈并赋给x

while(!IsEmpty(s2))〃将s2余下元素退栈后进入si中

(

pop(s2,y);

pushu(sl,y)：

3-8.答案:

算法如下：

voidHuiWen(LinkListL,intn)

{inti;

charch;

LinkList*p;snode*ls;

InitStack(Is);

p=L->next;

i=l；

while(i<=(n/2))〃将单链表中前半部分的字符进栈

(

ch=p->data;

Is.top++;

Is.data[ls.top]=ch;〃将ch送入栈顶指针所指向的单元

p=p->next;

i++；

)

if((n%2)==l)p=p->next;〃若n为奇数则中间位置的字符不进栈，p

指向〃单链表后半部分的第一个节点

k=l;〃设标志位k=l表示对应字符全部相等，k=0表

〃示至少有一对字符不相等

while((p!=NULL)U(k==l))〃将栈1s中的字符弹出并逐个与单链表后半部

〃分的字符进行比较

(

ch=ls.data[Is.top-];〃将栈顶指针所指的单元内的值赋给ch

if(p->data==ch)p=p->next〃若p指向的结点字符等于顺序栈中栈顶指

针

〃字符，则p顺链后移

elsek=0;〃若p指向的结点字符不等于顺序栈中栈顶指

针

〃字符，则k=0

)

if(k)cout«w这串字符序列为“回文”<<endl;

elsecout<<”这串字符序列不为“回文”<<endl;

}

voidInitStach(Lstach&ls)

(

ls=(snode*)malloc(sizeof(snode));

Is.top=-l

)

3-9.答案：

算法如下：

intSPQDelete(seqPQueue*Q,DataType*x)〃把优先级高的元素先删除，删除成功时

〃数返回1,否则返回0

DataTypemin=Q->list[0]〃初始选Q->list[0]为优先级最高的元素

inti,minIndex=0;//minindex为优先级最高元素的下标

if(Q->size<=0)

(

cout<<”队列已空无数据元素可删!"«endl;

return0;

)

for(i=l;i<Q->size;i++)〃寻找优先级最高的元素及对应下标

if(Q->list[i]<min)

(

min=Q->list[i];

minlndex=i;

}

*x=Q->list[minindex];

Q->list[minIndex]=Q->list[size-1];〃把最后一个元素放在被删除元素的位

置

Q->size—;〃数据元素个数减1

return1;

}

3-10.答案：

算法如下：

intGetValue_NiBoLan(char*str)〃对逆波兰式求值

{char*p；

snode*s;

p=str;

InitStack(s);〃s为操作数栈

while(*p)

(

if(*p是数)

push(s,*p)；

else

(

pop(s,a);pop(s,b);

r=compute(b,*p,a)〃假设compute为执行双目运算的过程

push(s,r);

p++;

)

pop(s,r);

returnr;

3-11.答案：

voidGList_PrintElem(GListA,intlayer)〃递归输出广义表的原子及其所在层

次，layer表示当前层次

(

if(!A)return;

if(!A->tag)

cout«w原子为"所在层为"<<layer〈<endl;

else

(

GList_PrintElem(A->ptr.hp,layer+1);

GList_PrintElem(A->ptr.tp,layer);〃注意尾表与原表是同一层次

)

}//GList_PrintElem

3-12.答案：

voidGList_Copy(GListA,GList&B)〃复制广义表的递归算法

(

if(!A->tag)〃当结点为原子时,直接复制

(

B->tag=0;

B->atom=A->atom;

)

else〃当结点为子表时

(

B->tag=l;

if(A->ptr.hp)

(

B->ptr.hp=malloc(sizeof(GLNode));

GList_Copy(A->ptr.hp,B->ptr.hp);

)〃复制表头

if(A->ptr.tp)

(

B->ptr.tp=malloc(sizeof(GLNode));

GList_Copy(A->ptr.tp,B->ptr.tp);

〃复制表尾

}//GList_Copy

3-12.答案:

(1)

intMatch(charexp[],intn)

(

charst[MaxSize];

inttop=-l;

inti=0;

booltag=ture;

while(i<n&&tag==l)

(

if(exp[i]==>(9

{top++;

st[top]=epx[i];

)

if(exp[i]==,)9

if(st[top]二二'(')top一;

elsetag=ture;

i++；

if(top>=0)

tag=false;

return(tag);

习题4

4-1答案:

本书中主要结点的树形表示可参考书中图4.1的表示法，即全书为整棵树的根，各个章

节为子树，章节名又为子树的根，各节为子树，以此类推。

(1)树中共有175个结点。

(2)叶结点即度为零的结点，在本书主要结点的树形表示中为类似于1.1,1.2.1,1.2.2这

样的结点。

(3)树根的层次为1,其它任一结点所在的层是其双亲的层加lo故第三层结点是类似于

1.1,1.2,2.1,3.2这样的结点。

(4)结点的度是树的结点所拥有的子树数。则根结点即全书节点拥有十棵子树;分别为十

个章节，度为十。又如第一章有七节，即度为七。

4-3答案：

根据二叉树的性质得：有m个叶子的二叉树最少有2m-1个节点。

4-4答案：

后序遍历二叉树结果为CBA,有五种二叉树可得到这一结果，如图：

4-5答案：

其参考算法如下：

voidSeqBiaoPreorder(inti){

if((i>last)||(!a[i])}return;

if(a[i])visit(a[i]);或cout〈〈a[i];/*访问第i个节点*/

SeqBiaoPreorder(2*i+l);/*递归访问第2i+l个节点*/

SeqBiaoPreorder(2*i+2);/*递归访问第2i+2个节点*/

4-7扩充BinaryTree,增加Copy。操作，复制二叉树。用两种方法实现，第一种按前序遍历

复制树，第二种按后序遍历复制树。两种实现方法所需要用到的递归栈空间有什么不同？

答案：第一种按前序遍历复制树参考算法：

voidCopy(BinTreeNode*rt){

if(rt){

BinTreeNode*temp=newBinTreeNode();

temp->data=rt->data;

temp->leftChild=Copy(rt->leftChild);

temp->rightChild=Copy(rt->rightChild);

)

}

第二种按后序遍历复制树参考算法：

voidBitree_Copy_Nonrecursive(BinaryTreeNode*T,BinaryTreeNode&U){

InitStack(SI);InitStack(S2);

SI.Push(T);

U=newBinaryTreeNode();

U->data=T->data;

q=U;S2.Push(U);

while(!StackEmpty(S)){

while(Gettop(SI,p)&&p){

q->1eftChi1d=newBinaryTreeNode();

q=q->leftChild;q->data=p->data;

push(SI,p->leftChild);

push(S2,q);

pop(SI,p);

pop(S2,q);

if(!StackEmpty(SI))

(

pop(SI,p);pop(S2,q);

q->rightChi1d=newBinaryTreeNode();

q=q->rightChild;q->data=p->data;

push(SI,p->rightChild);

push(S2,q);

4-8扩充BinaryTree,增加Compare(x)操作，对当前二叉树与二叉树x进行比较。若两棵二

叉树同构,则返回true,否则返回falseo

答案：参考算法如下：

boolequal(BinaryTreeNode*a,BinaryTreeNode*b){

if(!a&&!b)return1;

if(a&&b&&equal(a->leftChild,b->leftChild)&&equal(a->rightChild,

b->rightChild)return1;

return0;

|

4-10答案：

voidexchange(BinaryTreeNode*rt){

BinaryTreeNode*temp;

if(!rt->leftchild&&!lrt->rightchild)return;

else{temp=rt->leftChild;

rt->leftChild=rt->rightChild;

rt->rightChild=temp;

)

if(rt->leftChild)exchange(rt->leftChild);

if(rt->rightChild)exchange(rt->rightChiId);

4-12答案:

#include<iostream>

usingnamespacestd;

typedefenum{Link,hread}PointerTag;

typedefintTelemType;

typedefstructBiThrNode

(

TelemTypedata;

structBiThrNode*leftChild,*rightChild;

PointerTagItag,rtag;

}BiThrNode,*BiThrTree;

BiThrNode*pre;

voidInThreading(BiThrTreep)

(

if(p)

(

InThreading(p->leftChiId);

if(!p->leftChild)

(

p->1tag=hread;p->leftChild=pre;

)

if(!pre->rightChiId)

(

pre->rtag=hread;pre->rightChild=p;

}

pre=p;

InThreading(p->rightChiId);

}

)

intInorderThreading(BiThrTree&Thrt,BiThrTreeT)

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrTree))))

exit(1);

Thrt->1tag=Link;

Thrt->rtag=hread;

Thrt->rightChild=Thrt;

if(!T)

(

Thrt->leftChild=Thrt;

i

else

(

Thrt->leftChild=T;

pre=Thrt;

InThreading(T);

pre->rightChild=Thrt;pre->rtag=hread;

Thrt->rightChild=pre;

I

return1;

}

intmain()

(

return0;

)

4-14答案：

树与二叉树的转换可参考本书4.4节树与二叉树的转换算法进行。

4-15已知一棵二叉树以二叉链表作为存储结构，编写完成下列操作的算法：对于树中每一个

元素值为x的结点，删去以它为根的子树，并释放相应的结点。

答案：

voidDel_Sub_x(BinaryTreeNode*T,intx){/*删除所有以元素x为根的子树*/

if(T->data==x)Del_Sub(T);/*删除该子树*/

else{/*在左右子树中继续查找*/

if(T->leftChild)Del_Sub_x(T->leftChiId,x);

if(T->rightChiId)Del_Sub_x(T->rightChiId,x);

}/*else*/

}/*Del_Sub_x*/

voidDel_Sub(BitreeT){/*删除子树T*/

if(T->leftChiId)Del_Sub(T->leftChild);

if(T->rightChild)Del_Sub(T->rightChi1d);

free⑴；

}/*Del_Sub*/

4-16答案：

voidPrint_CSTree(CSNode*T,inti){

/*按凹入表形式打印输出树的元素，i表示结点所在层次,初次调用时i=l*/

if(!T)return;

for(j=l;j<i;j++)cout«'';

cout<<T->data<<endl;

Print_CSTree(T->firstChiId,i+1);

Print_CSTree(T->nextSibling,i+1);

I

4.17对以下存储结构分别写出计算树的深度的算法。

(1)双亲表示法；(2)子女兄弟表示法。

答案：(1)双亲表示法计算树的深度的算法参考答案：

intGetDepth_CSTree(CSNode*T){/*求双亲表表示的树T的深度*/

maxdep=l;

for(i=0;i<n,i++){

for(j=i,dep=l;(j=T.nodes[j].parent)>-l;dep++);/*求每一个结点的深度*/

if(dep>maxdep)maxdep=dep;

returnmaxdep;

}/*GetDepth_CSTree*/

(2)子女-兄弟表示法计算树的深度的算法参考答案：

intGetDepth_CSTree(CSNode*T){/*求子女-兄弟表示的树A的深度*/

if(!T)return0;

elsereturn1+Max(Depth(T->firstChiId),Depth(T->nextSibling));

}/*GetDepthCSTree*/

习题5

5-1.答案：

实现一个简单的文档检索管理系统。它将文档(摘要引用)插入到系统中，建立关键字与

文档之间的关

联，并按照给定的关键字检索文档。

ADTDocumentSystem{

Stringkey;〃关键字

Documentdocument;〃文当摘要

DocumnetSystemsystem;

)

ADTDocument{

Stringpreface;〃摘要

Stringcontent;〃弓|用

)

voidinsertDocumentSystem(DcoumentSystemsys,Document,doc){

sys.system=newDocuemntSystem(key,doc);

}

Documentsearch(key,system){

While(system->sys!=nul1){

If(system->key==key)

Returnsystem->doc;

Elsesystem=system->sys;

)

)

5-2.答案：

设计一个算法FreqCount,实现频率计数自组织线性查找表启发式规则，假定线性查找表使

用数组实现。它把查找的值作为输入，并且相应地调整线性查找表。如果值不在线性查

找表中，就把它添加到线性查找表的最后，其频率计数是1。

使用到的数据类型：采用二维数组实现：

IntLink[2][n]〃申明一个2行n列的数组

Intcounter=0〃标记在Link中此时存在多少个值

VoidinitLink(intlocation){

For(inti=0;i<=location;i++)

从i到location之间的值按频率从大到小排列

)

Booleansearch(intnumber){

for(inti=0;i<counter;i++){

If(Link[i][0]==number){

Link[i][1]++;

initLink(i);〃〃如果找到后则重新使数组按Link[l]口从大到小

排列

Returntrue;

)

}

Link[0][counter]=number;

Link[l][counter++]=l;

Returnfalse;

}

5-3.答案：

设计一个算法Transpose,实现转置自组织线性查找表启发式规则，假定线性查找表使

用数组实现。它把查找的值作为输入，并且相应地调整线性查找表。如果值不在线性查

找表中，就把它添加到线性查找表的最后。

使用到的数据类型：采用二维数组实现：

IntLink[n]//申明一个2行n列的数组

Intcounter=0〃标记在Link中此时存在多少个值

Booleansearch(intnumber){

for(inti=0;i<counter;i++){

If(Link[i]==number){

If(i>0)

交换Link[i]与Link-；〃转换位置

Returntrue;

)

Link[counter++]=number;

Returnfalse;

)

5-4.答案:

对顺序存储的有序查找表：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,用二分

查找算法查找关键字2、10、17时，其比较次数分别是多少？

先看key=2的查找过程：

位置：01234567891011121314

(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)

第一次：tlow=0tmid=7fhigh=14

第二次：tlow=0tmid=3thigh=6

第三次:tlow=0tmid=lthigh=2

成功结束!

再看key=10的查找过程：

位置：01234567891011121314

(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)

第一次：tlow=0tmid=7fhigh=14

第二次：tlow=8tmid=llthigh=14

第三次:tlow=8tmid=9thigh=10

成功结束!

再看key=17的查找过程：

位置：01234567891011121314

(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)

第一次：tlow=0tmid=7fhigh=14

第二次：tlow=8tmid=llthigh=14

第三次：tlow=12fmid=13thigh=14

第四次

tlow=14thigh=14

第五次查找失败!

5-5.答案：

对表：Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec

(1)试按表中元素的顺序依次插入到一棵初始为空的二叉查找树中；画出插入完成后的

二叉查找树.，并求其在等概率情况下查找成功的平均查找长度。

(2)若对表中元素先进行排序构成有序表，在等概率情况下对此表进行二分查找，试求

成功查找的平均查找长度。

5-6.答案：

假设在某语言中，可通过语句EQUIVALENCE定义共享变量，共享变量共享同一存储单元。其

规则是EQUIVALENCE语句中的每一对括号内的变量是共享变量，含共同变量的组内的所

有变量也是共享变量。如EQUIVALENCE((a,c,f),(h,k,m),(x,d,a),(k,e),(d,j,p,s)),

定义了a、c、f、x、d、_j、p、s是共享变量，h、k、m、e是共享变量，这样仅需为这

些变量分配两个存储单元即可。试借助MFSet,以EQUIVALENCE语句为输入，计算所需

单元数。

classMFSet{

intn;

int*parent;〃下标对应成员，值为双亲，根兼作子集的名称，根的双亲置0

public:

MFSet(intm)

viodMerge(inta,intb);//a和b为根,即子集名

intFind(inte);

voidOut();

};//classMFSet

MFSet(intm){//初始时，共输入m个字符,初始时为

n=m;parent=newint[n+1];

for(i=l;i<=n;i++)parent[i]=-l;//parent[0]暂且空闲

:}

viodMerge(chara,charb){〃&和b为根，即集合名

parent[b-'a']=a-'a';

boolFind(chare){

inta=e-'a';

while(parent[a]!=-l){

if(parent[])

a=parent[a];

returnfalse;

}//Find

5-7.答案:

在0〜16的散列地址空间中，试对关键字序列(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,

Sep,Oct,Nov,Dec),分别用以下两种方法构造哈希表，假设h(key)=|_i/2」，其中i为

关键字中第一个字母在字母表中的序号：(1)用线性探测再散列；(2)用开哈希法处理。

(1)用线性探测再散列：

01234567891011121314151()

apraugfebdecjanjulmarmarnovoctsep

(2)用开哈希法处理(略)

5-8.答案：

采用线性探测再散列，在下列各种情况下找到哈希函数除数m的合适值。

(1)n=50,S„W3,UnW20。(2)n=500,SnW5,UnW60。(3)n=10,S„W2,Un<10。

(1)S=l/2(l+l/(l-a))<=3U=l/2(1+1/(1-a)(1-a))<=3

可知a<0.9;由S知a<=4/5;即a<=min(0.9,0.8);

其中a=n/m;因为n=50;所以250/4的上限，所以m取63。

(2)(3)做法同上。

5-9.答案：

对于以下各种条件，找出哈希函数除数m