问答题给定有m个整数的递增有序数组a[1．．m]和有n个整数的递减有序数组b[1..n]，试写出算法：将数组a和b归并为递增有序数组c[1一..m+n]。(要求：算法的时间复杂度为O(m+n)。)【华中理工大学2000八、1(10分)】

【正确答案】正确答案：数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B复制到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。核心语句段如下： i=0； j=n—1 ； k=0；／／i，j，k分别是数组A，B和C的下标，下标从0开始 while(i=0) if(a[i]=0)c[k++]=b[j一一]；若不允许另辟空间，结果在A数组(空间足够大)，则初始k=m+n一1，请参见第2章算法设计题第18题。

【答案解析】