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

《《数据结构》吕云翔编著第2章线性表习题解答》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构第二章习题解答一、单选题1.在一个长度为n的顺序存储线性表中,向第i个元素(l

2、n-l)/24.在一个长度为n的线性表中,删除值为x的元素时需要比较元素和移动元素的总次数为(C)。A.(n+l)/2B.n/2C.nD.n+15.在一个顺序表的表尾插入一个元素的时间复杂度为(B)。A.0(n)B.0(1)C.0(n*n)D.O(log2n)6.若一个结点的弓

3、用为p，它的前驱结点的引用为q贝I」删除p的后继结点的操作为(B)。A.p=p.next.nextB.p.next=p.next.nextC.q.next=p.nextD.q.next=q.next.next8.假定一个多项式中x的最高次幕为

4、n,则在保存所有系数项的线性表表示中，其线性表长度为(A)。A.n+1B.nC.n-1D.n+2二填空题1.对于当前长度为n的线性表，共包含有多个插入元素的位置，共包含有多个删除元素的位置。(答案n+1n)2.若经常需要对线性表进行表尾插入和删除运算，则最好采用存储结构,若经常需要对线性表进行表头插入和删除运算，则最好采用存储结构。(答案:顺序链式)3.由n个元素生成一个顺序表,若每次都调用插入算法把一个元素插入到表头,则整个算法的时间复杂度为若每次都调用插入算法把一个元素插入到表尾,则整个算法的时间复杂度为。(答案

5、：0(n)0(n))4•由n个元素生成一个单链表,若每次都调用插入算法把一个元素插入到表头,则整个算法的时间复杂度为若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为。(答案：0(1)0(1))5.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为在表尾插入元素的时间复杂度为。(答案：0(n),0(l))6.对于一个单链接存储的线性表，在表头插入结点的时间复杂度为在表尾插入结点的时间复杂度为。(答案：0(1),0(1))7.从一个顺序表和单链表中访问任一个给定位置序号的元素(结点)的时间

6、复杂度分别为和o(答案：0(1),0(n))三、算法设计题1.修改从顺序存储的集合中删除元素的算法，要求当删除一个元素后检查数组空间的大小,若空间利用率小于40%同时数组长度大于maxSize时则释放数组的一半存储空间。publicvoidremove(inti)throwsException{if(i

7、

8、i>curLen-l)thrownewException^'删除位置非法”)；for(intj二i;ivcurLen-l;i++)Iistltem[j]=listltem[j+l];curLeif((doubl

9、e)curLen/maxSize<0.4&&curLen>maxSize){maxSize=maxSize/2;listitem二newObject[maxSize];System.out.println(maxSize);}2.编写顺序存储集合类sequenceSet中的构造方法，它包含有一维数组参数Object]]a,该方法中给setArray数组分配的长度是a数组长度的1.5倍,并且根据a数组中的所有不同的元素值建立一个集合。publicsequenceSet(Object[]a)length=0;setArr

10、ay=newObject[(int)(a.length*1.5)];for(inti=0;i

11、eSetdset=(sequenceSet)set;if(dset.size()==O)returnnull;Doublex=(Double)dset.value(l);for(inti=l;i0)x=y;}r