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

第一章 绪论

1.1 单选题

1. D 2. C 3. D 4. B 5. A 6. B 7. C 8. C 9. A 10. B

第10小题提示：在含有n个元素的数据表中顺序查找任一元素的平均比较次数为

i?1

?pici，p为查找第i个元素的概率，c是查找第i个元素时需要比较的元素数，查找所

i

i

n

有元素的概率之和为1，若查找每个元素的概率相同，则平均查找长度的计算公式可简化为

1ni?1?ci。

1311?2?(3?4?5?6?7)=35/12 412n 此题的计算式为?1?

1.2 算法分析题 1. 判断n是否为一个素数，若是则返回逻辑值true，否则返回逻辑值false。该算法的时间复杂度为O(

nn)。

2. 计算

?i!的值。时间复杂度为O(n)。 ?i!的值。时间复杂度为O(n)。

2i?1ni?1 3. 计算

4. 求出满足不等式1+2+3+...+i≥n的最小i值。时间复杂度为O(n)。 提示：因为1+2+3+...+i=(1+i)i/2，即当n很大时i的平方与n成正比，所以i的值（即函数中while循环的次数）与n的平方根成正比。

5. 打印出一个具有n行的乘法表，第i行（1≤i≤n）中有n-i+1个乘法项，每个乘法

2

项为i与j（i≤j≤n）的乘积。时间复杂度为O(n)。 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.3 算法设计题

2

设计二次多项式ax+bx+c的一种抽象数据类型，假定起名为Quadratic，该类型的数据部分为双精度类型的3个系数项a、b和c，操作部分为： (1) 初始化二次多项式中的三个数据成员a、b和c。 Quadratic(double aa, double bb, double cc);

(2) 做两个多项式加法，即它们对应的系数相加，返回相加结果。 Quadratic add(Quadratic q);

(3) 根据给定x的值计算多项式的值并返回。 double value(double x); (4) 计算多项式等于0时的两个实数根，对于有实根、无实根和不是二次方程（即a==0）这3种情况需要返回不同的整数值(1,0,-1)，以便调用函数能够做不同的处理。当有实数根时，分别用r[1]和r[2]保存所得到的两个实数根。

1

int seekRoot(double[] r);

2

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

请写出上面的抽象数据类型所对应的Java类。 抽象数据类型如下：

ADT Quadratic is Data:

double a,b,c; //二次项、一次项和常数项系数 Operations:

public Quadratic(double aa, double bb, double cc);//构造函数 public Quadratic add(Quadratic q); //二次多项式相加 public double value(double x); //二次多项式求值 public int seekRoot(double[] r); //二次多项式方程求解 public void print(); //输出二次多项式 end Quadratic Java类参考答案如下：

