首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2017-11-14
26
问题
对一个由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={MaxA,Max B}和Min={Min A,MinB}。对A使用同样的方法求出最大值和最小值,直到元素个数不超过3。 设C(n)是所需的最多比较次数,根据上述原则,当n>3时有如下关系式: [*] 通过逐步递推,可以得到:C(n)=(3n/2)一2。显然,当n>3时,2n一3>(3n/2)一2。事实上(3n/2)一2是解决这一问题的比较次数的下限。
解析
转载请注明原文地址:https://jikaoti.com/ti/BDfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列对第三次科技革命推动了国际经济格局调整的叙述,不正确的是()。
清末新政未能挽救清朝灭亡命运的根本原因是()
西汉末年,()对太初历作了系统的解释,并调整为三统历。这是中国第一部记载完整的历法。
1936年,德奥双方通过(),德国基本上控制了奥地利的内政和外交。
下列哪个文件标志着“文化大革命”的发起?()
德国纳粹党消灭资产阶级民主制的关键性事件是()。
三国时期,魏、蜀、吴三国灭亡的历史顺序是()。
基辅罗斯国家对居民征税的方式是()。
在一个HDLC帧的数据中,如果出现了000111111011这样的流,请问发送到信道上它将会变成()。
下列排序算法中,时间复杂度为O(nlogn)且占用额外空间最少的是()。
随机试题
某药厂以本厂过期药品作为主原料,更改生产日期和批号生产出售。甲市乙县药监局以该厂违反《药品管理法》第49条第1款关于违法生产药品规定,决定没收药品并处罚款20万元。药厂不服向县政府申请复议,县政府依《药品管理法》第49条第3款关于生产劣药行为的规定,决定维
患者,女性,30岁。患胃溃疡6年,近2个月疼痛加重,节律不定,伴乏力,服用奥美拉唑等多种药物,效果差。查体:精神欠佳,浅表淋巴结无肿大,心肺(-),腹平软,上腹部压痛,可扪及包块。最可能的临床诊断是()。
A______(psychology)issomeonewhostudiesthehumanmind,humanemotionsandhumanbehavior.
四神丸的组成药物中含有()
下列选项中,不属于风能特点的是()。
Butthesuccessofscience,bothitsintellectualexcitementanditspracticalapplication,dependsupontheself-correctingcha
简述合同承受应具备的条件。
(2010上集管)在项目人力资源计划编制中,一般会涉及到组织结构图和职位描述。其中,根据组织现有的部门、单位或团队进行分解,把工作包和项目的活动列在负责的部门下面的图采用的是______。
Don’tdisturbme.I______lettersallmorningandhavewrittenfive.
PartⅡReadingComprehension(SkimmingandScanning)Directions:Inthispart,youwillhave15minutestogooverthepassageq
最新回复
(
0
)