一.顺序表基础算法

1.说明

博主这里是算法练习，帅气的读者来这里默认已经知道了它，这里主要是针对408考研真题中关于线性表的算法题进行编写。第一部分是根据课本编写线性表的基本函数，剩下四个部分是针对考研真题的算法练习。

2.C语言代码

这里使用C语言实现课本要求的基本算法，一=以一个学生成绩单为例：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define MaxSize 50                //这里只是演示，我们假设这里最多存五十个学生信息
//定义学生结构
typedef struct {
  char name[20];              //姓名
  char tel[15];               //电话
  char id[10];               //学号，这个是主键
  int  grade;               //分数
} Elemtype;
//声明使用顺序表
typedef struct {
  /*这里给数据分配内存，可以有静态和动态两种方式，这里采用动态分配*/
  Elemtype  *data;            //存放线性表中的元素是Elemtype所指代的学生结构体
  int length;                 //存放线性表的长度
} SqList;           //给这个顺序表起个名字，接下来给这个结构体定义方法
//初始化线性表
void InitList(SqList &L){
  /*动态分配内存的初始化*/
  L.data = (Elemtype*)malloc(MaxSize * sizeof(Elemtype));  //为顺序表分配空间
  L.length = 0;                                            //初始化长度为0
}
//求表长函数
int Length(SqList &L){
  return L.length;
}
//求某个数据元素值
bool GetElem(SqList &L, int i, Elemtype &e) {
  if (i < 1 || i > L.length)
    return false;         //参数i错误时，返回false
  e = L.data[i - 1];      //取元素值
  return true;
}
//输出线性表
void DispList(SqList &L) {
  if (L.length == 0)
    printf("线性表为空");
  //扫描顺序表，输出各元素
  for (int i = 0; i < L.length; i++) {
    printf("%s   %s   %s     %d", L.data[i].name, L.data[i].tel, L.data[i].id, L.data[i].grade);
    printf("\n");
  }
  printf("\n");
}
//插入数据元素
bool ListInsert(SqList &L, int i, Elemtype e) {
  /*在顺序表L的第i个位置上插入新元素e*/
  int j;
  //参数i不正确时，返回false
  if (i < 1 || i > L.length + 1 || L.length == MaxSize)
    return false;
  i--;                //将顺序表逻辑序号转化为物理序号
  //参数i正确时，将data[i]及后面的元素后移一个位置
  for (j = L.length; j > i; j--) {
    L.data[j] = L.data[j - 1];
  }
  L.data[i] = e;      //插入元素e
  L.length++;         //顺序表长度加1
  return true;
  /*平均时间复杂度为O(n)*/
}
//删除数据元素
bool ListDelate (SqList &L, int i, Elemtype &e) {
  /*删除顺序表中的第i个元素，其值为e*/
  int j;
  if (i < 1 || i > L.length)
    return false;
  i--;              //将顺序表逻辑序号转化为物理序号
  e = L.data[i];
  //参数正确时，将data[i]之后的元素前移一个位置
  for (j = i; j < L.length - 1; j++)
    L.data[j] = L.data[j + 1];
  L.length--;     //顺序表的长度减1
  return true;
  /*平均时间复杂度为O(n)*/
}
//元素查找
int LocateElem(SqList &L, Elemtype e) {
  /*顺序查找第一个值域与e相等的元素逻辑序号（根据e找i）*/
  int i = 0;
  //while循环查找e,这里的依据是姓名
  while (i < L.length && strcmp(L.data[i].name, e.name) != 0)
    i++;
  if (i >= L.length)
    return 0;                      //未找到返回0
  else
    printf("%s    %s    %s     %d", L.data[i].name, L.data[i].tel, L.data[i].id, L.data[i].grade);
  return i + 1;                 //找到后返回其逻辑序号
  /*时间复杂度为O(n)*/
}

3.说明

由于只是算法练习，所以不写完整代码，博主已用线性表完成相关完整项目，可以点击这里查看

二.2010算法真题

1.题目

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

1)给出算法的基本设计思想。

2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

3)说明你所设计算法的时间复杂度和空间复杂度。

2.分析

可将问题视为把数组ab转换成数组ba (a代表数组的前p个元素，b代表数组中余下的n-p个元素，先将a逆置得到a -1b,再将a -1b逆置得到(a -1b-1),最后将整个a 'b I逆置得到(a -1b-1)-1=ba。

此算法原理来源于考研线性代数矩阵的转换公式，(a -1b-1)-1=ba。以abcdefgh为例：

Reverse (0,p-1)得到cbade fgh;
Reverse(p,n-1)得到cbahgfed;
Reverse(0,n-1)得到de fghabc;

3.算法代码

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

4.说明

最简单的算法题了，必须要会。

考研算法题，不一定看到要时间复杂度和空间复杂度最优就不会，按照平时的练习，能解决问题就行，其余都对只会扣1到2分，哪怕算法不是最优。

所以,如果你想不到这种算法,可以提前申请n个位置,然后把b整体搬迁,能解决问题就行。

三.2011算法真题

1.题目

一个长度为L (L≥1)的升序序列s,处在第[L/2]个位置的数称为s的中位数。例如，若序列Si=(11,13, 15, 17,19)，则S;的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2, 4,6,8, 20),则S和S2的中.位数是11。现在有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：

1)给出算法的基本设计思想。

2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

3)说明你所设计算法的时间复杂度和空间复杂度。

2.分析

算法的基本设计思想如下:

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

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

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

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

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

3.算法代码

