首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知某个序列存在“中值记录”,我们将其定义为:如果将此序列排序后,它是第n/2个记录。对于任意一个序列求出其“中值记录”。 请回答下列问题: (1)给出算法的主要思想; (2)根据设计思想,采用C或C++或JAVA语言表述算法,关键之处给出注释
已知某个序列存在“中值记录”,我们将其定义为:如果将此序列排序后,它是第n/2个记录。对于任意一个序列求出其“中值记录”。 请回答下列问题: (1)给出算法的主要思想; (2)根据设计思想,采用C或C++或JAVA语言表述算法,关键之处给出注释
admin
2014-07-18
30
问题
已知某个序列存在“中值记录”,我们将其定义为:如果将此序列排序后,它是第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
学硕统考专业
相关试题推荐
试析19世纪60年代列强对华政策的变化原因。(北京大学2006年中国通史真题)
“百日维新”的主要内容是什么?如何评价?
中古时代实行索贡巡行赋税征收方式的国家是()。
《凡尔赛和约》中,战胜国以何种方式处置德国的全部海外殖民地?()。
印度孔雀帝国时代,就土地占有情况而言,占全国土地的绝大部分的是()。
()用铜制造了人体模型,并统一了人体的穴位。
阅读下列材料,并结合所学知识回答问题:材料一重申粮食垄断和价格都是不可更改的,重申必须同粮食投机商进行无情斗争,同时责成每一者,必须在本法令公布后一周内,把超过播种田地和自己到下次收获前的定额消费量的全部余粮呈报交售,呈报的办法由粮
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
假定在一个处理机上执行的操作如下:作业估计服务时间片优先数A103B11C23D14E52这些
设某多道程序系统中有用户使用内存1000M,打印机1台。系统采用可变分区动态分配算法管理内存,而对打印机采用静态分配。假设输入输出操作时间忽略不计,采用最短剩余时间优先的进程调度算法,进程最短剩余时间相同时采用先来先服务的算法,进程调度时机选择在进程执行结
随机试题
论述悲剧的特点。
在委托监理的工程项目中,监理单位不具有( )的权力。
【背景资料】某道路工程属城市次干路,长3800m,路宽16.5m,位于城市环路以内,设计结构为:30Cm厚9%石灰土处理土基,12%石灰土底基层,35Cm水泥稳定碎石基层,12Cm沥青混凝土面层。施工项目部编制施工组织设计后,做了一些必要的技术准备工作
金属螺旋管道进场时,应检查和检验的项目有()。
某投资方案需原始投资30000元,投资后各年现金净流量分别为12000元、15000元、10000元,则该方案的投资回收期为()年。
“绿色GDP”是指从GDP中扣除自然资源耗减价值和环境污染损失价值后的国内生产总值,我国提出使用“绿色GDP”概念的主要目的是()。
关爱“空巢老人”的活动开始后不久。媒体就反映此项活动的工作人员滥用款项,大吃大喝,并和保健品公司合作推销保健品给老人。你是这项活动的负责人,此时你会怎么处理?
商场促销前先将商品提价20%,再实行“买400送200”的促销活动(200元为购物券,使用购物券时不循环赠送)。则在促销期间,商品的实际价格是不提价前商品原价格的
8259A两级级联情况下,可管理的中断源最多为______级。
Prevailingmythologyhasitthatcreativityistheexclusivedomainofartists,scientists,andinventors—agiftednessnotavail
最新回复
(
0
)