数据结构答案.docx

数据结构答案.docx

《数据结构答案.docx》由会员分享，可在线阅读，更多相关《数据结构答案.docx（16页珍藏版）》请在冰点文库上搜索。

数据结构答案

第1章绪论

【习题1-1】根据二元组表示分析其数据结构。

有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示（当出现多个关系时，对每个关系画出相应的结构图），并指出它们分别属于何种结构。

1．A=（K,R），其中，

K={a1,a2,a3,,an}

R={}

2．B=（K,R），其中，

K={a,b,c,d,e,f,g,h}

R={r}

r={,,,,,,}

3．C=（K,R），其中，

K={a,b,c,d,e,f,g,h}

R={,,,,,,}

4．D=（K,R），其中，

K={1,2,3,4,5,6}

R={（1,2）,（2,3）,（2,4）,（3,4）,（3,5）,（3,6）,（4,5）,（4,6）}

5．E=（K,R），其中，

K={48,25,64,57,82,36,75,43}

R={r1,r2,r3}

r1={<48,25>,<25,64>,<64,57>,<57,82>,<82,36>,<36,75>,<75,43>}

r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>,<36,43>}

r3={<25,36>,<36,43>,<43,48>,<48,57>,<57,64>,<64,75>,<75,82>}

参考解答：

略。

【习题1-2】按要求设计抽象数据类型。

设计二次多项式ax2+bx+c的一种抽象数据类型，假定该抽象数据类型命名为QUAdratic，该类型的数据部分为3个系数项a、b和c，操作部分为：

1．初始化数据成员a、b和c（假定用记录类型Quadratic定义数据成员），每个数据成员的默认值为0。

voidInitQuadratic（Quadratic&q,floataa=0,floatbb=0,floatcc=0）;

2．做两个多项式加法，即使对应的系数相加，返回相加结果。

QuadraticAdd（Quadratic&q1,Quadratic&q2）;

3．根据给定x的值，计算多项式的值并返回。

floatEval（Quadratic&q,floatx）;

4．计算方程ax2+bx+c=0的两个实数根并引用返回，对于有实根、无实根和不是二次方程（即a==0）这3种情况都要返回不同的整数值，以便调用函数做不同的处理。

intRoot（Quadratic&q,float&r1,float&r2）;

5．按照ax**2+bx+c的格式（x2用x**2表示）输出二次多项式，在输出时要注意去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。

voidPrint（Quadratic&q）;

请写出上面每一个操作的具体实现。

作为选择，有兴趣的学生还可以给出该抽象数据类型所对应的C++类的描述。

参考答案包含在下面的程序之中。

#include

#include

structQuadratic{

floata;floatb;floatc;

};

voidInitQuadratic（Quadratic&q,floataa,floatbb,floatcc）

{

q.a=aa;

q.b=bb;

q.c=cc;

}

QuadraticAdd（Quadratic&q1,Quadratic&q2）

{

Quadraticq;

q.a=q1.a+q2.a;

q.b=q1.b+q2.b;

q.c=q1.c+q2.c;

returnq;

}

floatEval（Quadratic&q,floatx）

{

return（q.a*x*x+q.b*x+q.c）;

}

intRoot（Quadratic&q,float&r1,float&r2）

{

if（q.a==0）return-1;

floatx=q.b*q.b-4*q.a*q.c;

if（x>=0）{

r1=（float）（-q.b+sqrt（x））/（2*q.a）;

r2=（float）（-q.b-sqrt（x））/（2*q.a）;

return1;

}

elsereturn0;

}

voidPrint（Quadratic&q）

{

if（q.a）{

if（q.a==1.0）cout<<'';

elseif（q.a==-1.0）cout<<'-';

elsecout<

cout<<"x**2";

}

if（q.b）

if（q.b>0）{

cout<<"+";

if（q.b!

=1.0）cout<

cout<<"x";

}

else{

if（q.b==-1.0）cout<<'-';

elsecout<

cout<<"x";

}

if（q.c）

if（q.c>0）cout<<"+"<

elsecout<

cout<

}

voidmain（）

{

Quadraticq1,q2;

floata,b,c,d1,d2;

cout<<"输入一个二次多项式三个系数项的值：

";

cin>>a>>b>>c;

InitQuadratic（q1,a,b,c）;

cout<<"输入另一个二次多项式三个系数项的值：

";

cin>>a>>b>>c;

InitQuadratic（q2,a,b,c）;

q2=Add（q1,q2）;

cout<

intf=Root（q1,d1,d2）;

if（f==1）cout<

Print（q1）;

Print（q2）;

}

若采用C++语言中的“类”描述，则参考程序如下。

#include

#include

classQuadratic{

floata;floatb;floatc;

public:

Quadratic（floataa=0,floatbb=0,floatcc=0）;

QuadraticAdd（Quadratic&q2）;

floatEval（floatx）;

intRoot（float&r1,float&r2）;

voidPrint（）;

};

