数据结构第二章习题解答
一、单选题 
    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. ext             B.&=   
 C.&=p.next                D.&= 
8. 假定一个多项式中x的最高次幂为n，则在保存所有系数项的线性表表示中，其线性 
表长度为(A )。 
A. n+1     B. n     C. n-1    D. n+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{
        if(i<0||i>curLen-1)
            throw new Exception("删除位置非法");
        for(int j=i;i<curLen-1;i++)
            listItem[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;
                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(ypareTo(x)>0) x=y;
            }
            return x;
        }
4. 编写顺序存储集合类sequenceSet中的复制构造方法，它包含有一个参数为Set set，实现把set所指向的顺序集合的内容复制到当前集合中的功能。
        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++) ve(dset2.value(i+1));

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。