首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知某个序列存在“中值记录”,我们将其定义为:如果将此序列排序后,它是第n/2个记录。对于任意一个序列求出其“中值记录”。 请回答下列问题: (1)给出算法的主要思想; (2)根据设计思想,采用C或C++或JAVA语言表述算法,关键之处给出注释
已知某个序列存在“中值记录”,我们将其定义为:如果将此序列排序后,它是第n/2个记录。对于任意一个序列求出其“中值记录”。 请回答下列问题: (1)给出算法的主要思想; (2)根据设计思想,采用C或C++或JAVA语言表述算法,关键之处给出注释
admin
2014-07-18
59
问题
已知某个序列存在“中值记录”,我们将其定义为:如果将此序列排序后,它是第n/2个记录。对于任意一个序列求出其“中值记录”。
请回答下列问题:
(1)给出算法的主要思想;
(2)根据设计思想,采用C或C++或JAVA语言表述算法,关键之处给出注释;
(3)总结所用算法的时间和空间复杂度。
选项
答案
(1)为了获取中值记录,我们将数组中的元素分成两组,一组是比当前记录大的数值,另外 一组是小于当前记录的数值。如果两组记录的数据数目相等或是最为接近,那么当前记录 即为要找的中值记录。 (2)算法的实现函数: ty pedef struct{ int g;//大于该记录的个数 int t;//小于该记录的个数 }place; im Get—Mid(int a[],int n){//获取中值记录的函数 place b[MAXSIZE]; /*对第i个元素统计比它大和比它小的元数的个数,分别为g和t*/ for(int i=0;i
a[i])b[i].g++; if(a[j]
2),算法实现过程中使用的辅助空间为数组,空间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/W4xi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
都江堰是闻名世界的防洪灌溉工程,负责这一工程的是()。
《凡尔赛和约》的内容最能反映巴黎和会性质的是()。①德国在中国山东的特权转给日本②对德国军备严格限制③莱茵河西岸由协约国军队占领15年④以“委任统治”形式瓜分德国海外殖民地
二战后,美国以经济手段扶植和控制西欧的表现是()。
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
“时方镇缺守帅,稍命文臣权之……又置转运使、通判,为之条禁,文薄渐为精密,由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。
以北宋三大发明为例简述北宋科学技术的特征。
简述当代科学技术革命兴起的背景、特点及影响。
最早测量子午线的长度,并主持修订了当时最先进历法《大衍历》的是僧人()。
下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削,工匠的人身依附关系加强
某计算机的CPU主频为500MHz,CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s,采用中断方式与主机进行数据传送,以32位为传输单位,对应的中断服务程序包含18条指令,中断服务的其他开销相当于2条指令的执行时间
随机试题
简述通信卫星处理转发器的工作原理。
男性,60岁。2年前曾因脑梗死住院治疗,此后常进食呛咳,1周前出现咳嗽、咳痰。体检:双下肺可闻及湿啰音,胸片示双下肺肺炎该患者主要是哪项呼吸防御功能受损
性格是指
有关钙拮抗剂对心肌的作用,不正确的是
闭经的分类中不包括
建设工程法律法规规章的效力顺序从高到低的顺序依次为()。
可用于液下喷射方式扑救大型储油罐火灾的泡沫灭火系统为()。
掷一个骰子实验,事件A表示“小于5的偶数点出现”,事件B表示“小于5的点数出现”,则事件发生的概率为()。
Therearetwomethodsoffighting,theonebylaw,theotherbyforce;thefirstmethodisthatofmen,thesecondofbeasts;an
Peopleinallpartsoftheworldare【B1】______."NoTobaccoDay".ItisthedaywhentheWorldHealthOrganizationappeals
最新回复
(
0
)