首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2017-11-14
53
问题
对一个由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://kaotiyun.com/show/P3Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
《齐民要求.序》中写道:“今采摭经传,爰及歌谣,洵之老成,验之行事,起自农耕,终于醯醢(酱醋),资生之靡不毕书书;号日《齐民要术》……舍本逐末,贤哲所非……故商贾之事,阙而不录。”这段材料表明作者()。①采取古今资料的编撰原则②
中华人民共和国恢复了在联合国合法席位的时间是()。
第二次工业革命引起的生产关系方面最突出的变化是()。
1936年,德奥双方通过(),德国基本上控制了奥地利的内政和外交。
下列关于第二三次科技革命的说法,不正确的是()。
阅读材料,回答以下问题:一、大清帝国之皇统,万世不易。二、皇帝神圣,不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序,于宪法规定之。五、宪法由资政院起草议决,皇帝颁布之。六、宪政改正提案权,属于国会。七、上院议员,由国民于法定特别资格公选之。八、总
西汉初年,反驳刘邦“马上治天下”的说法,并向汉帝国治国献策的是()。
美国首次提出争夺世界霸权的纲领性文件是()。
材料一材科二(戈尔巴乔夫政府)在制定改革政策方针中存在三个严重问题:第一,仍然以优先发展重工业和机器制造业为主的“加速发展战略”作为发展资本密集型产业的主要战略,已不符合时代潮流。现代经济结构已由资本密集型向技术密集型发展……苏联的经济改革对
晚清时期清帝年号的正确排序是
随机试题
下列属于战国时期的是()
生物朝不同方向进化的“对策”称为( ),也称( )。
A.山茱萸B.桑螵蛸C.海螵蛸D.诃子E.芡实性微温,主治妇女崩漏及月经过多的药物是
A公司发行了优先股,面值1元,并约定按票面股息率10%支付股息,投资人的必要报酬率为17%,则每股优先股的价值为()元。
简述儿童活动过度与儿童多动症的区别。
AccordingtoarecentGallupWorldPoll,1.1billionpeople,orone-quarteroftheearth’sadults,wanttomovetemporarilytoa
A—FreeDeliverytoYourDoorB—TollGateC—NoEntryD—StrictlyNoParkingE—Lugga
Psychologiststakeopposingviewsofhowexternalrewards,fromwarmpraisetocoldcash,affectmotivationandcreativity.Beha
A、680yearsago.B、Hundredsofyearsago.C、Inthe19thcentury.D、ThedaywhenEnglandcolonized.C事实细节题。女士提到在八所常春藤学校中七所都成立于几百年
InonesceneofModernTimes,CharlieChaplinwasshowntrying______tokeepintimewitharapidassemblyline.
最新回复
(
0
)