《数据结构》吕云翔编著第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.va …… 此处隐藏：3138字，全部文档内容请下载后查看。喜欢就下载吧 ……