首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知某个序列存在“中值记录”,我们将其定义为:如果将此序列排序后,它是第n/2个记录。对于任意一个序列求出其“中值记录”。 请回答下列问题: (1)给出算法的主要思想; (2)根据设计思想,采用C或C++或JAVA语言表述算法,关键之处给出注释
已知某个序列存在“中值记录”,我们将其定义为:如果将此序列排序后,它是第n/2个记录。对于任意一个序列求出其“中值记录”。 请回答下列问题: (1)给出算法的主要思想; (2)根据设计思想,采用C或C++或JAVA语言表述算法,关键之处给出注释
admin
2014-07-18
34
问题
已知某个序列存在“中值记录”,我们将其定义为:如果将此序列排序后,它是第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://jikaoti.com/ti/IRajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
反映查理大帝进攻阿拉伯人控制的西班牙的文学作品是()。
1938年,英、法、德、意在德国召开会议讨论对捷克斯洛伐克的苏台德地区的问题,这次会议被称为(),它把英法的绥靖政策推到了顶峰,加速了二战的爆发。
下列关于胡司战争的叙述错误的一项是()。
帝国前期罗马文化吸收了许多民族的文化成果,进入了兴盛时代。其中自然科学方面最有代表性的人物是()。
《凡尔赛和约》中,战胜国以何种方式处置德国的全部海外殖民地?()。
()的设置是清王朝实行满汉联合、以汉制汉统治方式在军事上的具体体现
东欧国家的私有化方式一般有四种,其中波兰采取的主要方式是()
近代自然科学产生的条件及其发展情况。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
某机字长32位,主存容量32MB,按字节编址;该机的Cache采用4路组相联映射方式,Cache容量为16KB,块长为4个字,试回答下列问题:(1)主存地址位数为多少?(2)画出主存地址格式示意图,注明各字段名称及位数。(3)设该Ca
随机试题
机体组主要包括:()、()、()、油底壳等。
Youcannotseethepatientatthemomentheisnow__________medicaltreatment.
结核病的原发综合征典型的X线胸片表现的是:
下列诱发恶性高热的概率最小的是()。
甲公司签发了一张银行承兑汇票,银行进行了承兑,乙公司和丙公司在汇票上记载了“保证”字样并签章,注明各承担50%的保证责任,但是未记载被保证人名称。下列说法正确的是:()
室内消火栓如何分类?
Theteacher(A)toldus(B)thattheearth(C)ranaround(D)thesun.
某城市社区有一些居民家里的宠物经常在小区内随地大小便,引起了其他居民的不满,甚至发生过口角。社会工作者小赵决定运用地区发展模式来解决这个问题。下列小赵的做法中,较为适当的是()。
白居易在登上庐山时写下:“人间四月芳菲尽,山寺桃花始盛开”。产生诗中景象的原因是()。
Maryhaskeptworkingfortenhours.______,sheneedsarestnow.
最新回复
(
0
)