Quadratic:

:

Quadratic（floataa,floatbb,floatcc）

{

a=aa;b=bb;c=cc;

}

QuadraticQuadratic:

:

Add（Quadratic&q2）

{

Quadraticq;

q.a=a+q2.a;

q.b=b+q2.b;

q.c=c+q2.c;

returnq;

}

floatQuadratic:

:

Eval（floatx）

{

return（a*x*x+b*x+c）;

}

intQuadratic:

:

Root（float&r1,float&r2）

{

if（a==0）return-1;

floatx=b*b-4*a*c;

if（x>=0）{

r1=（float）（-b+sqrt（x））/（2*a）;

r2=（float）（-b-sqrt（x））/（2*a）;

return1;

}

elsereturn0;

}

voidQuadratic:

:

Print（）

{

if（a）{

if（a==1.0）cout<<'';

elseif（a==-1.0）cout<<'-';

elsecout<

cout<<"x**2";

}

if（b）

if（b>0）{

cout<<"+";

if（b!

=1.0）cout<

cout<<"x";

}

else{

if（b==-1.0）cout<<'-';

elsecout<

cout<<"x";

}

if（c）

if（c>0）cout<<"+"<

elsecout<

cout<

}

voidmain（）

{

floata,b,c,d1,d2;

cout<<"输入一个二次多项式三个系数项的值：

";

cin>>a>>b>>c;

Quadraticq1（a,b,c）;

cout<<"输入另一个二次多项式三个系数项的值：

";

cin>>a>>b>>c;

Quadraticq2（a,b,c）;

q2=q1.Add（q2）;

cout<

（2）<<''<

intf=q1.Root（d1,d2）;

if（f==1）cout<

q1.Print（）;

q2.Print（）;

}

【习题1-3】用C++函数描述算法并求出其时间复杂度。

1．比较同一简单类型的两个数据x1和x2的大小，对于x1>x2，x1==x2和x1”，“=”和“<”字符。

假定简单类型用SimpleType表示，它可通过typedef语句定义为任一简单类型。

2．将一个字符串中的所有字符按相反的次序重新放置。

3．求一维double型数组a[n]中的所有元素之乘积。

4．计算

的值。

5．假定一维整型数组a[n]中的每个元素值均在［0,200］区间内，分别统计出落在［0,20］，［20,50］，［50,80］，［80,130］，［130,200］等各区间内的元素个数。

6．从二维整型数组a[m][n]中查找出最大元素所在的行、列下标。

参考解答如下。

1．charCompare（SimpleTypex1,SimpleTypex2）

{

if（x1>x2）return'>';

elseif（x1==x2）return'=';

elsereturn'<';

}

时间复杂度为O

（1）。

2．voidReverse（char*p）

{

intn=strlen（p）;

for（inti=0;i

charch;

ch=p[i];

p[i]=p[n-i-1];

p[n-i-1]=ch;

}

}

时间复杂度为O（n）。

3．doubleProduct（doublea[],intn）

{

doublep=1;

for（inti=0;i

p*=a[i];

returnp;

}

时间复杂度为O（n）。

4．doubleAccumulate（doublex,intn）

{

doublep=1,s=1;

for（inti=1;i<=n;i++）{

p*=x;

s+=p/（i+1）;

}

returns;

}

时间复杂度为O（n）。

5．intCount（inta[],intn,intc[5]）//用数组c[5]保存统计结果

{

intd[5]={20,50,80,130,201};//用来保存各统计区间的上限

inti,j;

for（i=0;i<5;i++）c[i]=0;//给数组c[5]中的每个元素赋初值0

for（i=0;i

{

if（a[i]<0||a[i]>200）

return0;//返回数值0表示数组中数据有错，统计失败

for（j=0;j<5;j++）//查找a[i]所在的区间

if（a[i]

c[j]++;//使统计相应区间的元素增1

}

return1;//返回数值1表示统计成功

}

时间复杂度为O（n）。

6．voidfind（inta[M][N],intm,intn,int&Lin,int&Col）

//M和N为全局常量,应满足M>=n和N>=n的条件,Lin和Col为

//引用形参,它是对应实参的别名,其值由实参带回

{

Lin=0;Col=0;

for（inti=0;i

for（intj=0;j

if（a[i][j]>a[Lin][Col]）{Lin=i;Col=j;}

}

时间复杂度为O（n2）。

【习题1-4】指出下列各算法的功能并求出其时间复杂度。

1．intPrime（intn）

{

inti=2;

intx=（int）sqrt（n）;

while（i<=x）{

if（n%i==0）break;

i++;

}

if（i>x）return1;

elsereturn0;

}

2．intsum1（intn）

