首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2017-11-14
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={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
学硕统考专业
相关试题推荐
【胡司战争】南京大学2006年世界近现代史真题
毛泽东在《论持久战》中指出,中国抗日战争取得最后胜利最为关键的阶段是()。
1948年,南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法,其核心是()。
武昌起义()。①由同盟会直接领导②原计划被偶然因素打乱③其成功有深刻的社会原因④迅速的胜利潜伏着失败的危机
宁夏回族自治区的设立时间是()。
建立帝国财政收支总账和元首金库,直接控制和调节全国财政收支的是()。
洋务派创办军事工业的方式是()。
周王室的两大官僚系统是()。
某系统中n个相互独立的生产者进程为一个消费者进程提供数据,假设每个生产者提供的数据写入各不相同的缓冲区,且生产者写缓冲区的速度比消费者读缓冲区的速度快,则缓冲区个数的最优值应为()。
序列的“中值记录”指的是:如果将此序列排序后,它是第n/2个记录。试写出一个求中值记录的算法。
随机试题
下列信息中,属于钢材合格证上内容的有()。
“沧浪之水清兮,可以濯我缨。沧浪之水浊兮,可以濯我足。”这首楚国民歌名为【】
在“当地化压力低”的情况下,可能采取的全球竞争战略包括()
带蒂皮瓣移植术,适用于下列哪种类型的手外伤
A、上颌第一磨牙B、上颌第二磨牙C、下颌第二磨牙D、下颌第一磨牙E、上颌中切牙牙冠的相对颊黏膜上是腮腺导管口
龟鹿二仙膏之主要功用为生脉散之主要功用为
可转换公司债券一般要经股东大会或董事会决议通过才能发行,而且在发行时,应在发行条款中规定()。Ⅰ.转换期限Ⅱ.转换条件Ⅲ.转换利率Ⅳ.转换价格
_______,遥看瀑布挂前川。_______,疑是银河落九天。(唐.李白《望庐山瀑布》)
把下面的六个图形分为两类,使每一类图形都有各自的共同特征或规律,分类正确的一项是:
Hitchhiking(搭车旅游)WhenIwasinmyteens(十几岁)and20s,hitchhikingwasamainformoflong-distancetransport.Thekindnessor
最新回复
(
0
)