首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键宇取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键宇取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2017-01-04
65
问题
对一个由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,MaxB,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/qLRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述从十月革命胜利到第二次世界大战爆发前夕苏俄(苏联)与主要资本主义国家关系演变的基本情况。
论述15世纪以后美洲作物在中国和欧洲的传播及影响。(2013年统考真题)
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
光绪元年七月,清政府迫于()强烈要求派一位使臣到其国,()成为中国第一个驻外公使
元代南戏发展很快,涌现出所谓的“四大传奇”,下列选项不属于其中的是()。
阅读材料,回答以下问题:一、大清帝国之皇统,万世不易。二、皇帝神圣,不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序,于宪法规定之。五、宪法由资政院起草议决,皇帝颁布之。六、宪政改正提案权,属于国会。七、上院议员,由国民于法定特别资格公选之。八、总
中古时代实行索贡巡行赋税征收方式的国家是()。
文艺复兴时期,古典文化成为人文艺术家乐于表现的题材。梵蒂冈宫系列壁画中,描绘古典哲学家聚集一堂的作品是()
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
计算机系统中,判断是否有中断事件发生的时机是()。
随机试题
斜方肌上束的主要功能是()。
妊娠高血压综合征的基本病理变化是()。
患者,男,50岁。突起呼吸困难,咳粉红色泡沫痰,血压25.3/13.3kPa(190/100mmHg)该患者的最佳治疗药物是()
中央处理器的重要作用是运算和显示。()
(操作员:刘主管;账套:101长套;操作日期:2015年1月1日)新增付款条件。付款条件编码:60D付款条件名称:60天到期日期(天):60
甲事业单位为财政全额拨款的事业单位,自2005年起,实行国库集中支付和政府采购制度。经财政部门核准,甲事业单位的10万元以上的物品和服务采购支出实行财政直接支付方式,10万元以下的物品和服务采购支出以及日常零星支出实行财政授权支付方式。甲事业单位需要采购一
历史与现实证明,________。纵观近年来世界各地的纷争,从西亚北非推倒“多米诺骨牌”到美国政府一度停摆,从伦敦、巴尔的摩街头火光冲天的骚乱到极端势力的暴行震惊世界,各国政治危机的相似之处就在于,共识缺失加剧社会裂痕,最终陷入动荡失序。而中国从破除计划经
以下是李丽测量荔枝质量、密度时的若干操作,如下图所示,请你帮助她完成以下实验:测量荔枝质量前,将天平放在水平桌面上,游码移至标尺的______处.
Twofactorsweighheavilyagainsttheeffectivenessofscientificresearchinindustry.Oneisthegeneralatmosphereofsecrecy
A、Itshowsthestructureoftheearth.B、Itleadstonewchanges.C、Itmaynotbetrue.D、Itisanimportantrevolutioninscien
最新回复
(
0
)