首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答【问题1】至【问题3】,将解答写在答题纸的对应栏内。 【说明】 采用归并排序对n个元素进行递增排序时,首先将n个元素的数组分成各含n/2个元素的两个子数组,然后用归并排序对两个子数组进行递归排序,最后合并两个已经排
阅读下列说明和C代码,回答【问题1】至【问题3】,将解答写在答题纸的对应栏内。 【说明】 采用归并排序对n个元素进行递增排序时,首先将n个元素的数组分成各含n/2个元素的两个子数组,然后用归并排序对两个子数组进行递归排序,最后合并两个已经排
admin
2015-12-01
43
问题
阅读下列说明和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://jikaoti.com/ti/asi7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
请在(1)、(2)、(3)、(4)空白处填写恰当的内容。Web客户机与服务器共同遵守(1)协议,其工作过程是;Web客户端程序根据输入的(2)连接到相应的Web服务器上,并获得指定的Web文档。动态网页以(3)程序的形式在服务器端处理,并给客户端返
在Windows2003中,(1)不能实现NAT功能。A.终端服务管理器B.Internet连接共享C.路由和远程访问部门B中主机PCI的默认网关地址应配置为(4)才能访问Internet。
该网络采用R1~R7共7台路由器,采用动态路由协议OSPF。由图1-1可见,该网络共划分了3个OSPF区域,其主干区域为(1),主干区域中,(2)为区域边界路由器,(3)为区域内路由器。下表是该系统中路由器的IP地址分配表。请根据上
阅读以下说明,回答问题1至问题5,将解答填入对应的解答栏内。【说明】某公司内部服务器S1部署了重要的应用,该应用只允许特权终端PC1访问,如下图所示。为保证通信安全,需要在S1上配置相应的IPSec策略。综合考虑后,确定该IPSec策略如下。
为了使DNS_Server1能正确解析本地Web站点的域名,需对DNS_Server1中的DNS服务进行配置。在图1所示的对话框中,新建的区域名称是(1);在图2所示的对话框中,添加的新建主机名称为(2),IP地址栏应填入(3)。DNS系统中反向查询
为了使DNS_Server1能正确解析本地Web站点的域名,需对DNS_Server1中的DNS服务进行配置。在图1所示的对话框中,新建的区域名称是(1);在图2所示的对话框中,添加的新建主机名称为(2),IP地址栏应填入(3)。如下图所示,配置允许
请在(1)~(4)空白处填写恰当的内容。DHCP的工作过程是:1)IP租用请求。DHCP客户机启动后,发出一个DHCPDISCOVER消息,其封包的源地址为(1),目标地址为(2)。2)IP租用提供。当DHCP服务器收到DHCPDI
与ISDN相关的网络设备主要有TA、NT1、NT2、TE1、TE2等。在图2-9所示的网络拓扑结构中,路由器Router1和ISDN之间是否需要加入终端适配器(TA)?请用150字以内的文字简要说明理由。在以上路由器Router2的配置命令列表中,di
阅读以下关于校园网组建的技术说明,根据要求回答问题1至问题4。【说明】某学校新建一栋21层教学综合大楼,楼层两端相距100m,距一端50m处有一弱电竖井,弱电竖井贯穿每层的弱电室。每层楼均有100个信息点(所有信息点要求具有100Mb/s的数据传
阅读以下关于网络地址转换(NAT)的技术说明,结合网络拓扑图回答问题1至问题3。【说明】网络地址转换(NAT)技术可用来缓解IP地址短缺问题和实现TCP负载均衡功能。动态地址翻译技术在子网外部使用少量的全局地址,通过路由器进行内部和外部地址的转换
随机试题
Whenisitpermissibletotellalie?Never,accordingtoAugustineandKant.Machiavelliapprovedlyingforprinces,Nietzsche
马克思主义最崇高的社会理想是
患者,50岁,男,原有慢性阻塞性肺疾病,呼吸困难、发绀,近日咳嗽加剧,突然发生右侧胸痛,约30分钟后呼吸困难突然加剧,患侧胸壁叩诊呈鼓音,听诊呼吸音消失。该变化是
婴儿腹泻伴低钾血症时错误的治疗是
有机磷农药中毒患者最早出现的症状是
在房地产估价中,长期趋势法运用的假设前提是()。[2006年考题]
可转让信用证和背对背信用证一样,都有两个受益人,两家开证行。
A企业委托B企业(A、B企业均为增值税一般纳税人,增值税税率17%)加工应税消费品一批,发出材料成本67.5万元,支付给B企业加工费用4.5万元,由B企业代收代缴的消费税税率为10%,材料已经加工完毕验收入库,用于直接销售。该委托加工物资加工后的入库成本是
在我国,公安机关是国务院和地方各级人民政府领导下的一个职能部门,是国家行政机关的重要组成部分。但公安机关不同于普通的行政机关,因为()。
在Windows系统中,默认权限最低的用户组是()。
最新回复
(
0
)