原创 2011 年全国硕士研究生入学考试计算机科学与技术学科编程题

 2011-11-25 00:43  1523 12 12 分类: MCU/ 嵌入式

一个长度为 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）说明你所设计算法的时间复杂度和空间复杂度。

解答：

int middle_number(int A[],int B[],int n){

int la=0,lb=0,ha=n-1,hb=n-1,ma,mb;

while(la<=ha&&lb<=hb){

ma=(la+ha)/2;

mb=(lb+hb)/2;

if(A[ma]==B[mb])

return A[ma];

if(A[ma]<B[mb]){