01.

①从顺序表中删除具有最小值的元素（假设唯一），并由函数返回被删元素的值。

②空出的位置由最后一个元素填补。

③若顺序表为空，则显示出错信息并退出运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Q1(SqList &L){
    if(L.length==0){ //
        return -1; //  ③ （返回 -1 表示出错) //
    } //
    int last = L.data[L.length-1]; //
    int min = L.data[0];
    int j = 0; //
    for(int i=1;i<L.length;i++) // ① 跳过第一个元素
        if (L.data[i]<min){
            min = L.data[i];
            j = i;
        } //
    L.data[j] = last; // ②
    L.length--; // 顺序表长度减小了 //
    return min; // 返回的是最小值，不是返回0 //
}

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

1
2
3
int Q2(Sqlist &L){
    
}

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

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

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

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

07. 已知在一维数组A[m+n]中依次存放两个线性表(a1, a2, …, am)和(b1, b2, …, bn)，编写一个函数，将数组中两个顺序表的位置互换，即将(b1, b2, …, bn)放在(a1, a2, …, am)的前面。

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

09. 给定三个序列A, B, C，长度均为n，且均为无重复元素的递增序列，请设计一个时间复杂度上尽可能高效的算法，逐行输出同时存在于这三个序列中的所有元素。例如，数组A为{1,2,3}，数组B为{2,3,4}，数组C为{-1,0,2}，则输出2。要求：

  1. 给出算法的基本设计思想。
  2. 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
  3. 说明你的算法的时间复杂度和空间复杂度。

10. 【2010统考真题】 设将n(n>1)个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p(0<p<n)个位置，即将R中的数据由(X0, X1, …, Xn-1)变换为(Xp, Xp+1, …, Xn-1, X0, X1, …, Xp-1)。要求：

  1. 给出算法的基本设计思想。
  2. 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
  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. 说明你所设计算法的时间复杂度和空间复杂度。

12. 【2013统考真题】 已知一个整数序列A=(a0, a1, …, an-1)，其中0≤ai<n(0≤i<n)。若存在ap1=ap2=…=apm=x且m>n/2(0≤pk<n,1≤k≤m)，则称x为A的主元素。例如A=(0,5,5,3,5,7,5,5)，则5为主元素；又如A=(0,5,5,3,5,1,5,7)，则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：

  1. 给出算法的基本设计思想。
  2. 根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
  3. 说明你所设计算法的时间复杂度和空间复杂度。

13. 【2018统考真题】 给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4。要求：

  1. 给出算法的基本设计思想。
  2. 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
  3. 说明你所设计算法的时间复杂度和空间复杂度。

14. 【2020统考真题】 定义三元组(a,b,c)(a,b,c均为整数)的距离D=|a-b|+|b-c|+|c-a|。给定3个非空整数集合S1、S2和S3，按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a,b,c)(a∈S1,b∈S2,c∈S3)中的最小距离。例如S1={-1,0,9}，S2={-25,-10,10,11}，S3={2,9,17,30,41}，则最小距离为2，相应的三元组为(9,10,9)。要求：

  1. 给出算法的基本设计思想。
  2. 根据设计思想，采用C语言或C++语言描述算法，关键之处给出注释。
  3. 说明你所设计算法的时间复杂度和空间复杂度。