顺序表的C语言实现、插入、删除、查找的有关习题

一、单项选择题

1.下述哪一条是顺序存储结构的优点（ ）。
A .存储密度大     B.插入运算方便
C.删除运算方便     D.方便地运用于各种逻辑结构的存储表示

2.线性表的顺序存储结构是一种（ ）。
A.随机存取的存储结构     B.顺序存取的存储结构
C.索引存取的存储结构     D.散列存取的存储结构

3. —个顺序表所占用的存储空间大小与（ ）无关。
A.表的长度     B.元素的存放顺序
C.元素的类型     D.元素中各字段的类型

4.若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为了提高效率，应用（ ）的存储方式。
A.单链表     B.双向链表     C.单循环链表     D.顺序表

5.一个线性表最常用的操作是存取任一指定序号的兀素和在最后迸行插入删除操作，则利用（ ）存储方式可以节省时间。
A.顺序表    B.双链表       C.带头结点的双循环链表    D.单循环链表

6.在n个元素的线性表的数组表示中，以下时间复杂度为O(1)的操作是（    ）。
Ⅰ.访问第i个结点(1<=i<=n)和求第i个结点的直接前驱(2<=i<=n)
Ⅱ.在最后一个结点后插入一个新的结点
Ⅲ.删除第1个结点
Ⅳ.在第i个结点后插入一个结点(1<=i<=n)
A.Ⅰ      B. Ⅱ、Ⅲ      C. Ⅰ、Ⅱ      D. Ⅰ、Ⅱ、Ⅲ

7.设线性表有n个元素，严格说来，以下操作中，（    ）在顺序表上实现要比链表上实现的效率高。
Ⅰ. 输出第i(1<=i<=n)个元素值
Ⅱ.交换第3个元素与第4个元素的值
Ⅲ.顺序输出这n个元素的值
A.Ⅰ    B. Ⅰ、Ⅲ     C. Ⅰ、Ⅱ     D. Ⅱ、Ⅲ

8.在一个长度为n的顺序表中删除第i个元素(1<=i<=n)时，需向前移动（）个元素。
A. n    B. i-l    C. n-i    D. n-i+1

9.对于顺序表，访问第i个位置的元素和在第i个位置插入一个元素的时间复杂度为（）。
A. O(n), O(n)     B. O(n), O(1)     C. O(1), O(n)      D. O(1), O(1)

10.若长度为n的非空线性表用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是（ ）
A. 1<=i<=n     B. 1<=i<=n+l     C. 0<=i<=n-1     D. 0<=i<=n

二、综合应用题

1.从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。

2.设计一个高效的算法，将顺序表的所有元素逆置，要求算法的空间复杂度为O(1)。

3.长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。

4.从有序顺序表中删除其值在给定值s与t之间（要求s<t）的所有元素，如果s或t 不合理或者顺序表为空则显示出错信息并退出运行。

5.从顺序表中删除其值在给定值s与t之间（包含s和t，要求s<t）的所有元素，如果 s或t不合理或者顺序表为空则显示出错信息并退出运行。

6.从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。

7.将两个有序顺序表合并成一个新的有序顺序表，并由函数返回结果顺序表。

8.已知在一维数组A[m+n]中依次存放着两个线性表 (a₁, a₂, a₃, …, a_m) 和(b₁, b₂, b₃, …, b_n)。试编写一个函数，将数组中两个顺序表的位置互换，即将 (b₁, b₂, b₃, …, b_n) 放在 (a₁, a₂, a₃, ..., a_m) 的前面。

9.线性表(a₁, a₂, a₃, …, a_n)中元素递增有序且按顺序存储于计算机内。要求设计一算法完成用最少时间在表中查找数值为x的元素，若找到将其与后继元素位置相交换，若找不到将其插入表中并使表中元素仍递增有序。

