软件设计师案例分析当天每日一练试题地址：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4

往期软件设计师每日一练试题汇总：www.cnitpm.com/class/27/e4_1.html

软件设计师案例分析每日一练试题（2024/12/14）在线测试：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2024/12/14

点击查看：更多软件设计师习题与指导

软件设计师案例分析每日一练试题内容（2024/12/14）

阅读下列说明和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）。
信管网试题答案与解析：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2024/12/14

信管网考友试题答案分享：

信管网cnit**************：
p＜n1＜br＞arr[k]=right[j]＜br＞begin＜end＜br＞mergesort（arr,ｍｉｄ,end）＜br＞分治＜br＞n＊logn＜br＞n2＜br＞＜br＞

信管网cnit**************：
k＜=r arr[k]=right[j] begin＜end mergesort（arr,ｍｉｄ+1,end） 分治，t（n）=t（n/2）+o（n）,o（nlogn）,o（n） n1+n2

信管网wang**：
问题1： 1: k＜= r 2: arr[k]=right[j] 3: begin ＜ end 4: mergesort（arr, ｍｉｄ+1, end） 问题2： 5: 分治 6: 7: o（nlgn） 8: o（n） 问题3： n1+n2

信管网试题答案与解析：www.cnitpm.com/exam/ExamDayAL.aspx?t1=4&day=2024/12/14