首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知某个序列存在“中值记录”,我们将其定义为:如果将此序列排序后,它是第n/2个记录。对于任意一个序列求出其“中值记录”。 请回答下列问题: (1)给出算法的主要思想; (2)根据设计思想,采用C或C++或JAVA语言表述算法,关键之处给出注释
已知某个序列存在“中值记录”,我们将其定义为:如果将此序列排序后,它是第n/2个记录。对于任意一个序列求出其“中值记录”。 请回答下列问题: (1)给出算法的主要思想; (2)根据设计思想,采用C或C++或JAVA语言表述算法,关键之处给出注释
admin
2014-07-18
60
问题
已知某个序列存在“中值记录”,我们将其定义为:如果将此序列排序后,它是第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
学硕统考专业
相关试题推荐
两极格局终结的原因、标志及影响是什么?
1948年,南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法,其核心是()。
火的使用,是人类在征服自然过程中所取得的伟大成果。开始使用天然火是在()。
国共合作之后,红军改编为八路军,其中原是红四方面军的是()
波兰三次被瓜分的时间是()
斯蒂文逊负责勘测和修建的世界上的第一条公共交通铁路通车于()。
下列选项中,不是由晁错提出的是()
二战后,美国以经济手段扶植和控制西欧的表现是()。
“时方镇缺守帅,稍命文臣权之……又置转运使、通判,为之条禁,文薄渐为精密,由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
随机试题
心房纤颤发生后至少可使心排血量下降
A、《黄帝内经》B、宋国宾《医业伦理学》C、孙思邈《备急千金要方》D、希波克拉底《希波克拉底誓言》E、帕茨瓦尔《医学伦理学》奠定西方医学人道传统的文献是
关于物资需求计划的说法,正确的是()。
根据《注册建造师管理规定》,注册建造师的下列行为违法的有()。
下列哪一条符合儿童动作发展的规律()
14世纪欧洲学校的课程有算数、几何、天文等,到16世纪增加了地理和力学,17世纪又增加代数、三角、物理和化学等。这说明对教学内容变化产生影响的是()
设矩阵A、B的行数都是m.证明:矩阵方程AX=B有解的充分必要条件是r(A)=r(A┆B).
下列关于世界上第一台电子计算机ENIAC的叙述中,错误的是()。
FoodandYourLifeStagesThenutritionalneedsofthehumanbodychangeatdifferentlifestages.Tobefitandhealthy,it
HowtoBuildTeamSpiritandGetBestSalesPerformanceA)Itisawell-knownfactthatanorganisationcanachieveagreatersuc
最新回复
(
0
)