关于线性表408考的还是挺频繁的，其实总体来说并不难（暴力破解），要是最优算法在考场上那种气氛还是蛮难想到的。本文主要总结在2010年-2020年的408考试中考过的关于线性表大题破解方法以及代码，废话不多说直接上真题：
2010年大题：
算法思路：这是一道很经典的逆置算法题，可以通过数学的思路设前面的X0，X1，...Xp-1为a序列，后面的X p，Xp+1...Xn-1为b，则我们知道原序列为
，通过逆置我们可以得到
，随后对整个数列进行逆置
。根据这个思路我们可以来构建算法。
代码：
int Turn(int a[],int left,int right,int arraySize) //逆置算法 { if(right<left||arraySize>Maxsize) { printf("error"); return 0; } int temp; int i=left,j=right; int mid=(left+right+1)/2; for(i,j;i<mid;i++,j--) { temp=a[i]; a[i]=a[j]; a[j]=temp; } } int main() { int a[6]={1,2,3,4,5,6}; //如果设定p为4的话 Turn(a,0,2,6); Turn(a,3,5,6); Turn(a,0,5,6); for(int i=0;i<6;i++) printf("%d ",a[i]); return 0; }
算法时间复杂度为O(n)，空间复杂度为O(1)。
2011年大题：
算法思路：这道题我一拿到想到的就是先进行合并再进行计算。这样做的时间复杂度为，
标准答案给的是
。但进入考场本身408时间就紧张，我这里提供暴力算法进行计算。因为这两个序列都是升序序列，所以只要进行合并之后变可以很轻松的获得该中位数。
代码：
int merge_list(int a[],int b[],int n) { int i=0,j=0,k=0; int c[2*n]; while(i<n&&j<n) { if(a[i]<=b[j]) c[k++]=a[i++]; else c[k++]=b[j++]; } while(i<n) { c[k++]=a[i++]; } while(j<n) { c[k++]=b[j++]; } return c[n-1]; } int main() { int a[5]={2,4,6,8,20}; int b[5]={11,13,15,17,19}; printf("%d",merge_list(a,b,5)); return 0; }
算法时间复杂度为O(n)，空间复杂度为O(2n)。
这里附上真题标准答案：
int M _ Search(int A[ ],int B[ ],int n){ int start1, end1, mid1, start2, end2, mid2 ; start1 =0;end1 =n-1 ; start2 = 0 ; end2 = n- 1 ; while(start1 ! = end1 || start2 ! = end2) { mid1 = (start1 +end1 )/2 ; mid2 = ( start2 +end2 )/2 ; if(A[mid1 ] = =B[mid2]) return A[mid1 ] ; if( A [ mid1 ] {//分别考虑奇数和偶数，保持两个子数组元素个数相等 if((start1+end1)%2==0){//若元素为奇数个 start1=mid1; //舍弃A 中间点以前的部分且保留中间点 end2=mid2; //舍弃B 中间点以后的部分且保留中间点 } else{ //若元素为偶数个 start1=mid1+1;//舍弃A 的前半部分 end2=mid2; //舍弃B 的后半部分 } } else{ if((start1+end1)%2=：0){//若元素为奇数个 end1=mid1; //舍弃A 中间点以后的部分且保留中间点 start2=mid2; //舍弃B 中间点以前的部分且保留中间点 } else{//若元素为偶数个 end1=mid1; //舍弃A 的后半部分 start2=mid2+1;//舍弃B 的前半部分 } } } return A[start1] }
上述所给算法的时间、空间复杂度分别是0(log2n)和0(1)。
