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

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

数据结构第二章习题解答

一、单选题

1．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移（B）个元素。

A、n-i

B、n-i+1

C、n-i-1

D、i

2．在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移（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，它的前驱结点的引用为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

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

二、填空题

1．对于当前长度为n的线性表，共包含有________多个插入元素的位置，共包含有________多个删除元素的位置。（答案n+1 n）

2．若经常需要对线性表进行表尾插入和删除运算，则最好采用________存储结构，若经

常需要对线性表进行表头插入和删除运算，则最好采用________存储结构。（答案：顺序链式）

3．由n个元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为________，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为________。（答案：O（n）O（n））

4．由n个元素生成一个单链表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为________，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为________。（答案：O（1）O（1））

5. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为________，

在表尾插入元素的时间复杂度为________。（答案：O（n），O（1））

6. 对于一个单链接存储的线性表，在表头插入结点的时间复杂度为________，在表尾插

入结点的时间复杂度为________。（答案：O（1），O（1））

7. 从一个顺序表和单链表中访问任一个给定位置序号的元素（结点）的时间复杂度分别

为________和_______。（答案：O（1），O（n））

三、算法设计题

1. 修改从顺序存储的集合中删除元素的算法，要求当删除一个元素后检查数组空间的大小，若空间利用率小于40%同时数组长度大于maxSize时则释放数组的一半存储空间。public void remove(int i) throws Exception{

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

if(i<0||i>curLen-1)

throw new Exception("删除位置非法");

for(int j=i;i<curLen-1;i++)

l istItem[j]=listItem[j+1];

curLen--;

if((double)curLen/maxSize<0.4 && curLen>maxSize) {

maxSize=maxSize/2;

listItem=new Object[maxSize];

System.out.println(maxSize);

}

}

2. 编写顺序存储集合类sequenceSet中的构造方法，它包含有一维数组参数Object[] a，该方法中给setArray数组分配的长度是a数组长度的1.5倍，并且根据a数组中的所有不同的元素值建立一个集合。

public sequenceSet(Object[] a)

{

length=0;

setArray=new Object[(int)(a.length*1.5)];

for(int i=0; i<a.length; i++) {

int j;

for(j=0; j<length; j++)

if(setArray[j].equals(a[i])) break;

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

if(j==length) {

setArray[length]=a[i];

length++;

}

}

}

3. 编写一个静态成员方法，返回一个顺序存储的集合set中所有元素的最大值，假定元素类型为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; i<dset.size(); i++) {

Double y=(Double)dset.value(i+1);

if(http://pareTo(x)>0) x=y;

}

return x;

}

4. 编写顺序存储集合类sequenceSet中的复制构造方法，它包含有一个参数为Set set，实现把set所指向的顺序集合的内容复制到当前集合中的功能。

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

public sequenceSet(Set set)

{

sequenceSet dset=(sequenceSet)set;

setArray=new Object[dset.setArray.length];

for(int i=0; i<dset.length; i++)

setArray[i]=dset.setArray[i];

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; i<dset2.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();

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

for(int i=0; i<dset1.size(); i++) dset3.add(dset1.value(i+1));

for(int i=0; i<dset2.size(); i++) dset3.remove(dset2.value(i+1));

return dset3;

}

7. 编写一个带有主函数的程序，其中包含两个静态成员方法，分别为使用顺序和链接存储的线性表解决约瑟夫（Josephus）问题。约瑟夫的问题是：设有n个人围坐在一张圆桌周围，现从某个人开始从1报数，数到m的人出列（即离开坐位，不参加以后的报数），接着从出列的下一个人开始重新从1报数，数到m的人又出列，如此下去直到所有人都出列为止，试求出这n个人的出列次序。

例如，当n=8,m=4时，若从第一个人开始报数，假定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出列

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

if(n<=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个元素，元素值依次为1~n

k=s; //给k赋初值为s,开始从编号为s的人起报数for(i=1; i<n; i++) { //循环n-1次，每次使一个人出列k=(k+m-1)%a.size(); //计算出待出列的元素序号

if(k==0) k=a.size(); //若k的值为0则应修改为表尾的序号

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<=0) {

System.out.println("参数值不合法，退出运行！");

System.exit(1);

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

}

linkList a=new linkList(); //定义和创建一个空的线性链表a int i,k;

for(i=n; i>=1; i--) a.add(i,1); //插入n个结点，结点值依次为1~n Node p=a.prior(), q=p.next, head=p; //q指向表头结点，p为前驱

k=1; //给k赋初值1

while(k<s) { //循环结束后q结点为第s个结点p=q; q=q.next;

if(q==head) {p=q; q=q.next;}//若q为附加表头结点，则移到表头k++;

}

for(i=1; i<n; i++) { //循环n-1次，每次从1报数到m k=1;

while(k<m) { //每次循环结束，q指向要出列的结点p=q; q=q.next;

if(q==head) {p=q; q=q.next;}//使指针跳过表头附加结点

k++;

}

System.out.print(q.element+", "); //输出q结点的值

p.next=q.next; //从链表中删除q结点

if(p.next==head) { //使指针跳过表头附加结点

p=head; q=head.next;

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

}

else q=p.next; //修改q的值，将从q结点重新报数}

System.out.println(q.element);//最后一个人出列

}

public static void main(String[] args)

{

linkJosephus(8,4,1);

seqJosephus(8,4,1);

}

}