10.【2010年计算机联考真题】设将n (n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p (0<p<n)个位置，即将R中的数据由 (X₀, X₁,…, X_n-1)变换为(X_p, X_p+1,…, X_n-1, X₀, X₁, …, X_p-1)。要求：
1) 给出算法的基本设计思想。
2) 根据设计思想，用C或C++或Java语言描述算法，关键之处给出注释。
3) 说明你所设计算法的时间复杂度和空间复杂度。

11.【2011年计算机联考真题】一个长度为L (L>=1)的升序序列S，处在第[L/2]个位置的数称为S的中位数。例如，若序列S1=(11, 13, 15, 17, 19)，则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2= (2, 4，6，8, 20)，则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：
1) 给出算法的基本设计思想。
2) 根据设计思想，用C或C++或Java语言描述算法，关键之处给出注释。
3) 说明你所设计算法的时间复杂度和空间复杂度。

答案与解析

一、单项选择题

1.    A
顺序表不像链表要在结点中存放指针域，因此存储密度较大，A正确。B和C是链表的优点。D是错误的，比如对于树形结构，顺序表显然不如链表表示起来方便。

2.    A
本题容易误选B。顺序表是一种支持随机存取的顺序存储结构，根据起始地址加上元素的序号，可以很方便地访问到任一元素，即随机存取的概念。注意，顺序存取是一种读写方式，不是存储方式，有别于顺序存储。

3.    B
顺序表所占存储空间的大小=表长*sizeof (元素的类型)，元素的类型显然会影响到存储空间的大小。对于同一类型的顺序表，表越长，则所占存储空间就越大。

4.    D
题干实际要求能够最快存取第i-1、i和i+1个元素值。A、B、C都只能从头结点依次顺序查找，时间复杂度为O(n)，只有顺序表可以随机存取，时间复杂度为O(1)。

5.    A
只有顺序表具有随机存取的优点，且在最后进行插入和删除操作不需要移动任何元素。

6.    C
Ⅰ中，时间复杂度显然为O(1)；Ⅱ中，在最后一个结点插入一个新结点不需要移动元素，故也为O(1)；Ⅲ中，第一个结点后的结点需要依次前移，时间复杂度为O(n)；Ⅳ中，需要移动n-i个结点，时间复杂度为O(n)。

7.    C
顺序输出这n个元素的值，都要依次访问每个元素，故时间复杂度相同。

8.    C
需要将a_i+1~a_n元素前移一位，共移动n-(i+1)+1=n-i个元素。

9.    C
顺序表中，第i个元素的物理地址可以通过起始地址和序号直接计算出，即可在O(1) 时间内访问。在第i个位置插入一个元素，需要移动n-i+1个元素，时间复杂度为O(n)。

10.    B
表元素序号从1开始，而在第n+1个位置插入相当于在表尾追加。

二、综合应用题

1.解答：

算法思想：搜索整+顺序表，查找最小值元素并记住其位置，搜索结束后用最后-个元素填补空出的原最小值元素位置。本题代码如下：

bool Del_Min(sqList &L,ElemType &value){
    //删除顺序表L中最小值元素结点，并通过引用型参数value返回其值
    //如果删除成功，返回true；否则，返回false
    if (L.length==0)
        return false;  //表空，中止操作返回
    value=L.data[0];
    int pos=0;  //假定0号元素的值最小
    for (int i=1; i<L.length; i++)    //循环，寻找具有最小值的元素
        if (L.data[i]<value) {  //让value记忆当前具有最小值的兀素
            value=L.data[i];
            pos=i;
        }
    L.data[pos] = L.data[L.length-1];  //空出的位置由最后一个元素填补
    L.length--;
    return true;     //此时，value即为最小值
}

注意：本题也可以用函数返回值返回，两者的区别是：函数返回值只能返回一个值，而参数返回（引用传参）则可以返回多个值。

2.解答：

算法思想：扫描顺序表L的前半部分元素，对于元素L.data[i] (0<=i<L.lengh/2),将其余后半部分对应元素L.data[L.length-i-1]进行交换。本题代码如下：

