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

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

1、数据结构第二章习题解答一、单选题     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.在一

2、个长度为n的线性表中顺序查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度（即需要比较的元素个数）为(C)。A.nB.n/2C.(n+1)/2D.(n-1)/24．在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为(C)。A.(n+1)/2B.n/2C.nD.n+15.在一个顺序表的表尾插入一个元素的时间复杂度为(B)。A.O(n)B.O(1)C.O(n*n)D.O(log2n)6.若一个结点的引用为p，它的前驱结点的引用为q，则删除p的后继结点的操作为(B  )。    

3、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+1B.nC.n-1D.n+2 二、填空题 1．对于当前长度为n的线性表，共包含有________多个插入元素的位置，共包含有 ________多个删除元素的位置。（答案n+1n） 2．若经常需

4、要对线性表进行表尾插入和删除运算，则最好采用________存储结构，若经 常需要对线性表进行表头插入和删除运算，则最好采用________存储结构。 （答案：顺序链式）3．由n个元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个 算法的时间复杂度为________，若每次都调用插入算法把一个元素插入到表尾，则整个算法 的时间复杂度为________。 （答案：O（n）O（n））4．由n个元素生成一个单链表，若每次都调用插入算法把一个元素插入到表头，则整个 算法的时间复杂度为________

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

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

7、

8、i>curLen-1)thrownewException("删除位置非法");for(intj=i;i

9、1];curLen--;if((double)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

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