軟件設(shè)計(jì)師下午考試科目為案例分析，考試題型為主觀題，4道必答題，2道(5、6題)選答題，考試時長2個半小時，共75分。為幫助廣大軟考中級軟件設(shè)計(jì)師考生更好備考，信管網(wǎng)特整理匯總了軟件設(shè)計(jì)師部分真題、答案及解析供考生查閱，并提供免費(fèi)在線模擬答題、歷年真題免費(fèi)下載等服務(wù)，了解軟件設(shè)計(jì)師更多備考信息請關(guān)注信管網(wǎng)。

相關(guān)推薦：

點(diǎn)擊查看/下載：軟件設(shè)計(jì)師歷年真題匯總

點(diǎn)擊查看：軟件設(shè)計(jì)師在線培訓(xùn)課程 丨 免費(fèi)試聽課程

免費(fèi)練習(xí)：軟件設(shè)計(jì)師考試題庫(模擬試題、章節(jié)練習(xí)、每日一練)

閱讀下列說明和C代碼，回答問題1至問題3，將解答寫在答題紙的對應(yīng)欄內(nèi)。

【說明】

采用歸并排序?qū)個元素進(jìn)行遞增排序時，首先將n個元素的數(shù)組分成各含n/2個元素的兩個子數(shù)組，然后用歸并排序?qū)蓚€子數(shù)組進(jìn)行遞歸排序，最后合并兩個已經(jīng)排好序的子數(shù)組得到排序結(jié)果。

下面的C代碼是對上述歸并算法的實(shí)現(xiàn)，其中的常量和變量說明如下：

arr：待排序數(shù)組

p,q,r：一個子數(shù)組的位置從p到q，另一個子數(shù)組的位置從q+1到r

begin,end：待排序數(shù)組的起止位置

left,right：臨時存放待合并的兩個子數(shù)組

n1,n2：兩個子數(shù)組的長度

i,j,k：循環(huán)變量

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;i left[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】

根據(jù)以上說明和C代碼，填充1-4。

【問題2】

根據(jù)題干說明和以上C代碼，算法采用了(5)算法設(shè)計(jì)策略。

分析時間復(fù)雜度時，列出其遞歸式位(6)，解出漸進(jìn)時間復(fù)雜度為(7)(用O符號表示)?？臻g復(fù)雜度為(8)(用O符號表示)。

【問題3】

兩個長度分別為n1和n2的已經(jīng)排好序的子數(shù)組進(jìn)行歸并，根據(jù)上述C代碼，則元素之間比較次數(shù)為(9)。

信管網(wǎng)參考答案：

【問題1】

(1)k<=r

(2)arr[k]=right[j]

(3)begin

(4)mergesort(arr,mid+1,end)

【問題2】

(5)分治

(6)T(n)=2T(n/2)+n

(7)O(nlgn)

(8)O(n)

【問題3】

(9)n1+n2

查看解析：m.xiexiliangjiufa.com/st/3814226162.html