void Reverse(Sqlist &L){
    Elemtype temp;  //辅助变量
    for(i=0;i<L.length/2;i++){
        temp=L.data[i];  //交换 L.data[i]与 L.data[L.length-i-1]
        L.data[i]=L.data[L.length-i-1];
        L.data[L.length-i-1]=temp;
    }
}

3.解答：

解法一：用k记录顺序表L中不等于x的元素个数（即需要保存的元素个数)，边扫描 L边统计k，并将不等于x的元素向前放置k位置上，最后修改L的长度。本题代码如下：

void del_x_1(Sqlist &L, Elemtype x){
    //本算法实现删除顺序表L中所有值为x的数据元素
    int k=0;  //记录值不等于x的元素个数
    for(i=0; i<L.length; i++)
        if(L.data[i] != x){
            L.data[k] = data[i];
            k++;  //不等于x的元素增1
        }
    L.length=k;  //顺序表L的长度等于k
}

解法二：用k记录顺序表L中等于X的元素个数，边扫描L边统计k，并将不等于X的元素前移k个位置，最后修改L的长度。本题代码如下：   

void del_x_2(Sqlist &L,Elemtype x){
    int k=0,i=0;  //k记录值等于x的元素个数
    while(i<L.length){
        if (L.data[i]==x)
            k++;
        else
            L.data [i-k]=L.data [i];  //当前元素前移k个位置
        i++;
    }
    L.length=L.length-k;  //顺序表L的长度递减
}

此外，本题还可以考虑设头、尾两个指针（i=l, j=n)，从两端向中间移动，凡遇到最左端值X的元素时，直接将最右端值非X的元素左移至值为X的数据元素位置，直到两指针相遇。但这种方法会改变原表中元素的相对位置。

4.解答：

注意本题与上一题的区别，因为是有序表，所以删除的元素必然是相连的整体。

算法思想：先寻找值大于等于s的第一个元素（第一个删除的元素)，然后寻找值>t 的第一个元素（最后一个删除的元素的下一个元素)，要将这段元素删除，则只需直接将后面的元素前移即可。本题代码如下：

bool Del_s_t2(sqList &L, ElemType s, ElemType t){
    //删除有序顺序表L中值在给定值s与t之间的所有元素
    int i,j;
    if(s>=t) || L.length==0)
        return false;
    for (i=0; i<L.length && L.data[i] <s; i++) ;    //寻找值>=s 的第一个元素
    if(i>=L.length)
        return false;  //所有元素值均小于s，则返回
    for(j=i; j<L.length && L.data[j] <=t; j++) ;    //寻找值>t 的第一个元素
    for(;j<L.length;i++, j++)
        L.data[i]=L.data[j];  //前移，填补被删元素位置
    L.length=i;
    return true;
}

5.解答：

算法思想：从前向后扫描顺序表L，用k记录下元素值在s到t之间元素的个数（初始时k=0）。对于当前扫描的元素，若其值不在s到t之间，则前移k个位置；否则，删除该元素，并执行k++。由于这样每个不在s到t之间的元素仅移动一次，所以算法效率高。本题代码如下：

bool Del_s_t (sqList &Lf ElemType s, ElemType t) {
    //删除顺序表L中值在给定值s与t之间（要求s<t）的所有元素
    int i,k=0;
    if (L.length==0 || s>=t)
        return false;  //线性表为空或s、t不合法，返回
    for(i=0;i<L.length;i++){
        if (L.data[i] >= s && L.data[i] <= t)
            k++;
        else
            L.data [i-k] = L.data[i];  //当前元素前移 k 个置
    } //for
    L.length-=k;  // 长度减小
    return true;
}

注意：本题也可以从后向前扫描顺序表，每遇到一个值在S到t之间的元素，则删除该元素，其后的所有元素全部前移。但移动次数远大于前者，效率不够高。

6.解答：

