2. 从业资格
  3. 采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n/2个元素的

采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n/2个元素的

考试题库2022-08-02  2
问题 采用归并排序对n个元素进行递增排序时，首先将n个元素的数组分成各含n/2个元素的两个子数组，然后用归并排序对两个子数组进行递归排序，最后合并两个已经排好序的子数组得到排序结果。下面的C代码是对上述归并算法的实现，其中的常量和变量说明如下：arr：待排序数组p,q,r：一个子数组的位置从p到q，另一个子数组的位置从q+1到rbegin,end：待排序数组的起止位置left,right：临时存放待合并的两个子数组n1,n2：两个子数组的长度i,j,k：循环变量mid：临时变量【C代码】#inciude＜stdio.h>#inciude＜stdlib.h>#define MAX 65536void 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");exit(1);}if((right=(int*)malloc((n2+1)*sizeof(int)))=NULL){perror("malloc error");exit(1);}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;（1）;k++){if(left>right[j]){（2）;j++;}else{arr[k]=left；i++；}}}void mergeSort(int arr[],int begin,int end){int mid;if(（3）){mid=(begin+end)/2;mergeSort(arr,begin,mid);（4）;merge(arr,begin,mid,end);}}【问题1】（8分）根据以上说明和C代码，填充1-4。【问题2】（5分）根据题干说明和以上C代码，算法采用了（5）算法设计策略。分析时间复杂度时，列出其递归式位（6），解出渐进时间复杂度为（7）（用O符号表示）。空间复杂度为（8）（用O符号表示）。【问题3】（2分）两个长度分别为n1和n2的已经排好序的子数组进行归并，根据上述C代码，则元素之间比较次数为（9）。
选项
答案
解析 【问题1】（8分）
（1）k＜=r
（2）arr[k]=right[j]
（3）begin＜end
（4）mergeSort(arr,mid+1,end)
【问题2】（5分）
（5）分治
（6）T(n)=2T(n/2)+n
（7）O(nlgn)
（8）O(n)
【问题3】（2分）
（9）n1+n2
根据题目中的参数说明，void merge(int arr[],int p,int q,int r)是将数组arr[p...q]和数组arr[q+1...r]进行合并成一个排序的数组，因此合并之后数组的长度为r-q+1>0，k=q，也就是k＜=r或k＜r+1；数组arr存入子数组arr[p...q]、arr[q+1...r]当前进行比较的最小值，因此当left>right[j]时，数组arr中存入right，即arr[k]=right[j]；
void mergeSort(int arr[],int begin,int end)是指将数组arr递归进行划分，直到分成多个由一个元素组成的子数组时，停止划分，此时也就是begin==end，因此（3）处为begin＜end，也就是只要begin!=end则继续划分。划分的时候每次分成两半，两半再分别递归，因此mergeSort(arr,begin,mid);mergeSort(arr,mid+1,end);
很明显归并排序使用的分治算法，每次将数组分割成两个小的子数组。
假设对n个元素的数组进行归并排序时间复杂度为T(n)，则分成两个小的子数组后分别进行排序所需的时间为T(n/2)，两个子数组则时间复杂度为2T(n/2)，再加上归并的时间n，即可得出答案归并排序的时间复杂度为O(nlgn)，因为在归并过程中，需要借助left和right两个数组辅助，因此空间复杂度为O(n)。
转载请注明原文地址:https://tihaiku.com/congyezige/2409839.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

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