int M_Search(int A[], int B[], int n) {
  int s1 = 0, d1 = n - 1, m1, 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];     //满足条件①
    if (A[m1] < B[m2]) {      //满足条件②
      if ((s1 + d1) % 2 == 0) { //若元素 个数为奇数
        s1 = m1 ;     //舍弃A中间点以前
        d2 = m2;
      }//舍弃B中间点以后
      else {                 //元素个数为偶数
        s1 = m1 + 1 ;
        //舍弃A中间点及中
        d2 = m2;
        // 舍弃B中间点以后
      }
    } else {
      //满足条件③
      if ((s2 + d2) / 2 == 0) { //若元素 个数为奇数
        d1 = m1;
        //舍弃A中间点以后
        s2 = m2;
        //舍弃B中间点以前
      } else {
        // 元素个数为偶数
        d1 = m1;
        //舍弃A中间点以后
        s2 = m2 + 1;
        //舍弃B中间点及中
      }
      return A[s1] < B[s2] ? A[s1] : B[s2] ;
    }
  }
}

4.补充

答案确实是最标准的算法,但是我们很难想到,最简单想到的就是使用归并排序后再求中位数,考试也可以这么干.

四.2013算法真题

1.题目

[2013统考真题]已知一个整数序列A=(a,a1,.,an-1),其中0≤a;<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)说明你所设计算法的时间复杂度和空间复杂度。

2.思路

算法的基本设计思想:算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数，确认Num是否是主元素。

算法可分为以下两步:

①选取候选的主元素。依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1;若遇到的下一个整数仍等于Num,则计数加1，否则计数减1;当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1,开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。

②判断c中元素是否是真正的主元素。再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素;否则，序列中不存在主元素。

3.算法代码

int Majority(int A[], int n) {
  int i, c, count = 1;
  //c用来保存候选主元素，count用来计数
  c = A[0] ;
  //设置A[0]为候选主元素
  for (i = 1; i < n; i++)
    //查找候选主元素
    if (A[i] == c)
      count++;
  //对A中的候选主元素计数
    else if (count > 0)
      //处理不是候选主元素的情况
      count-- ;
    else {
      //更换候选主元素，重新计数
      c = A[i];
      count = 1 ;
      if (count > 0)
        for (i = count = 0; i < n; i++) //统计 候选主元素的实际出现次数
          if (A[i] == c)
            count++ ;
      if (count > n / 2) return c;
      // 确认候选主元素
      else return -1 ;
      // 不存在主元素
    }
}

五.2018算法真题

1.题目

给定一个含n (n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3, 2,3}中未出现的最小正整数是1;数组{1,2, 3}中未出现的最小正整数是4。要求:

1)给出算法的基本设计思想。

2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

3)说明你所设计算法的时间复杂度和空间复杂度。

2.思路

要求在时间上尽可能高效，因此采用空间换时间的办法。分配一个用于标记的数组B[n],用来记录A中是否出现了1~n 中的正整数，B[0]对应正整数1，B[n-1]对应正整数n,初始化B中全部为0。由于A中含有n个整数，因此可能返回的值是1~n+1，当A中n个数恰好为1~n时返回n+1。当数组A中出现了大于或等于0或大于n的值时，会导致1~n中出现空余位置，返回结果必然在1~n中，因此对于A中出现了大于或等于0或大于n的值，可以不采取任何操作。

3.算法代码

int findMissMin(int A[], int n) {
  int i, *B;
  B = (int *)malloc(sizeof (int) * n) ; //分配空间
  memset(B, 0, sizeof (int)*n) ;
  for (i = 0; i < n; i++)
    if (A[i] > 0 && A[i] <= n)
      //若A[i]的值介于1~n，则标记数组B
      B[A[i] - 1] = 1;
  for (i = 0; i < n; i++)
    //扫描数组B，找到目标值
    if (B[i] == 0) break;
  return i + 1;
}

4.补充

上一道题的次优解法思路,典型的空间换时间.

六.2020算法真题

1.题目

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

1)给出算法的基本设计思想。

2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

3)说明你所设计算法的时间复杂度和空间复杂度。

2.思路

由D的表达式可知，事实上决定D大小的关键是a和c之间的距离，于是问题就可以简化为每次固定c找一个a,使得L3=|c- a|最小。

1)算法的基本设计思想

①使用Dmin记录所有已处理的三元组的最小距离，初值为一个足够大的整数。

②集合S、S2和S3 分别保存在数组A、B、C中。数组的下标变量i=j=k=0,当i<|S|j<|S2|且k< |Ss|时(|S|表示集合S中的元素个数)，循环执行下面的a) ~c)。

a)计算(A[i], B[], C[k])的距离D; (计算 D)

b)若D<Dmin,则Dmin=D; (更新D)

c)将A[]、B[小]、C[k]中的最小值的下标+1; (对照分析:最小值为a,最大值为c，这里

C不变而更新a,试图寻找更小的距离D)

③输出Dmin, 结束。

顺序表算法练习

一.顺序表基础算法

1.说明

2.C语言代码

3.说明

二.2010算法真题

1.题目

2.分析

3.算法代码

4.说明

三.2011算法真题

1.题目

2.分析

3.算法代码

4.补充

四.2013算法真题

1.题目

2.思路

3.算法代码

五.2018算法真题

1.题目

2.思路

3.算法代码

4.补充

六.2020算法真题

1.题目

2.思路

3.算法代码

热门文章

最新文章

相关课程

相关电子书

相关实验场景