首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2016-03-29
66
问题
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
选项
答案
将n个元素对称比较,即第一个元素与最后一个元素比较,第二个元素与倒数第二个元素比较……比较中的小者放前半部,大者放后半部,用了n/2次比较。再在前后两部分中分别简单选择最小和最大元素,备用(n/2)一1次比较。总共用了(3n/2)一2次比较。显然,当n≥3时,(2n一3)>(3n/2)一20 用分治法求解再给出另一参考答案。 对于两个数x和y,经一次比较可得到最大值和最小值;对于三个数x,y,z,最多经3次比较可得最大值和最小值;对于n个数(n>3),将分成长为n一2和2的前后两部分A和B,分别找出最大者和最小者:Max A,Min 4,Max B,MinB,最后Max={Max A,Max B}和Min={Min A,Min B}。对A使用同样的方法求出最大值和最小值,直到元素个数不超过3。 设C(n)是所需的最多比较次数,根据上述原则,当孔>3时有如下关系式: [*] 通过逐步递推,可以得到:C(n)=(3n/2)一2。显然,当n>3时,2n一3>(3n/2)一2。事实上(3n/2)一2是解决这一问题的比较次数的下限。
解析
转载请注明原文地址:https://kaotiyun.com/show/GnRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
赫尔岑和车尔尼雪夫斯基是()的杰出代表人物。
标志着国民党反动统治建立的事件是()。
三国时期,魏、蜀、吴灭亡的先后顺序是()。
1941年8月14日,罗斯福和丘吉尔发表了(),表示了反对纳粹暴政的决心,这是反法西斯同盟建立过程中的重要一环。
最早测量子午线的长度,并主持修订了当时最先进历法《大衍历》的是僧人()。
关于垄断组织的积极作用,不正确的说法是()。
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
“二战期间,美国研制了原子弹并用于实践;1946年美国投入的第一台电子计算机最初是用于计算炮弹弹道;德国人研制成功的远程液体火箭是用于空袭英国的。”以上史实说明()。
编写一个算法,实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
一个磁盘有N个磁道,寻道时每移过一个磁道耗时T秒,文件相邻的数据块在磁盘上存放的位置平均相隔13个磁道,磁盘旋转延时平均R秒,每个存储块的传输时间为P秒,在这种情况下,传输100个数据块需要的时间是()。
随机试题
表中(?)处应填入的数字是:
试分析圆盘凸轮加工中的顺逆铣和端面凸轮铣削中引起“凹心”现象的原因。
根据我国法律中关于法律规避的规定,下列说法正确的是:
业主方进度控制的任务是控制( )的工作进度。
位于市区的A有限责任公司2018年发生以下业务:(1)年初,无偿使用B股份有限公司的一处闲置房产作为生产经营用房,该房产计税余值为610万元,市场价值700万元;同类房产市场租赁费为每年20万元(B公司未缴纳该房产的房产税)。(2)4月1日,购入乘用车
下列抽样风险中,可能导致降低审计效率的有()。
大量饮用清水后,尿量增多的原因是:
Thiskindofanimalsareonthevergeofextinction,becausesomanyarebeingkilledfortheirfur.
BluejeansareprobablythesinglemostrepresentativearticleofAmericanclothing.Theywereoriginally【C1】______byJacobDavi
A.ambitiousB.appealstoC.contactsD.expectE.easilyF.worksG.consulting
最新回复
(
0
)