public class Quadratic {

private double a,b,c;

public Quadratic(double aa, double bb, double cc) { a=aa; b=bb; c=cc; }

public Quadratic add(Quadratic q) { Quadratic qq=new Quadratic(0,0,0); qq.a=a+q.a; qq.b=b+q.b; qq.c=c+q.c; return qq; }

public double value(double x) { return a*x*x+b*x+c; }

public int seekRoot(double[] r) {

if(a==0) return -1; //不是二次方程返回-1 double x=b*b-4*a*c; if(x>=0){

r[1]=(-b+Math.sqrt(x))/(2*a); r[2]=(-b-Math.sqrt(x))/(2*a); return 1; //有实数根返回1

2

} else

return 0; //有虚数根返回0 }

public void print() {

if(a!=0.0) //输出二次项

System.out.print(a+\ if(b!=0.0) //输出一次项

if(b>0) System.out.print(\ else if(b<0) System.out.print(b+\ if(c!=0.0) //输出常数项

if(c>0) System.out.print(\ else if(c<0) System.out.print(c); System.out.println(); } }

用于调试的主函数类如下： public class Chap1_x2 {

public static void main(String[] args) {

double a1=3,b1=5,c1=-2; double a2=1,b2=6,c2=5;

Quadratic q1=new Quadratic(a1,b1,c1); Quadratic q2=new Quadratic(a2,b2,c2); Quadratic q3;

q3=q1.add(q2);

double x=q1.value(2); double[] r=new double[3]; int t1=q1.seekRoot(r);

if(t1==-1) System.out.println(\不是二次方程!\ else if(t1==0) System.out.println(\有虚数根!\ else System.out.println(\有实数根!\

q1.print(); q2.print(); q3.print();

System.out.println(x+\ } }

3

运行结果如下：

D:\\xuxk>javac Quadratic.java

D:\\xuxk>javac Chap1_x2.java

D:\\xuxk>java Chap1_x2 有实数根!

3.0*x**2+5.0*x-2.0 1.0*x**2+6.0*x+5.0 4.0*x**2+11.0*x+3.0

20.0 0.3333333333333333 -2.0

第二章 集合

习题二

2.1 选择题 1. 在一个长度为n的顺序存储的集合中查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度为( C )。

A. n B. n/2 C. (n+1)/2 D. (n-1)/2

2. 在一个长度为n的链接存储的集合中查找值为x的元素时，算法的时间复杂度为( B )。

A. O(1) B. O(n) C. O(n*n) D. O(log2n) 3. 已知一个元素x不属于一个长度为n的顺序或链接存储的集合set中的元素，在插入前若省去顺序查找过程而直接进行插入，则算法的时间复杂度为( A )。 A. O(1) B. O(log2n) C. O(n) D. O(n*n) 4. 从一个长度为n的顺序或链接存储的集合set中删除值为obj的一个元素时，其平均时间复杂度为( C )。

A. O(1) B. O(log2n) C. O(n) D. O(n*n)

5. 从一个长度为n的链接存储的集合S中删除表头结点的时间复杂度为( D )。 A. O(n*n) B. O(log2n) C. O(n) D. O(1)

6. 从顺序存储的集合中删除一个元素时，其空出的位置由（ B ）元素填补。 A. 表头 B. 表尾 C. 前驱 D. 后继

2.2 填空题

1. 向顺序存储的集合中插入元素是把该元素插入到___表尾_____。

2. 向链接存储的集合中插入元素是把该元素的结点插入到__表尾_______。 3. 从顺序存储的集合中删除一个元素时只需要移动___1_____个元素。 4. 求顺序或链接集合长度算法的时间复杂度为____O(n)____。

5. 由集合set1和集合set2的并运算得到的结果集合set，该集合的长度必然___大于等于_____set1和set2中任一个集合的长度。

6. 由集合set1和集合set的交运算得到的结果集合set，该集合的长度必然__小于等于________ set1和set2中任一个集合的长度。

4

7. 设集合set的长度为n，则判断x是否属于集合set的时间复杂度为__________。 8. 设集合set1和集合set2的长度分别为n1和n2，则进行并运算的时间复杂度为__________。

9. 设集合set1和集合set2的长度分别为n1和n2，则进行交运算的时间复杂度为__________。

10. 在集合的链接存储中，表头指针head所指向的结点为__________。

2.3 运算题

1. 假定一个集合S={23,56,12,49,35}采用顺序存储，若按照教材中的相应算法先向它插入元素72，再从中删除元素56，写出运算后得到的集合S。 2. 假定一个集合S={23,56,12,49,35,48}采用顺序存储，若按照教材中的相应算法依次从中删除元素56和23，写出运算后得到的集合S。

3. 假定一个集合S={23,56,12,49,35}采用链接存储，若按照教材中的相应算法插入62和删除23，写出运算后得到的集合S。 4. 假定集合S1={23,56,12,49,35}和集合S2={23,12,60,38}均采用顺序存储，若按照教材中集合并运算的算法对S1和S2进行并运算，写出并运算后的结果集合。 5. 假定集合S1={23,56,12,49,35}和集合S2={23,12,60,38}均采用顺序存储，若按照教材中集合交运算的算法对S1和S2进行交运算，写出交运算后的结果集合。

2.4 算法设计题 1. 修改从顺序存储的集合中删除元素的算法，要求当删除一个元素后检查数组空间的大小，若空间利用率小于40%同时数组长度大于maxSize时则释放数组的一半存储空间。 2. 编写顺序存储集合类sequenceSet中的构造方法，它包含有一维数组参数Object[] a，该方法中给setArray数组分配的长度是a数组长度的1.5倍，并且根据a数组中的所有不同的元素值建立一个集合。 3. 编写一个静态成员方法，返回一个顺序存储的集合set中所有元素的最大值，假定元素类型为Double。 4. 编写顺序存储集合类sequenceSet中的复制构造方法，它包含有一个参数为Set set，实现把set所指向的顺序集合的内容复制到当前集合中的功能。

5. 编写一个静态成员方法，实现两个顺序存储集合的差运算，并返回所求得的差集。 6. 编写一个静态成员方法，实现两个链接存储集合的差运算，并返回所求得的差集。

2.1 选择题

1. C 2. B 3. A 4. C 5. D 6. B 2.2 填空题

1. 表尾 2.表尾 3. 1 4. O(1) 5. 大于等于 6. 小于等于 7. O(n) 8. O(n1*n2) 9. O(n1*n2) 10. 附加头结点 2.3 运算题

1. S={23,72,12,49,35} 2. S={35,48,12,49} 3. S={56,12,49,35,62} 4. {23,56,12,49,35,60,38} 5. {23,12} 2.4 算法设计题

5

本文来源：https://www.bwwdw.com/article/gjxt.html