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

第一章 绪论1.1 单选题1. D 2. C 3. D 4. B 5. A6. B 7. C 8. C 9. A 10. B 第10小题提示：在含有n个元素的数据表中顺序查找任一元素的平均比较次数为，pi为查找第i个元素的概率，ci是查找第i个元素时需要比较的元素数，查找所有元素的概率之和为1，若查找每个元素的概率相同，则平均查找长度的计算公式可简化为。 此题的计算式为=35/12 1.2 算法分析题 1. 判断n是否为一个素数，若是则返回逻辑值true，否则返回逻辑值false。该算法的时间复杂度为O()。 2. 计算的值。时间复杂度为O(n)。 3. 计算的值。时间复杂度为O(n2)。 4. 求出满足不等式1+2+3+.+in的最小i值。时间复杂度为O()。 提示：因为1+2+3+.+i=(1+i)i/2，即当n很大时i的平方与n成正比，所以i的值（即函数中while循环的次数）与n的平方根成正比。 5. 打印出一个具有n行的乘法表，第i行（1in）中有n-i+1个乘法项，每个乘法项为i与j（ijn）的乘积。时间复杂度为O(n2)。 6. 统计并返回二维数组a中大于等于k的元素的个数。时间复杂度为O(mn)，假定m和n分别表示二维数组a的行数和列数。 7. 矩阵相乘，即amnbnpcmp。时间复杂度为O(MNP)。这里假定二维数组a的行列数为m和n，二维数组b的行列数为n和p，二维数组c的行列数为m和p。 1.3 算法设计题 设计二次多项式ax2+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)，以便调用函数能够做不同的处理。当有实数根时，分别用r1和r2保存所得到的两个实数根。 int seekRoot(double r); (5) 按照a*x*2+b*x+c的格式（x2用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) r1=(-b+Math.sqrt(x)/(2*a); r2=(-b-Math.sqrt(x)/(2*a); return 1; /有实数根返回1 else return 0; /有虚数根返回0 public void print() if(a!=0.0) /输出二次项 System.out.print(a+*x*2); if(b!=0.0) /输出一次项 if(b0) System.out.print(+b+*x); else if(b0) System.out.print(+c); else if(cjavac Quadratic.javaD:xuxkjavac Chap1_x2.javaD:xuxkjava Chap1_x2有实数根!3.0*x*2+5.0*x-2.01.0*x*2+6.0*x+5.04.0*x*2+11.0*x+3.020.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中任一个集合的长度。 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 算法设计题1. public boolean remove(Object obj) /从集合删除一个元素 int i; for(i=0; ilength; i+) if(setArrayi.equals(obj) break; /查找成功退出此循环 if(ilength) setArrayi=setArraylength-1; /把集合中最后一个元素赋给被删除元素的位置 length-; int ms=setArray.length; if(double)length/msmaxSize) Object p=new Objectms/2; for(int j=0; jlength; j+) pj=setArrayj; setArray=p; return true; /删除成功返回真 else return false; /删除失败返回假 提示：在原来的删除算法remove中的length-语句的下面增加如下两条语句。 int ms=setArray.length; if(double)length/msmaxSize) Object p=new Objectms/2; for(int j=0; jlength; j+) pj=setArrayj; setArray=p; 2. public sequenceSet(Object a) length=0; setArray=new Object(int)(a.length*1.5); for(int i=0; ia.length; i+) int j; for(j=0; jlength; j+) if(setArrayj.equals(ai) break; if(j=length) setArraylength=ai; length+; 3. public static Object maxValue(Set set) sequenceSet dset=(sequenceSet)set; if(dset.size()=0) return null; Double x=(Double)dset.value(1); for(int i=1; i0) x=y; return x; 4. public sequenceSet(Set set) sequenceSet dset=(sequenceSet)set; setArray=new Objectdset.setArray.length; for(int i=0; idset.length; i+) setArrayi=dset.setArrayi; length=dset.length; 5. public static Set difference(Set set1, Set set2) sequenceSet dset2=(sequenceSet)set2; sequenceSet1 dset3=new sequenceSet(set1); for(int i=0; idset2.size(); i+) dset3.remove(dset2.value(i+1); return dset3; 6. public static Set difference1(Set set1, Set set2) linkSet dset1=(linkSet)set1; linkSet dset2=(linkSet)set2; linkSet dset3=new linkSet(); for(int i=0; idset1.size(); i+) dset3.add(dset1.value(i+1); for(int i=0; idset2.size(); i+) dset3.remove(dset2.value(i+1); return dset3; 第三章 线性表习题三 3.1 单选题 1. 在一个长度为n的顺序存储的线性表中，向第i个元素（1in+1）位置插入一个新元素时，需要从后向前依次后移( B )个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 2. 在一个长度为n的顺序存储的线性表中，删除第i个元素（1in）时，需要从前向后依次前移( A )个元素。 A. n-i B. n-i+1 C. n-i-1 D. i 3. 在一个长度为n的线性表中顺序查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度（即需要比较的元素个数）为( C )。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 4在一个长度为 n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为( C )。 A. (n+1)/2 B. n/2 C. n D. n+1 5. 在一个顺序表的表尾插入一个元素的时间复杂度为( B )。 A. O(n) B. O(1) C. O(n*n) D. O(log2n) 6. 若一个结点的引用为p，在p结点后面插入一个值为x的新结点的操作为( D )。 A. p=new Node(x,p) B. p=new Node(x,p.next) C. p.next=new Node(x,p) D. p.next=new Node(x,p.next) 7. 若一个结点的引用为p，它的前驱结点的引用为q，则删除p的后继结点的操作为( B )。 A. p=p.next.next B. p.next=p.next.next C. q.next=p.next D. q.next=q.next.next 8. 假定一个多项式中x的最高次幂为n，则在保存所有系数项的线性表表示中，其线性表长度为( A )。 A. n+1 B. n C. n-1 D. n+2 3.1 单选题 1. B 2. A 3. C 4. C 5. B 6. D 7. B 8. A 3.2 填空题 1对于当前长度为n的线性表，共包含有_N+1_多个插入元素的位置，共包含有_N_多个删除元素的位置。 2若经常需要对线性表进行表尾插入和删除运算，则最好采用_顺序_存储结构，若经常需要对线性表进行表头插入和删除运算，则最好采用_链式_存储结构。 3由n个元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为_O(N2)_，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为_O(N)_。 4由n个元素生成一个单链表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为_，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为_。 5. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_，在表尾插入元素的时间复杂度为_。 6. 对于一个单链接存储的线性表，在表头插入结点的时间复杂度为_，在表尾插入结点的时间复杂度为_。 7. 在线性表的单链接存储中，若一个元素所在结点的引用为p，结点的类型为Node，则其后继结点的引用为_。 8. 从一个顺序表和单链表中访问任一个给定位置序号的元素（结点）的时间复杂度分别为_和_。 9. 在多项式的线性表表示中，有两种表示方法，对应的线性表中的元素分别包含有_和_个数据项。 10.假定一个稀疏矩阵具有m行、n列和t个非0元素，在对它进行快速转置的算法中，使用了两个整型数组num和pot，其中num的所有元素值之和为_，pot1的值为_。 3.2 填空题 1. n+1、n 2. 顺序、链接 3. O(n2) O(n) 4. O(n) O(n2) 5. O(n) O(1) 6. O(1) O(n) 7. p.next 8. O(1) O(n) 9. 1、2 10. t、1 3.3 写出下面主控程序类Chap3_13中的每个静态成员方法的功能并给出程序运行结果 public class Chap3_13 public static Comparable minimum(sequenceList list) if(list.size()=0) return null; Comparable min=(Comparable)list.value(1); for(int i=2; i=list.size(); i+) Comparable x=(Comparable)list.value(i); if(pareTo(min)0) min=x; return min; 功能：求出并返回顺序存储的list线性表中所有元素的最小值。 public static void separate(sequenceList list, Comparable com) int n=list.size(); if(n=0 | n=1) return; int i=1, j=n; while(i=j) while(i=j) & (Comparable)list.value(i).compareTo(com)0) i+; while(i=0) j-; if(ij) Comparable x=(Comparable)list.value(i); list.modify(list.value(j), i); list.modify(x, j); i+; j-; 功能：重新调整顺序存储的线性表list中元素值的排列次序，使得前面的元素都小于参数com的值，后面的元素都大于等于参数com的值。调整的方法是分别从两头向中间扫描，若碰到需要调整的元素就交换位置。 static void insertTail(sequenceList list, Object a) for(int i=0; ia.length; i+) list.add(ai, list.size()+1); 功能：向顺序存储的线性表list的表尾依次插入数组a中的每个元素。 static void insertTop(sequenceList list, Object a) for(int i=0; ia.length; i+) list.add(ai, 1); 功能：向顺序存储的线性表list的表头依次插入数组a中的每个元素。 public static void main(String args) sequenceList std=new sequenceList(); int r=15,9,20,14,15,8,12; int i; for(i=0; ijavac Chap3_13.java D:xuxkjava Chap3_13 15 9 20 14 15 8 12 x=8 12 9 8 14 15 20 15 7 15 10 2 12 9 8 14 15 20 15 13 18 5 6 长度：15 3.4 写出下面主控程序类Chap3_14中的每个静态成员方法的功能并给出程序运行结果 public class Chap3_14 public static Comparable minimum(linkList list) if(list.size()=0) return null; Node p=list.prior(), q=p.next; Comparable min=(Comparable)q.element; while(q.next!=p) q=q.next; Comparable x=(Comparable)q.element; if(pareTo(min)0) min=x; return min; 功能：求出并返回链接存储的list线性表中所有元素的最小值。 public static void separate(linkList list, Comparable com) int n=list.size(); if(n=0 | n=1) return; Node p=list.prior(), head=p; while(p.next!=head) p=p.next; Node r=head, s=head.next; for(int i=1; i=n; i+) if(Comparable)s.element).compareTo(com)0) r=s; s=s.next; else r.next=s.next; s.next=p.next; p=p.next=s; s=r.next; 功能：重新调整链接存储的线性表list中结点的链接次序，使得前面结点的值都小于参数com的值，后面结点的值都大于等于参数com的值。调整的方法是从表头顺序向后扫描，若碰到需要调整的结点则把它摘除并插入到表尾。 static void insertTail(linkList list, Object a) Node p=list.prior(), head=p; while(p.next!=head) p=p.next; for(int i=0; ia.length; i+) p=p.next=new Node(ai, p.next); list.setSize(list.size()+a.length); 功能：向链接存储的线性表list的表尾依次插入数组a中的每个元素。 static void insertTop(linkList list, Object a) Node p=list.prior(); for(int i=0; ia.length; i+) p.next=new Node(ai, p.next); list.setSize(list.size()+a.length); 功能：向链接存储的线性表list的表头依次插入数组a中的每个元素。 public static void main(String args) linkList std=new linkList(); int r=15,9,20,14,15,8,12; int i; for(i=0; i=0; i-) std.add(ri,1); /运行时间较少 std.nextOrder(); System.out.println(); int x=(Integer)minimum(std); System.out.println(x=+x); System.out.println(); separate(std,15); std.nextOrder(); System.out.println(); Integer a1=13,18,5,6; Integer a2=2,10,15,7; insertTail(std, a1); insertTop(std, a2); std.nextOrder(); System.out.println(长度：+std.size(); 程序运行结果如下： D:xuxkjavac Chap3_14.java D:xuxkjava Chap3_14 15 9 20 14 15 8 12 x=8 9 14 8 12 15 20 15 7 15 10 2 9 14 8 12 15 20 15 13 18 5 6 长度：15 3.5 使用顺序存储的线性表类sequenceList的编程练习在一个任意设定的类中，不妨设定的类名为seqListExtend，按照下列每小题的要求和方法声明编写出相应的方法。 1根据数组a中的所有元素建立并返回一个顺序存储的线性表。 public static sequenceList create(Object a); public static sequenceList create(Object a) /根据数组a中的所有元素建立并返回一个线性表 sequenceList s=new sequenceList(); /定义和创建一个空表 for(int i=0; ia.length; i+) /依次向表尾插入元素 s.add(ai,i+1); return s; /返回所建立的线性表