軟件設(shè)計(jì)師案例分析當(dāng)天每日一練試題地址：www.shc2b.com/exam/ExamDayAL.aspx?t1=4

往期軟件設(shè)計(jì)師每日一練試題匯總：www.shc2b.com/class/27/e4_1.html

軟件設(shè)計(jì)師案例分析每日一練試題（2022/6/27）在線測(cè)試：www.shc2b.com/exam/ExamDayAL.aspx?t1=4&day=2022/6/27

點(diǎn)擊查看：更多軟件設(shè)計(jì)師習(xí)題與指導(dǎo)

軟件設(shè)計(jì)師案例分析每日一練試題內(nèi)容（2022/6/27）

閱讀下列說(shuō)明和C代碼，回答問(wèn)題1至問(wèn)題3，將解答寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)。
【說(shuō)明】
采用歸并排序?qū)個(gè)元素進(jìn)行遞增排序時(shí)，首先將n個(gè)元素的數(shù)組分成各含n/2個(gè)元素的兩個(gè)子數(shù)組，然后用歸并排序?qū)蓚€(gè)子數(shù)組進(jìn)行遞歸排序，最后合并兩個(gè)已經(jīng)排好序的子數(shù)組得到排序結(jié)果。
下面的C代碼是對(duì)上述歸并算法的實(shí)現(xiàn)，其中的常量和變量說(shuō)明如下：
arr：待排序數(shù)組
p,q,r：一個(gè)子數(shù)組的位置從p到q，另一個(gè)子數(shù)組的位置從q+1到r
begin,end：待排序數(shù)組的起止位置
left,right：臨時(shí)存放待合并的兩個(gè)子數(shù)組
n1,n2：兩個(gè)子數(shù)組的長(zhǎng)度
i,j,k：循環(huán)變量
mid：臨時(shí)變量
【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);
}
}
【問(wèn)題1】
根據(jù)以上說(shuō)明和C代碼，填充1-4。
【問(wèn)題2】
根據(jù)題干說(shuō)明和以上C代碼，算法采用了（5）算法設(shè)計(jì)策略。
分析時(shí)間復(fù)雜度時(shí)，列出其遞歸式位（6），解出漸進(jìn)時(shí)間復(fù)雜度為（7）（用O符號(hào)表示）?？臻g復(fù)雜度為（8）（用O符號(hào)表示）。
【問(wèn)題3】
兩個(gè)長(zhǎng)度分別為n1和n2的已經(jīng)排好序的子數(shù)組進(jìn)行歸并，根據(jù)上述C代碼，則元素之間比較次數(shù)為（9）。
信管網(wǎng)試題答案與解析：www.shc2b.com/st/3814226162.html

信管網(wǎng)考友試題答案分享：

信管網(wǎng)wangly：
問(wèn)題1： 1: k＜= r 2: arr[k]=right[j] 3: begin ＜ end 4: mergesort（arr, ｍｉｄ+1, end） 問(wèn)題2： 5: 分治 6: 7: o（nlgn） 8: o（n） 問(wèn)題3： n1+n2

信管網(wǎng)試題答案與解析：www.shc2b.com/st/3814226162.html