{

intp=1,s=0;

for（inti=1;i<=n;i++）{

p*=i;

s+=p;

}

returns;

}

3．intsum2（intn）

{

ints=0;

for（inti=1;i<=n;i++）{

intp=1;

for（intj=1;j<=i;j++）p*=j;

s+=p;

}

returns;

}

4．intfun（intn）

{

inti=1,s=1;

while（s

returni;

}

5．voidUseFile（ifstream&inp,intc[10]）

//假定inp所对应的文件中保存有n个整数

{

for（inti=0;i<10;i++）c[i]=0;

intx;

while（inp>>x）{

i=x%10;

c[i]++;

}

}

6．voidmtable（intn）

{

for（inti=1;i<=n;i++）{

for（intj=i;j<=n;j++）

cout<

（2）<

cout<

}

}

7．voidcmatrix（inta[M][N],intd）//M和N为全局整型常量

{

for（inti=0;i

for（intj=0;j

a[i][j]*=d;

}

8．voidmatrimult（inta[M][N],intb[N][L],intc[M][L]）

//M、N和L均为全局整型常量

{

inti,j,k;

for（i=0;i

for（j=0;j

c[i][j]=0;

for（i=0;i

for（j=0;j

for（k=0;k

c[i][j]+=a[i][k]*b[k][j];

}

参考答案如下。

1．判断n是否是一个素数，若是则返回数值1，否则返回0。

该算法的时间复杂度为O（

）。

2．计算

的值。

时间复杂度为O（n）。

3．计算

的值。

时间复杂度为O（n2）。

4．求出满足不等式1+2+3++i≥n的最小i值。

时间复杂度为O（

）。

提示：

因为1+2+3++i=（1+i）i/2，即当n很大时i的平方与n成正比，所以i的值（即函数中while循环的次数）与n的平方根成正比。

5．利用数组c[10]中的每个元素c[i]对应统计出inp所联系的整数文件中个位值同为i的整数个数。

时间复杂度为O（n）。

6．打印出一个具有n行的乘法表，第i行（1

i

n）中有n–i+1个乘法项，每个乘法项为i与j（i

j

n）的乘积。

时间复杂度为O（n2）。

7．使数组a[M][N]中的每一个元素均乘以d的值。

时间复杂度为O（M×N）。

8．矩阵相乘，即a[M][N]×b[N][L]→c[M][L]。

时间复杂度为O（M×N×L）。

*【习题1-5】设计集合的一种抽象数据类型。

集合是由若干个同一类型元素组成的、元素之间不存在任何关系的一种数据结构。

通常，一个集合用一对大括号括起来，元素之间用逗号分隔。

一个集合中的元素来自于一个数据集，并且不允许出现重复的元素。

如对于1～n之间的整数集，它共包含有2n个不同的集合，其中，{}表示空集，{1,2,…,n}表示全集。

假定一个整数集为1～3，则在它之上可以构成的8（23）个集合为：

{}，{1}，{2}，{3}，{1,2}，{1,3}，{2,3}，{1,2,3}

在C++语言中，可用一个整型数组来表示一个集合，若一个数组元素的值为0，则表示相应元素不在集合中，若为1则表示相应元素存在于集合中。

如对于整数集1～6之上的一个集合{1,4,5}，则用整型数组a[7]表示（a[0]元素未用）为：

012345 6

1

0

0

1

1

0

对于集合运算通常有并（∪）、交（∩）和属于（）等。

两个集合的并的结果仍为一个集合，它包含有两个集合中的所有元素，当然不允许出现重复。

两个集合的交的结果也仍为一个集合，它中的每一个元素同时属于两个集合。

属于运算是判断一个元素是否存在于一个集合之中，若存在则返回真（true），否则返回假（false）。

若x={1,4,5}，y={2,4}，则x∪y={1,2,4,5}，x∩y={4}，1x为真，2x为假。

假定在1～SETSIZE整数集（SETSIZE为一个整型全局常量）上建立集合，抽象数据类型名用SET表示，该类型的数据部分为一个整型数组m[SETSIZE+1]，用于保存一个集合，操作部分如下。

1．对一个集合中的所有元素清0，假定用记录类型Set定义数据成员，即Set类型的定义为：

structSet{intm[SETSIZE+1];}

该操作就是对Set类型的一个对象初始化，使其数组m域中的每个元素被置为0。

voidInitSet（Set&s）;

2．利用整型数组a[n]初始化数据成员，即置一个集合中的m[a[i]]为1（0

i

n–1），如a[3]={1,3,6}，则相应集合中的m[1]、m[3]和m[6]元素应被置为1。

voidInitSet（Set&s,inta[],intn）;

3．重载加法运算符实现两个集合的并运算。

Setoperator+（Set&s1,Set&s2）;

4．重载乘法运算符实现两个集合的交运算。