问答题
试题四(共15分)
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
[说明]
采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n／2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排好序的子数组得到排序结果。
下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下：
arr：持排序数组
p，q，r：一个子数组的位置为从p到q，另一个子数组的位置为从q+1到r
begin，end：待排序数组的起止位置
left，right：临时存放待合并的两个子数组
n1，n2：两个子数组的长度
k，j，k：循环变量
mid：临时变量
[C代码]
问答题
[问题1](8分)
根据以上说明和C代码，填充C代码中的空(1)～(4)。
【正确答案】(1) k＜＝r或k＜r+1 (2)arr[k]＝right[j]
(3)begin＜end (4)mergeSort(arr，mid+1，end)
【答案解析】试题四分析
本题考查算法设计、分析和C程序实现的知识，属于传统题目，考查点也与往年类似。
归并排序是一种经典的排序算法，基本思想：把n个元素构成的数组分成两个n／2个元素构成的子数组，再进一步划分，一直到每个子数组仅包含1个元素，此时再把两两有序的数组合并成更大的有序数组，一直到整个数组有序为止。
[问题1]
本问题考查算法的实现。C程序中有两个函数，merge函数将两个有序数组合并成一个更大的有序数组。归并过程是首先将两个有序的子数组的元素分别放到left和right数组中，然后依次比较这两个数组中的元素，从小到大把元素放到arr数组的特定元素中。包含空格(1)的for循环中，给出了将left和right元素放入arr中，放入的位置是从p到r，因此，空格(1)填写k＜＝r。在比较left[i]和right[j]元素时，若left[i]＞right[j]，则应该把right[j]的值放入arr[k]中，因此空格(2)填写arr[k]＝right[j]。mergeSort函数进行数组的排序。若数组元素个数大于1，则继续划分，因此空格(3)填写begin＜end。将数组从arr[begin]到arr[end]划分为arr[begin]到arr[mid]和arr[mid+1]到arr[end]两个部分，因此空格(4)填写mergeSort(arr，mid+1，end)。
问答题
[问题2](5分)
根据题干说明和以上C代码，算法采用了____(5)____算法设计策略。
分析时间复杂度时，列出其递归式为____(6)____，解得渐进时间复杂度为____(7)____(用O符号表示)。空间复杂度为____(8)____(用O符号表示)。
【正确答案】(5)分治
(6)T(n)＝2T(n／2)+n或T(n)＝2T(n／2)+f(n) (f(n)为线性函数)
(7)O(nlgn)
(8)O(n)
【答案解析】 本问题考查算法的设计策略和时间复杂度，归并排序算法是一个典型的分治算法。每次将一个规模为n的问题变成两个规模为n/2的子问题，划分时直接从中间分开，因此划分采用O(1)的时间，然后是递归求解两个子问题，根据merge函数代码，合并的时间是线性时间O(n)。因此递归式为T(n)＝2T(n／2)+f(n)，f(n)为线性函数。用主方法求解，得到时间复杂度为O(nlgn)。由于在归并过程中，需要left和right两个辅助数组，其规模为待排序的数组长度，即O(n)。
问答题
[问题3](2分)
两个长度分别为n1和n2的已排好序的子数组进行归并，根据上述C代码，则元素之间比较次数为____(9)____。
【正确答案】(9)n1+n2
【答案解析】 本问题考查对算法的进一步分析。元素之间的比较次数就是merge函数的最后一个for循环体执行的次数，由于k从p到r，故循环体执行次数为r-p+1次，即n1+n2次。