【正确答案】正确答案：求两个序列A和B的中位数最简单的办法就是将两个升序序列进行归并排序，然后求其中位数。这种解法虽可求解，但在时间和空间两方面都不大符合高效的要求，但也能获得部分分值。 根据题目分析，分别求两个升序序列A和B的中位数，设为a和b。 ①若a=b，则a或b即为所求的中位数。 原因：容易验证，如果将两个序列归并排序，则最终序列中，排在子序列ab前边的元素为先前两个序列中排在a和b前边的元素；排在子序列ab后边的元素为先前两个序列中排在a和b后边的元素。所以子序列ab一定位于最终序列的中间，又因为a=b，显然a就是中位数。 ②否则(假设a＜b)，中位数只能出现(a，b)范围内。 原因：同样可以用归并排序后的序列来验证，归并排序后必然有形如…a…b…的序列出现，中位数必出现在(a，b)之间。因此可以做如下处理：舍弃a所在序列A的较小一半，同时舍弃b所在序列B的较大一半。在保留两个升序序列中求出新的中位数a和b，重复上述过程，直到两个序列中，只含一个元素时为止，则较小者即为所求的中位数。每次总的元素个数变为原来的一半。 算法的基本设计思想如下。 分别求出序列A和B的中位数，设为a和b，求序列A和B的中位数过程如下： ①若a=b，则a或b即为所求中位数，算法结束。 ②若a＜b，则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求舍弃的长度相等。 ③若a＞b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求舍弃的长度相等。 在保留的两个升序序列中，重复过程①、②、③，直到两个序列中只含一个元素时为止，较小者即为所求的中位数。

【正确答案】正确答案：算法的实现如下： int M Search(int A[]，intB[]，int n){ int s1=0，d1=n-1，m1，s2=1，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 f／／元素个数为偶数 s1=m1+1；／／舍弃A中间点及中间点以前部分 d2=m2；／／舍弃B中间点以后部分且保留中间点 } } elsef／／满足条件3) if((sl+d1)％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]， }

【正确答案】正确答案：算法的时间复杂度为O(log ₂ n)，空间复杂度为O(1)。

【答案解析】解析：综合考查了顺序表的折半查找和归并的思想。