问答题
已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入前一个数组序列中，完成后两个数组中的数分别有序(非降序)并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。例如，第一个数组为：4，12，28第二个数组为：1，7，9，29，45输出结果为：1，4，7…………一第一个数组9，12，28，29，45……-一第二个数组【上海大学1998四(20分)】
【正确答案】正确答案：设两个数组分别是A和B，各有m和n个元素。结果要求第一个数组的最后一个数A[m一1]不大于第二个数组的第一个数B[0]。由于要求将第二个数组的数插入第一个数组中。因此比较A[m一1]和B[0]，如Aim一1]＞B[0]，则交换。交换后仍保持A和B有序。重复以上步骤，直到A[m一1]≤B[0]为止。核心语句段如下： while(A[m-1]>B[0]) {x=A[m一1]；A[m一1]=B[0]； ／／交换A[m一1]和B[0] 在0..m一2间折半查找A[m一1]的插入位置，并插入 在1..n一1间折半查找x的插入位置，并插入 }
【答案解析】