>>>>>2016下半年软考考前串讲网络班特惠开班！讲师解析知识点，赠送历年真题！

    下午试题，是软件设计师考试的一大难点，除了掌握对应的知识点外，还要多做历年软考真题来巩固学过的知识点，希赛小编为大家整理了2014上半年软件设计师考试下午真题，希望对大家有所帮助。

      试题四

      采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n/2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排好序的子数组得到排序结果。下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下：

      arr：待排序数组

      p，q，r：一个子数组的位置为从p到q，另一个子数组的位置为从q+l到r

      begin，end:待排序数组的起止位置

      left，right:临时存放待合并的两个子数组

      n1，n2:两个子数组的长度

      i，j，k：循环变量

      mid:临时变量

      问题4.1

      根据以上说明和C代码，填充C代码中的空(1)～(4)。

      答案：

      1）k≤r

      2）arr[k]=right[j]

      3)begin<end

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

      问题4.2

      根据题干说明和以上c代码，算法采用了(5)算法设计策略。

      分析时间复杂度时，列出其递归式为(6)，解得渐进时间复杂度为(7)（用O符号表示）。空间复杂度为

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

      答案：

      5)分治

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

      7)O(nlogn)

      8)O(n)

      问题4.3

      两个长度分别为nl和n2的已排好序的子数组进行归并，根据上述C代码，则元素之间比较次数为(9)。

      答案：

      n1+n2

    返回目录：2014上半年软件设计师考试下午真题汇总

    希赛软考网，拥有十四年软考培训经验，希赛网一直坚持自主研发，将丰富的软考培训经验有效融入教程研发过程，自成体系的软考在线题库（软考历年真题）、软考培训教材和软考视频教程，多样的培训方式包括面授、和，使考生的学习更具系统性，辅导更具针对性。采用全程督学机制，，软考平均通过率在全国。