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

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

      試題四

      采用歸并排序?qū)個元素進行遞增排序時，首先將n個元素的數(shù)組分成各含n/2個元素的兩個子數(shù)組，然后用歸并排序?qū)蓚€子數(shù)組進行遞歸排序，最后合并兩個已經(jīng)排好序的子數(shù)組得到排序結(jié)果。下面的C代碼是對上述歸并算法的實現(xiàn)，其中的常量和變量說明如下：

      arr：待排序數(shù)組

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

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

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

      n1，n2:兩個子數(shù)組的長度

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

      mid:臨時變量

      問題4.1

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

      答案：

      1）k≤r

      2）arr[k]=right[j]

      3)begin<end

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

      問題4.2

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

      分析時間復(fù)雜度時，列出其遞歸式為(6)，解得漸進時間復(fù)雜度為(7)（用O符號表示）?？臻g復(fù)雜度為

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

      答案：

      5)分治

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

      7)O(nlogn)

      8)O(n)

      問題4.3

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

      答案：

      n1+n2

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

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