一.顺序表基础算法
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, 结束。