算法思想：注意是有序顺序表，值相同的元素一定在连续的位置上，用类似于直接插入排序的思想，初始时将第一个元素看做是非重复的有序表。之后顺序依次判断后面的元素是否与前面非重复有序表的最后一个元素相同，如果相同则继续向后判断，如果不同则插入到前面的非重复有序表的最后，直至判断到整个表尾为止。本题代码如下：

bool Delete_Same(SeqList & L){
    if(L.length==0)
        return false;
    int i,j;  //i存储第一个不相同的元素，j工作指针
    for(i=0,j=1; j<L.length; j++)
        if(L.data[i] < L.data[j])  //查找下一个与上个元素值不同的元素
    L.data[++i] = L.data[j];  //找到后，则将元素前移
    L.length = i+1;
}

对于本题的算法，请读者以序列1，2，2，2，2，3，3，3，4，4，5来手动模拟算法的执行过程，在模拟的过程中要标注i和j所指示的元素。

7.解答：

算法思想：首先，按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后，看哪个表还有剩余，将剩下的部分加到新的顺序表后面。本题代码如下：

bool Merge(SeqList A, SeqList B, SeqList &C){
    //合并有序顺序表A与B成为一个新的有序顺序表C
    if(A.length+B.length>C.maxSize)  //大于顺序表的最大长度
        return false;
    int i=0,j=0,k=0;
    while(i<A.length && j<B.length){
        //循环，两两比较，小者存入结果表
        if(A.data[i] < B.data[j])
            C.data[k++] = A.data[i++];
        else
            C.data[k++]=B.data[j++];
    }
    while(i<A.length)  //还剩一个没有比较完的顺序表
        C.data[k++] =A.data[i++];
    while(j<B.length)
        C.data[k++] = B.data[j++];
    C.length=k;
    return true;
}

注，本算法的方法非常典型，需牢固掌握。

8.解答：

算法思想：首先将数组A[m+n]中的全部元素 (a₁, a₂, a₃, …, a_m, b_i, b₂, b₃, …, b_n) 原地逆置为 (b_n, b_n-1, b_n-2, …, b₁, a_m, a_m-1, a_m-2, …, a₁)，再对前n个元素和后m个元素分别使用逆置算法，就可以得到(b₁, b₂, b₃, …, b_n, a₁, a₂, a₃, …, a_m)，从而实现顺序表的位置互换。本题代码如下：

typedef int DataType;
void Reverse(DataType A[], int left, int right, int arraySize){
    //逆转（aleft, aleft+1, aleft+2,..., aright)为（aright, aright-1, ..., aleft)
    if(left>=right || right>=arraySize)  return;
    int mid== (left+right)/2;
    for(int i=0; i<mid-left; i++) {
        Datatype temp=A[left+i];
        A[left+i]=A[right-i];
        A[right-i]=temp;
    }
}
void Exchange(DataType A[],int m,int n,int arraySize){
    // 数组A[m+n]中，从0到m-1存放顺序表(a1, a2, a3, …, am)
    // 从m到m+n-1存放顺序表 (b1, b2, b3, ..., bn )，算法将这两个表的位置互换
    Reverse(A, 0, m+n-1, arraySize);
    Reverse(A, 0, n-1, arraySize);
    Reverse(A, n, m+n-1, arraySize);
}

9.解答：

算法思想：顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找法。本题代码如下：

void SearchExchangeInsert(ElemType A[], ElemType x){
    int low=0, high=n-1;  //low和high指向顺序表下界和上界的下标
    while(low<=high){
        mid = (low+high)/2;  //找中间位置
        if(A[mid]==x) break;  //找到 x，退出 while 循环
        else if (A[mid]<x) low = mid+1;  //到中点 mid 的右半部去查
        else high=mid-1;  //到中点mid的左半部去查
    } //下面两个if语句只会执行一个   
    if(A[mid] == x && mid != n-1) {  //若最后一个元素与x相等，则不存在与其后继交换的操作   
        t=A[mid]; A[mid]=A[mid+1]; A[mid+1]=t;
    }
    if(low>high) {  //查找失败，插入数据元素x
        for(i=n-1; i>high; i--) A[i+l]=A[i] ;  //后移元素
            A[i+1]=x;  //插入 x
    }  //结束插入
}

