数据结构实用教程第二版答案_徐孝凯

《数据结构实用教程第二版答案_徐孝凯》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章绪习题一1.有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示（当出现多个关系时，对每个关系画出相应的结构图），并指出它们分别属于何种结构。⑴A=(K,R)其中K={a1,a2,a3...,an}R={}⑵B=(K,R)其中K={a,b,c,d,e,f,g,h}R={r}r={,,,,,,}⑶C=(K,R)其中K={a,b,c,d,f,g,h}R={r}r={,,,,,,}⑷D=(K,R)其中K={1,2,

2、3,4,5,6}R={r}r={(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,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>

3、,<75,82>}解：⑴是集合结构；⑵是线性结构；⑶⑷是树型结构；⑸散列结构。只作为参考。2.设计二次多项式ax2+bx+c的一种抽象数据类型，假定起名为QIAdratic,该类型的数据部分分为三个系数项a、b和c，操作部分为：(请写出下面每一个操作的具体实现)。⑴初始化数据成员ab和c(假定用记录类型Quadratie定义成员)，每个数据成员的默认值为0。QuadraticInitQuadratic(floataa=0,floatbb=0,floatcc=0);解：QuadraticInitQuadratic(floataa,floatbb,floatcc){

4、Quadraticq;q.a=aa;q.b=bb;q.c=cc;returnq;}⑵做两个多项式加法,即使对应的系数相加,并返回相加的结果。QuadraticAdd(Quadraticq1,Quadraticq2);解：QuadraticAdd(Quadraticq1,Quadraticq2);{Quadraticq;q.a=q1.a+q2.a;q.b=q1.b+q2.b;q.c=q1.c+q2.c;returnq;}⑶根据给定x的值计算多项式的值。floatEval(Quadraticq,floatx);解：floatEval(Quadraticq,float

5、x){return(q.a*x*x+q.b*x+q.c);}⑷计算方程ax2+bx+c=0的两个实数根，对于有实根、无实根和不是实根方程(即a==0)这三种情况要返回不同的整数值，以便于工作调用函数做不同的处理。intRoot(Quadraticq,float&r1,float&r2);解：intRoot(Quadraticq,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.

6、b-sqrt(x))/(2*q.a);return1;}elsereturn0;}⑸按照ax**2+bx+c的格式(x2用x**2表示)输出二次多项式，在输出时要注意去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。voidPrint(Quadraticq)解：voidPrint(Quadraticq){if(q.a)cout<0)cout<<"+"<0)cout<<"+"<

7、out<x2,x1=x2和x1''='和'<'字符。假定简单类型用SimpleType表示，它可通过typedef语句定义为任一简单类型。解：charcompare(SimpleTypex1,SimpleTypex2){if(x1>x2)return'>';elseif(x1==x2)return'=';elsereturn'<';}其时间复杂度为O(1)⑵将一个字符串中的所有字符按相反方的次序重新

8、放置。解：voidRev