《数据结构》吕云翔编著第2章线性表习题解答

1、数据结构第二章习题解答一、单选题1在一个长度为n的顺序存储线性表中，向第i个元素(1in+1)之前插入一个新元素时，需要从后向前依次后移（B）个元素。A、n-iB、n-i+1C、n-i-1D、i2在一个长度为n的顺序存储线性表中，删除第i个元素(1in+1)时，需要从前向后依次前移（A）个元素。A、n-iB、n-i+1C、n-i-1D、i3. 在一个长度为n的线性表中顺序查找值为x的元素时，在等概率情况下，查找成功时 的平均查找长度（即需要比较的元素个数）为( C )。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 4在一个长度为 n的线性表中，删除值为x的元素时需要比较

2、元素和移动元素的总次 数为(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，它的前驱结点的引用为q，则删除p的后继结点的操作为(B)。A.p=p.next.nextB.p.next=p.next.nextC.q.next=p.nextD.q.next=q.next.next8. 假定一个多项式中x的最高次幂为n，则在保存所有系数项的线性表表示中，其线性表长度为(A )。 A. n+1 B. n C. n-1 D

3、. n+2二、填空题1对于当前长度为n的线性表，共包含有_多个插入元素的位置，共包含有_多个删除元素的位置。（答案n+1 n）2若经常需要对线性表进行表尾插入和删除运算，则最好采用_存储结构，若经常需要对线性表进行表头插入和删除运算，则最好采用_存储结构。（答案：顺序 链式）3由n个元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为_，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为_。（答案： O（n） O（n）4由n个元素生成一个单链表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为_，若每次都调用插入算法把一个元素

4、插入到表尾，则整个算法的时间复杂度为_。（答案： O（1） O（1）5. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_，在表尾插入元素的时间复杂度为_。（答案：O（n），O（1）6. 对于一个单链接存储的线性表，在表头插入结点的时间复杂度为_，在表尾插入结点的时间复杂度为_。（答案：O（1），O（1）7. 从一个顺序表和单链表中访问任一个给定位置序号的元素（结点）的时间复杂度分别为_和_。（答案：O（1），O（n）三、 算法设计题1. 修改从顺序存储的集合中删除元素的算法，要求当删除一个元素后检查数组空间的大小，若空间利用率小于40%同时数组长度大于maxSize时则释放

5、数组的一半存储空间。public void remove(int i) throws Exceptionif(icurLen-1)throw new Exception(删除位置非法);for(int j=i;icurLen-1;i+)listItemj=listItemj+1;curLen-;if(double)curLen/maxSizemaxSize) maxSize=maxSize/2;listItem=new ObjectmaxSize; System.out.println(maxSize);2. 编写顺序存储集合类sequenceSet中的构造方法，它包含有一维数组参数Objec

6、t a，该方法中给setArray数组分配的长度是a数组长度的1.5倍，并且根据a数组中的所有不同的元素值建立一个集合。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. 编写一个静态成员方法，返回一个顺序存储的集合set中所有元

7、素的最大值，假定元素类型为Double。 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. 编写顺序存储集合类sequenceSet中的复制构造方法，它包含有一个参数为Set set，实现把set所指向的顺序集合的内容复制到当前集合中的功能。 public sequenceSet(Set set) seq

8、uenceSet 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 s

9、equenceSet(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();

10、i+) dset3.add(dset1.value(i+1); for(int i=0; idset2.size(); i+) dset3.remove(dset2.value(i+1); return dset3; 7. 编写一个带有主函数的程序，其中包含两个静态成员方法，分别为使用顺序和链接存储的线性表解决约瑟夫（Josephus）问题。约瑟夫的问题是：设有n个人围坐在一张圆桌周围，现从某个人开始从1报数，数到m的人出列（即离开坐位，不参加以后的报数），接着从出列的下一个人开始重新从1报数，数到m的人又出列，如此下去直到所有人都出列为止，试求出这n个人的出列次序。 例如，当n=8,m=4时

11、，若从第一个人开始报数，假定n个人对应的编号依次为1、2、n，则得到的出列次序为：4,8,5,2,1,3,7,6。 在每个解决约瑟夫问题的静态成员方法中，要求以整型对象n、m和s作为参数，n表示开始参加报数的人数，m为下一次要出列的人所报出的数字序号，s为最开始报数的那个人的编号。 注意：人的座位是首位相接的，所以报数是循环进行的，最后一个人报数后，接着是最前面的一个人报数。 参考程序如下： public class Chap3_15 static void seqJosephus(int n, int m, int s) /使用顺序表解决约琵夫问题的算法，n为人数，每次报数到m出列 if(n

12、=0 | m=0 | s=0) System.out.println(参数值不合法，退出运行！); System.exit(1); sequenceList a=new sequenceList(n); /定义和创建一个线性表a int i,k; for(i=1; i=n; i+) a.add(i,i); /插入n个元素，元素值依次为1n k=s; /给k赋初值为s,开始从编号为s的人起报数 for(i=1; in; i+) /循环n-1次，每次使一个人出列 k=(k+m-1)%a.size(); /计算出待出列的元素序号 if(k=0) k=a.size(); /若k的值为0则应修改为表尾的

13、序号 System.out.print(a.value(k)+, ); /输出序号为k的元素值 a.remove(k); /从线性表中删除序号为k的元素 System.out.println(a.value(1); /输出最后剩余的一个元素的值 static void linkJosephus(int n, int m, int s) /使用链表解决约琵夫问题的算法，n为人数 if(n=0 | m=0 | s=1; i-) a.add(i,1); /插入n个结点，结点值依次为1n Node p=a.prior(), q=p.next, head=p; /q指向表头结点，p为前驱 k=1; /给k赋初值1 while(ks) /循环结束后q结点为第s个结点 p=q; q=q.next; if(q=head) p=q; q=q.next;/若q为附加表头结点，则移到表头 k+; for(i=1; in; i+) /循环n-1次，每次从1报数到m k=1; while(km) /每次循环结束，q指向要出列的结点 p=q; q=q.next; if(q=head) p=q; q=q.next;/使指针跳过表头附加结点 k+; System.out.print(q.element+, ); /输出q结点的值 p.next