本题的算法也可以写成三个函数：查找函数、交换后继函数与插入函数。写成三个函数的优点是逻辑清晰、易读。

10.解答：

(1)算法的基本设计思想：可以将这个问题看做是把数组ab转换成数组ba (a代表数组的前p个元素，b代表数组中余下的n-p个元素），先将a逆置得到a^-1b，再将b逆置得到a^-1b^-1，最后将整个a^-1b^-1逆置得到(a^-1b^-1)^-1=ba。设Reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3 (p=3)个位置的过程如下：

• Reverse(0, p-1)得到 cbadefgh;
• Reverse(p, n-1)得到 cbahgfed;
• Reverse(0, n-1)得到 defghabc;

注：Reverse中，两个参数分别表示数组中待转换元素的始末位置。

(2)使用C语言描述算法如下：

void Reverse(int R[], int from, int to) {
   int i, temp;
    for(i=0; i<(to-from+1)/2; i++){
        temp=R[from+i];
        R[from+i]=R[to-i];
        R[to-i]=temp;
    }
}  //Reverse
void Converse(int R[],int n,int p){
    Reverse(R,0,p-1);
    Reverse(R,p,n-1);
    Reverse(R,0,n-1);
}

(3)上述算法中三个Reverse函数的时间复杂度分别为O(p/2)、O((n-p)/2)和O(n/2)，故所设计的算法的时间复杂度为O(n)，空间复杂度为O(1)。

另解，借助辅助数组来实现：

算法思想：创建大小为p的辅助数组S，将R中前p个整数依次暂存在S中，同时将R 中后n-p个整数左移，然后将S中暂存的p个数依次放回到R中的后续单元。

时间复杂度为O(h)，空间复杂度为O(p)。

11.解答：

(1)算法的基本设计思想如下：

分别求两个升序序列A、B的中位数，设为a和b,求序列A、B的中位数过程如下：

1) 若a=b，则a或b即为所求中位数，算法结束。

2) 若a<b，则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求两次舍弃的长度相等。

3) 若a>b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求两次舍弃的长度相等。

在保留的两个升序序列中，重复过程1)、2)、3)，直到两个序列中均只含一个元素时为止，较小者即为所求的中位数。

(2)本题代码如下：

int M_Search(int A[], int B[],int n) {
    int s1=0, d1=n-1, ml, s2=0, d2=n-1, m2;
    //分别表示序列A和B的首位数、末位数和中位数
    while(s1!=d1 || s2!=d2){
        m1=(s1+d1)/2;
        m2=(s2+d2)/2;
        if(A[m1]==B[m2])
            return A[m1];  //满足条件 1)
        if(A[m1]<B[m2]){  // 满足条件 2)
            if((s1+d1)%2==0) {  //若元素个数为奇数
                s1=m1;  //舍弃A中间点以前的部分且保留中间点
                d2=m2;  //舍弃B中间点以后的部分且保留中间点
            }else{  //元素个数为偶数
                s1=m1+1;  //舍弃A中间点及中间点以前部分
                d2=m2;  //舍弃B中间点以后部分且保留中间点
            }
        }else{  //满足条件3)
            if((s2+d2)%2==0){  //若元素个数为奇数
                d1=m1;    //舍弃A中间点以后的部分且保留中间点
                s2-m2;    //舍弃B中间点以前的部分且保留中间点
            }else {  //元素个数为偶数
                d1=m1;    //舍弃A中间点以后部分且保留中间点
                s2=m2 + 1;    //舍弃B中间点及中间点以前部分
            }
        }
    }
    rerurn A[s1]<B[s2]?A[s1]:B[s2];
}

(3)算法的时间复杂度为O(log₂n)，空间复杂度为O(1)。