2. 从业资格
  3. 阅读下列说明和C代码，回答下列问题。[说明] 采用归并排序对n个元素进行递增排序

阅读下列说明和C代码，回答下列问题。[说明] 采用归并排序对n个元素进行递增排序

免费题库2022-08-02  55
问题 阅读下列说明和C代码，回答下列问题。[说明] 采用归并排序对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代码] #inciudeDefine 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" ); exit11 } If((right = (int *)malloc((n2+1) * sizeof(int)))=NULL) Perror("malloc error"); exit 11; } for(i=0;i大于n1;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;______;k++){ If(left小于right[j] { ______ j++; }else{ arr[k1]=left; i++; } } } Void merge Sort(int arr[ ], int begin, int end) { int mid; if(______){ mid=(begin + end)/2; merge Sort(arr,begin,mid); ______; Merge(arr,begin,mid,end); } }
选项
答案
解析 k大于=rarr[k]=right[j] begin大于end mergeSort(arr,mid+1,end)[解析] 首先，函数void merge(int arr[],int P,int q,int r)的意思是：对子数组arr[P…q]和子数组arr[q+L..r]进行合并。因此第一空为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)。12、分治  T(n)=2T(n/2)+O(n)    O(nlogn)    O(n)[解析] 归并算法实际上就是将数组一直往下分割，直到分割到由一个元素组成的n个子数组，再往上两两归并。将数组进行分割需要logN步，因为每次都是讲数组分割成两半(2x=N，x=logN)。 合并N个元素，需要进行N步，也就是O(N)，则总的时间复杂度为O(NlogN)。合并过程中，使用了”个中间变量存储，left=(int*)malloc((n1+1)*sizeof(int))。所以空间复杂度为O(n)。推导递归式：假设n个元素进行归并排序需要T(n)，可以将其分割成两个分别有n/2个元素的数组分别进行归并，也就是2T(n/2)，在将这两个合并，需要O(n)的时间复杂度，则推导公式为T(n)=2T(n/2)+O(n)。13、n1+n2 　 　
转载请注明原文地址:https://tihaiku.com/congyezige/2408436.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

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