2. 计算机
  3. 阅读下列说明和C代码，回答【问题1】至【问题3】，将解答写在答题纸的对应栏内。 【说明】 采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n／2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排

阅读下列说明和C代码，回答【问题1】至【问题3】，将解答写在答题纸的对应栏内。 【说明】 采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n／2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排

admin2015-12-01  73
问题 阅读下列说明和C代码，回答【问题1】至【问题3】，将解答写在答题纸的对应栏内。
    【说明】
    采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n／2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排序的子数组得到排序结果。
    下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下：
    arr：待排序数组
    P，q，r：一个子数组的位置从P到q，另一个子数组的位置从q+1到r
    begin，end：待排序数组的起止位量
    left，right：临时存放待合并的两个子数组
    n1，n2：两个子数组的长度
    i，j，k：循环变量
    mid：临耐变量
    【C代码】
    #inciude＜stdio．h＞
    #inciude＜stdlib．h＞
    Define MAX 65536
    void merge(int arr([]，int P，int q，int r){
    int*left，*right；
    int nl，n2，I，J，k；
    n1=q—P+1：
    n2=r—q：
    If(left=(int*)malloc((nl+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＜nl；i++){
    left=arr[p+i]；
    }
    left=MAX；
    for(i=0；i＜n2；i++){
    right=arr[q+i+1]
    }
    right=MAX；
i=0；j=0；
    For(k=p；(1)；k++)(
    If(1eft＞right[j]{
    (2)
    j++；
    )else{
    arr[k1]=left；
    i++：
    }
    }
    }
    Void merge Sot-t(int arr()，int begin，int end){
    int mid：
    if(    (3)    ){
    mid=(begin+end)／2；
    merge Sort (arr，begin，mid)；
    (4)    ；
    Merge(arr，begin，mid，end)；
    }
    }
    【问题1】
    根据以上说明和C代码，填充(1)一(4)。
    【问题2】
    根据题干说明和以上C代码，算法采用了(5)算法设计策略，分析时间复杂度时，列出其递归式位  (6)  ，接触渐进时间复杂度  (7)  (用O符号表示)。空间复杂度为  (8)  。(用O符号表示)
    【问题3】
    两个长度分别为n1和n2的已经排好序的子数组进行归并，根据上述C代码，则元素之间比较次数为    (9)    。
选项
答案【问题1】 (1)k＜=r (2)arr[k]=right[j] (3)begin＜end (4)mergeSort(arr，mid+1，end) 【问题2】 (5)分治 (6)T(n)=2T(n／2)+O(n) (7)O(nlogn) (8)O(n) 【问题3】 (9)n1+n2
解析 【问题1】
    首先，函数void merge(int arr[]，int P，int q，int r)的意思是：对子数组arr[p…q3和子数组arr[q+L．．r3进行合并。因此第一空为k＜=q；由于是采用归并排序对n个元素进行递增排序，所以第二空是将left和right[j]的小者存放到arr[k]中去，即arr[k]=right[j]：当数组长度为1时，停止递归，因为此时该数组有序，则第三空为begin＜end，即数组至少有两个元素才进行递归。合并了begin到mid之间的元素，继续合并mid+1到end之间的元素，则第四空为mergeSort(arr，mid+1，end)。
    【问题2】
    归并算法实际上就是将数组一直往下分割，直到分割到由一个元素组成的n个子数组，再往上两两归并。
    将数组进行分割需要logN步，因为每次都是讲数组分割成两半(2x=N，x=logN)。
    合并N个元素，需要进行N步，也就是O(N)，则总的时间复杂度为O(NlogN)。
    合并过程中，使用了n个中间变量存储，left=(int*)malloc((nl+1)*sizeof(int))。所以空间复杂度为O(n)。
    推导递归式：
    假设n个元素进行归并排序需要T(n)，可以将其分割成两个分别有n／2个元素的数组分别进行归并，也就是2T(n／2)，在将这两个合并，需要O(n)的时间复杂度，则推导公式为T(n)=2T(n／2)+O(n)。
转载请注明原文地址:https://kaotiyun.com/show/xdDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)