《数据结构实用教程第二版答案徐孝凯》由会员分享，可在线阅读，更多相关《数据结构实用教程第二版答案徐孝凯（68页珍藏版）》请在金锄头文库上搜索。
1、 第一章绪习 题 一1.有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示（当出现多个关系时，对每个关系画出相应的结构图），并指出它们分别属于何种结构。 A=(K,R)其中K=a1,a2,a3.,anR= B=(K,R)其中K=a,b,c,d,e,f,g,hR=rr=, C=(K,R)其中K=a,b,c,d,f,g,hR=rr=, D=(K,R)其中K=1,2,3,4,5,6R=rr=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6) E=(K,R)其中K=48,25,64,57,82,36,75,43R=r1,r2,r3r1=,r2=,
2、r3=,解：是集合结构；是线性结构；是树型结构；散列结构。只作为参考。2.设计二次多项式ax2+bx+c的一种抽象数据类型，假定起名为QIAdratic,该类型的数据部分分为三个系数项a、b和c，操作部分为：(请写出下面每一个操作的具体实现)。 初始化数据成员ab和c(假定用记录类型Quadratie定义成员)，每个数据成员的默认值为0。Quadratic InitQuadratic(float aa=0,float bb=0,float cc=0);解：Quadratic InitQuadratic(float aa,float bb,float cc)Quadratic q;q.a=aa;
3、q.b=bb;q.c=cc;return q; 做两个多项式加法,即使对应的系数相加,并返回相加的结果。Quadratic Add(Quadratic q1,Quadratic q2);解：Quadratic Add(Quadratic q1,Quadratic q2);Quadratic q;q.a=q1.a+q2.a;q.b=q1.b+q2.b;q.c=q1.c+q2.c;return q; 根据给定x的值计算多项式的值。float Eval(Quadratic q,float x);解：float Eval(Quadratic q,float x)return(q.a*x*x+q.b*x
4、+q.c); 计算方程ax2+bx+c=0的两个实数根，对于有实根、无实根和不是实根方程(即a=0)这三种情况要返回不同的整数值，以便于工作调用函数做不同的处理。int Root(Quadratic q,float& r1,float& r2);解：int Root(Quadratic q,float& r1,float& r2)if(q.a=0)return -1;float x=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);return 1;elseretur
5、n 0; 按照ax*2+bx+c的格式(x2用x*2表示)输出二次多项式，在输出时要注意去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。void Print(Quadratic q)解：void Print(Quadratic q)if(q.a) coutq.a0)cout+q.bx;elsecoutq.b0)cout+q.c;elsecoutq.c;coutx2,x1=x2和x1=和x2) return;else if(x1=x2) return =;else return;其时间复杂度为O(1) 将一个字符串中的所有字符按相反方的次序重新放置。解：void Reverse(ch
6、ar*p)int n=strlen(p);for(int i=0;in/2;i+)char ch;ch=pipi=pn-i-1;pn-i-1=ch;其时间复杂度为O(n) 求一维double型数组an中的所有元素之乘积。解：double product(double a,int n)double p=1;for(int i=0;in;i+)p*=ai;return p;其时间复杂度为O(n) 计算ni=0xi/i+1的值。解：double Accumulate(double x,int n)double p=1,s=1;for(int i=1;i=n;i+)p*=x;s+=p/(i+1);re
7、turn s;其时间复杂度为O(n) 假定一维数组an中的每个元素值均在0，200区间内，分别统计出落在0，20),20,50),50,80),80,130),130,200等各区间的元素个数。解：int Count(int a,int n,int c5)/用数组c5保存统计结果int d5=20,50,80,130,201;/用来保存各统计区间的上限int i,j;for(i=0;i5;i+)ci=0;/给数组c5中的每个元素赋初值0for(i=0;in;i+)if(ai200)return 0;/返回数值0表示数组中数据有错，统计失败for(j=0;j5;j+)/查找ai所在区间if(ai
8、=n和N=n的条件，Lin和Col为引用/形参，它是对应实参的别名，其值由实参带回Lin=0;Col=0;for(int i=0;im;i+)for(int j=0;jaLinCol)Lin=i;Col=j;其时间复杂度为O(m*n)4.指出下列各算法的功能并求出其时间复杂度。 int prime(int n)int i=2;int x=(int)sqrt(n);while(ix)return 1;elsereturn 0;解：判断n是否是一个素数，若是则返回数值1，否则返回0。该算法的时间复杂度为O(n1/2)。 int sum1(int n)int p=1,s=0;for(int i=1;
9、i=n;i+)p*=i;s+=p;return s;解：计算i!(上标为n，下标为i=1)的值，其时间的复杂度为O(n)。 int sum2(int n)int s=0;for(int i=1;i=n;i+)int p=1;for(int j=1;j=i;j+)p*=j;s+=p;return s;解：计算i!的值，时间复杂度为O(n2) int fun(int n)int i=1,s=1;while(sn)s+=+i;return i;解：求出满足不等式1+2+3.+in的最小i值， 其时间复杂度为O(n1/2)。 void UseFile(ifstream& inp,int c10)/假定
10、inp所对应的文件中保存有n个整数for(int i=0;ix)i=x%10;ci+;解：利用数组c10中的每个元素ci对应统计出inp所联系的整数文件中个位值同为i的整数个数，时间复杂度为O(n) void mtable(int n)for(int i=1;i=n;i+)for(int j=i;j=n;j+)couti*j=setw(2)i*j;coutend1;解：打印出一个具有n行的乘法表，第i行(1in)中有n-i+1个乘法项，每个乘法项为i与j(ijn)的乘积，时间复杂度为O(n2)。 void cmatrix(int aMN,int d)/M和N为全局整型常量for(int i=0;iM;i+)for(int j=0;jN;j+)aij*=d;解：使数组aMN中的每一个元素均详细以d的值，时间复杂度为O(M*N) void matrimult(int aMN,int bNL,int cML)/int i,j,k;for(i=0;iM;i+)for(j=0;jL;j+)cij=0;for(i=0;iM;i+)for(j=0
