数据结构教程(java)习题解答

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

1、1第一章第一章第一章第一章绪论绪论绪论绪论1111....1111单选题单选题单选题单选题1.D2.C3.D4.B5.A6.B7.C8.C9.A10.B第10小题提示：在含有n个元素的数据表中顺序查找任一元素的平均比较次数为pciiin=∑1，pi为查找第i个元素的概率，ci是查找第i个元素时需要比较的元素数，查找所有元素的概率之和为1，若查找每个元素的概率相同，则平均查找长度的计算公式可简化为11niinc=∑。此题的计算式为)76543(121241131+++++×+×=35/121.1.1

2、.1.2222算法分析题算法分析题算法分析题算法分析题1.判断n是否为一个素数，若是则返回逻辑值true，否则返回逻辑值false。该算法的时间复杂度为O(n)。2.计算∑=nii1!的值。时间复杂度为O(n)。3.计算∑=nii1!的值。时间复杂度为O(n2)。4.求出满足不等式1+2+3+...+i≥n的最小i值。时间复杂度为O(n)。提示：因为1+2+3+...+i=(1+i)i/2，即当n很大时i的平方与n成正比，所以i的值（即函数中while循环的次数）与n的平方根成正比。5.打印出一个

3、具有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]→c[m][p]。时间复杂度为O(M×N×P)。这里假定二维数组a的行列数为m和n，二维数组b的行列数为n和p，二维数组c的行列数为m和p。1.1.1.1.3333算法设计题算法设计题算法设计题算法设计题设计二次

4、多项式ax2+bx+c的一种抽象数据类型，假定起名为Quadratic，该类型的数据部分为双精度类型的3个系数项a、b和c，操作部分为：(1)初始化二次多项式中的三个数据成员a、b和c。Quadratic(doubleaa,doublebb,doublecc);(2)做两个多项式加法，即它们对应的系数相加，返回相加结果。Quadraticadd(Quadraticq);(3)根据给定x的值计算多项式的值并返回。doublevalue(doublex);(4)计算多项式等于0时的两个实数根，对于有实

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

6、类型如下：：：：ADTQuadraticisData:doublea,b,c;//二次项、一次项和常数项系数Operations:publicQuadratic(doubleaa,doublebb,doublecc);//构造函数publicQuadraticadd(Quadraticq);//二次多项式相加publicdoublevalue(doublex);//二次多项式求值publicintseekRoot(double[]r);//二次多项式方程求解publicvoidprint();//

7、输出二次多项式endQuadraticJavaJavaJavaJava类类类类参考答案如下参考答案如下参考答案如下参考答案如下：：：：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

8、;qq.c=c+q.c;returnqq;}publicdoublevalue(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;//有实数根返回13}elsereturn0;/