>>>>>2016下半年軟考考前串講網(wǎng)絡(luò)班特惠開(kāi)班！講師解析知識(shí)點(diǎn)，贈(zèng)送歷年真題！

    下午試題，是軟件設(shè)計(jì)師考試的一大難點(diǎn)，除了掌握對(duì)應(yīng)的知識(shí)點(diǎn)外，還要多做歷年軟考真題來(lái)鞏固學(xué)過(guò)的知識(shí)點(diǎn)，希賽小編為大家整理了2014上半年軟件設(shè)計(jì)師考試下午真題，希望對(duì)大家有所幫助。

      試題四

      采用歸并排序?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+l到r

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

      left，right:臨時(shí)存放待合并的兩個(gè)子數(shù)組

      n1，n2:兩個(gè)子數(shù)組的長(zhǎng)度

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

      mid:臨時(shí)變量

      問(wèn)題4.1

      根據(jù)以上說(shuō)明和C代碼，填充C代碼中的空(1)～(4)。

      答案：

      1）k≤r

      2）arr[k]=right[j]

      3)begin<end

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

      問(wèn)題4.2

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

      分析時(shí)間復(fù)雜度時(shí)，列出其遞歸式為(6)，解得漸進(jìn)時(shí)間復(fù)雜度為(7)（用O符號(hào)表示）。空間復(fù)雜度為

      (8)（用O符號(hào)表示）。

      答案：

      5)分治

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

      7)O(nlogn)

      8)O(n)

      問(wèn)題4.3

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

      答案：

      n1+n2

    返回目錄：2014上半年軟件設(shè)計(jì)師考試下午真題匯總

    希賽軟考網(wǎng)，擁有十四年軟考培訓(xùn)經(jīng)驗(yàn)，希賽網(wǎng)一直堅(jiān)持自主研發(fā)，將豐富的軟考培訓(xùn)經(jīng)驗(yàn)有效融入教程研發(fā)過(guò)程，自成體系的軟考在線題庫(kù)（軟考?xì)v年真題）、軟考培訓(xùn)教材和軟考視頻教程，多樣的培訓(xùn)方式包括面授、和，使考生的學(xué)習(xí)更具系統(tǒng)性，輔導(dǎo)更具針對(duì)性。采用全程督學(xué)機(jī)制，，軟考平均通過(guò)率在全國(guó)。