试题详情

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n/2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排好序的子数组得到排序结果。
下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下：
arr：待排序数组
p,q,r：一个子数组的位置从p到q，另一个子数组的位置从q+1到r
begin,end：待排序数组的起止位置
left,right：临时存放待合并的两个子数组
n1,n2：两个子数组的长度
i,j,k：循环变量
mid：临时变量
【C代码】
#inciude
#inciude
#define MAX 65536
void merge(int arr[],int p,int q,int r) {
int *left, *right;
int n1,n2,i,j,k;
n1=q-p+1;
n2=r-q;
if((left=(int*)malloc((n1+1)*sizeof(int)))=NULL) {
perror("malloc error");
exit(1);
}
if((right=(int*)malloc((n2+1)*sizeof(int)))=NULL) {
perror("malloc error");
exit(1);
}
for(i=0;ileft[i]=arr[p+i]；
}
left[i]=MAX；
for(i=0; i right[i]=arr[q+i+1]
}
right[i]=MAX;
i=0; j=0;
for(k=p;   （1）  ; k++) {
if(left[i]> right[j]) {
（2）  ;
j++;
}else {
arr[k]=left[i]；
i++；
}
}
}
void mergeSort(int arr[],int begin,int end){
int mid;
if(  （3）  ){
mid=(begin+end)/2;
mergeSort(arr,begin,mid);
（4）  ;
merge(arr,begin,mid,end);
}
}
【问题1】
根据以上说明和C代码，填充1-4。
【问题2】
根据题干说明和以上C代码，算法采用了（5）算法设计策略。
分析时间复杂度时，列出其递归式位（6），解出渐进时间复杂度为（7）（用O符号表示）。空间复杂度为（8）（用O符号表示）。
【问题3】
两个长度分别为n1和n2的已经排好序的子数组进行归并，根据上述C代码，则元素之间比较次数为（9）。