数据结构教程(Java)习题解答.doc

《数据结构教程(Java)习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章绪论1.1单选题1.D2.C3.D4.B5.A6.B7.C8.C9.A10.B第10小题提示：在含有n个元素的数据表中顺序查找任一元素的平均比较次数为，pi为查找第i个元素的概率，ci是查找第i个元素时需要比较的元素数，查找所有元素的概率之和为1，若查找每个元素的概率相同，则平均查找长度的计算公式可简化为。此题的计算式为=35/121.2算法分析题1.判断n是否为一个素数，若是则返回逻辑值true，否则返回逻辑值false。该算法的时间复杂度为O()。2.计算的值。时间复杂度为O(n)。3.计算的值。时间复杂度为O(n

2、2)。4.求出满足不等式1+2+3+...+i≥n的最小i值。时间复杂度为O()。提示：因为1+2+3+...+i=(1+i)i/2，即当n很大时i的平方与n成正比，所以i的值（即函数中while循环的次数）与n的平方根成正比。5.打印出一个具有n行的乘法表，第i行（1≤i≤n）中有n-i+1个乘法项，每个乘法项为i与j（i≤j≤n）的乘积。时间复杂度为O(n2)。6.统计并返回二维数组a中大于等于k的元素的个数。时间复杂度为O(m×n)，假定m和n分别表示二维数组a的行数和列数。7.矩阵相乘，即a[m][n]×b[n][p

3、]→c[m][p]。时间复杂度为O(M×N×P)。这里假定二维数组a的行列数为m和n，二维数组b的行列数为n和p，二维数组c的行列数为m和p。1.3算法设计题设计二次多项式ax2+bx+c的一种抽象数据类型，假定起名为Quadratic，该类型的数据部分为双精度类型的3个系数项a、b和c，操作部分为：(1)初始化二次多项式中的三个数据成员a、b和c。Quadratic(doubleaa,doublebb,doublecc);(2)做两个多项式加法，即它们对应的系数相加，返回相加结果。Quadraticadd(Quadrati

4、cq);(3)根据给定x的值计算多项式的值并返回。doublevalue(doublex);(4)计算多项式等于0时的两个实数根，对于有实根、无实根和不是二次方程（即a==0）这3种情况需要返回不同的整数值(1,0,-1)，以便调用函数能够做不同的处理。当有实数根时，分别用r[1]和r[2]保存所得到的两个实数根。intseekRoot(double[]r);(5)按照a*x**2+b*x+c的格式（x2用x**2表示）输出二次多项式，在输出时要注意去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。voidprin

5、t();请写出上面的抽象数据类型所对应的Java类。抽象数据类型如下：ADTQuadraticisData:doublea,b,c;//二次项、一次项和常数项系数Operations:publicQuadratic(doubleaa,doublebb,doublecc);//构造函数publicQuadraticadd(Quadraticq);//二次多项式相加publicdoublevalue(doublex);//二次多项式求值publicintseekRoot(double[]r);//二次多项式方程求解publicv

6、oidprint();//输出二次多项式endQuadraticJava类参考答案如下：publicclassQuadratic{privatedoublea,b,c;publicQuadratic(doubleaa,doublebb,doublecc){a=aa;b=bb;c=cc;}publicQuadraticadd(Quadraticq){Quadraticqq=newQuadratic(0,0,0);qq.a=a+q.a;qq.b=b+q.b;qq.c=c+q.c;returnqq;}publicdoubleval

7、ue(doublex){returna*x*x+b*x+c;}publicintseekRoot(double[]r){if(a==0)return-1;//不是二次方程返回-1doublex=b*b-4*a*c;if(x>=0){r[1]=(-b+Math.sqrt(x))/(2*a);r[2]=(-b-Math.sqrt(x))/(2*a);return1;//有实数根返回1}elsereturn0;//有虚数根返回0}publicvoidprint(){if(a!=0.0)//输出二次项System.out.print

8、(a+"*x**2");if(b!=0.0)//输出一次项if(b>0)System.out.print("+"+b+"*x");elseif(b<0)System.out.print(b+"*x");if(c!=0.0)//输出常数项if(c>0)System.out.print("+"