首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答【问题1】至【问题3】,将解答写在答题纸的对应栏内。 【说明】 采用归并排序对n个元素进行递增排序时,首先将n个元素的数组分成各含n/2个元素的两个子数组,然后用归并排序对两个子数组进行递归排序,最后合并两个已经排
阅读下列说明和C代码,回答【问题1】至【问题3】,将解答写在答题纸的对应栏内。 【说明】 采用归并排序对n个元素进行递增排序时,首先将n个元素的数组分成各含n/2个元素的两个子数组,然后用归并排序对两个子数组进行递归排序,最后合并两个已经排
admin
2015-12-01
83
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
阅读以下说明,回答问题1至问题7,将解答填入对应的解答栏内。【说明】某网络拓扑结构如下图所示。网络A中的DNS_Server1和网络B中的DNSSeNer2分别安装有WindowsServer2003并启用了DNS服务。DNS_Server
根据你的网络工程经验,请用250字以内的文字简要描述该21层教学综合大楼网络层次结构设计的要点。(不要求画图)该21层教学综合大楼网络规则方案不仅要体现所设计的网络能满足现有及未来几年信息系统的应用需求,还需具有较高的平均无故障时间和尽可能低的平均故障
如果ping127.0.0.1(本地循环地址),如果该地址无法Ping通,则说明了是什么原因?在DOS状态下输入tracertwww.ciu.net.cn并执行后,经过一段时间等待,系统会反馈出很多IP地址。出现在最上方(第1条记录)的IP地址是什么
阅读以下有关传统局域网络运行和维护的叙述,将应填入(n)处的字句写在对应栏内。在对网络运行及维护前首先要了解网络,包括识别网络对象的硬件情况、判别局域网的拓扑结构和信道访问方式、确定网络互联以及用户负载等。常见的3种拓扑结构是星形、(1)与(2)拓
阅读以下说明、Java源程序和运行测试部分1.HTTP协议。●HTTP请求消息示例:GET/index,htmlHTTP/1.1Accept:image/gif,image/jpeg,*/Acc
在图4-8所示的无线接待室中WLAN采用的体系结构如图4-9所示,请将(1)~(3)空缺处填写完整请将以下(11)~(14)空缺处的内容填写完整,并帮助郭工程师解释产生以下网络故障的原因。该网络建成后一直使用正常,但最近发现无线覆盖区域A、B
请阅读以下说明和Socket程序,将应填入(n)处的字句写在对应栏内。【说明】网络应用的基本模型是客户机/服务器模型,这是一个不对称的编程模型,通信的双方扮演不同的角色:客户机和服务器。一般发起通信请求的应用程序称为客户软件,该应
简述网络规划阶段需求分析的方法和解决的问题。(控制在100个字以内)在网络规划阶段“系统可行性分析和论证”的主要内容是什么?(控制在100个字以内)
随机试题
下列对关键酶的叙述错误的是
具有杀虫作用的药物有
土地估价报告的内部审核应坚持合法性准则,其审核的重点主要有()。
“申报日期”栏应填()。“装货港”栏应填()。
证券公司从事介绍业务,应当在其经营场所显著位置或者其网站,公开( )等信息。
根据刑法理论,实施一个行为,同时触犯数个不同罪名的犯罪形态是()。
(2009年)甲研究所与乙公司订立的买卖合同约定:乙公司向甲研究所购买一台具有特定性能的石墨卷材生产设备,总价款300万元;乙公司应于合同签订之日起3日内向甲研究所支付100万元预付款;甲研究所应于2008年11月1日之前交付设备(乙公司自行提货);乙公司
从所给的四个选项中,选择最合适的一个填入问号处,使之呈现一定的规律性:
Fearanditscompanionpainaretwoofthemostusefulthingsthatmenandanimalspossess,iftheyareproperlyused.Iffired
A、itbelievedthatthebookswereanabhorrencetoGodB、itbelievedthatthebookswouldweakenthecommunicationwithGodC、it
最新回复
(
0
)