首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2019-08-15
31
问题
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
选项
答案
将n个元素对称比较,即第一个元素与最后一个元素比较,第二个元素与倒数第二个元素比较……比较中的小者放前半部,大者放后半部,用了n/2次比较。再在前后两部分中分别简单选择最小和最大元素,各用(n/2)一1次比较。总共用了(3n/2)一2次比较。显然,当n≥3时,(2n一3)>(3n/2)一2。 用分治法求解再给出另一参考答案。 对于两个数x和y,经一次比较可得到最大值和最小值;对于三个数x,y,z,最多经3次比较可得最大值和最小值:对于n个数(n>3),将分成长为n一2和2的前后两部分A和B,分别找出最大者和最小者:Max A,Min A,Max B,Min B,最后Max={Max A,Max B}和Min={Min A,Min B}。对A使用同样的方法求出最大值和最小值,直到元素个数不超过3。 设C(n)是所需的最多比较次数,根据上述原则,当n>3时有如下关系式: [*] 通过逐步递推,可以得到:C(n)=(3n/2)一2。显然,当n>3时,2n一3>(3n/2)一2。事实上(3n/2)一2是解决这一问题的比较次数的下限。
解析
转载请注明原文地址:https://kaotiyun.com/show/VKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
唐玄宗前期设置的藩镇不仅后来使唐朝走向衰落,而且对后来的历史产生了严重影响。据此回答问题下列有关唐朝后期藩镇割据局面形成原因的表述,不正确的是()
关于一战后构筑的凡尔赛体系,说法不正确的是()。
某激光打印机每分钟打印20页,每页4000字符,相应的设备驱动程序一次输出一个字符,采用中断方式,CPU处理每次中断需50微秒,则CPU用于打印的开销是()。
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,-1,4,-4,…,j2,-j2(j<=m/2)。当di>0时,Hi=(H(key)+di)%m当di<0时,Hi=(H(key)+di+m)%m散列
编写一个算法,实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
在下列查找的方法中,平均查找长度与结点个数n无关的查找方法是()。
描述滑动窗口机制及其作用。比较停止一等待协议,多帧滑动窗口和后退N帧协议,多帧滑动窗口与选择重传协议的区别。
设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素,a[0][O]的存储地址为860,则a[3][5]的存储地址为()。
下图是三个计算机局域网A,B和C,分别包含10台,8台和5台计算机,通过路由器互联,并通过该路由器接口d联入因特网。路由器各端口名分别为a、b、c和d(假设端口d接入IP地址为61.60.21.80的互联网地址)。LANA和LANB公用一个C类IP地址
假设有一个进程拥有两个线程(编号为0和1)需要去访问同一个共享资源,为了避免竞争状态的问题,必须实现一种互斥机制,使得在任何时候只能有一个线程在访问这个资源。假设有如下的一段代码:intflag[2];/*flag数组,初始化为FALSE*/
随机试题
患者,男,45岁。2周前体检发现ALT升高,为进一步诊治来诊。此患者处理1.必须住院治疗2.大量输液及保肝药3.食管及胃底曲张静脉硬化治疗4.大量进食蛋白食物5.抗HBV治疗6.不须抗HBV治疗7.应用干扰素治疗8.应用核苷(酸)类似物
A.朱砂B.磁石C.龙骨D.酸枣仁E.柏子仁具有养心安神,收敛止汗功效的药物是
下列关于期货公司期货投资咨询业务利益冲突防范的说法,错误的是()。
根据《商业银行个人理财业务风险管理指引》的要求,下列相关描述正确的有()。
某公司2012年发生以下应税项目:(1)与甲公司签订一份加工承揽合同,受托为其加工一批产品,原材料价值80万元、辅助材料价值2007年由公司提供,向甲企业收取加工费30万元,各项金额均在加工承揽合同中分别记载。(2)与乙企业签订一份建筑工程承包合同,记
下列关于诉讼时效起算的说法中,错误的是()。
下图中,图甲表示光照和CO2浓度对某植物光合速率的影响,图乙表示该植物夏季连续两昼夜对CO2吸收量和释放量的变化曲线图,S1~S2表示曲线与横轴围成的面积。请据图回答问题。若48小时内该植物能生长,则应满足的条件是_________(用S1~S5表示
“民为贵,社稷次之,君为轻”这一思想的提出者是()。
“万夫一力,天下无敌”说的就是团结。团结出凝聚力,出生产力,出战斗力.团结可以战胜艰难险阻,创造人间奇迹。一个组织的成员只有团结一致,这个组织才能高效率地运作:一个组织的成员如果能团结一致,也就一定能产生超出各个体之和的整体效益。由此可以推出:
(2011年河北.7)去年李文同学参加市作文大赛,名落孙山,他很沮丧。语文老师对他只说了一句话:“这会过去的。”今年,李文同学又参加市作文大赛,获得一等奖,他可高兴了。这时语文老师还是对他只说了一句话:“这会过去的。”对这段文字理解准确的是(
最新回复
(
0
)