首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2023-02-06
64
问题
对一个由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,MinB,最后Max={Max A,MaxB}和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/uIwD777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
教育心理学常用的方法有()。
进行课程管理时,应该强化课程意识,提高学校课程建设与管理的功能,构建重基础、多样化、有层次、综合性的课程结构。()
一个好的教师必须挚爱自己的职业,对教学有极大的热情,这样他才可能积极地投入到教学工作中去。这体现了()是成为好教师的关键。
某学生总是倾向于选择难度适中的任务,通过完成挑战性任务来获得心理上的满足。这位学生的成就动机水平最可能是()。
通常来说,作业有课内和课外两种形式。教师在布置课外作业时要尽量做到“分量适中,难度要大”,以保证学生充分的休息时间和增加学生知识的储备。()
50.将符号所代表的新知识与学习者认知结构中已有的适当观念建立起非人为的、实质性的联系属于()。
习近平总书记在北京师范大学看望教师和学生时说:“一个人遇到好老师是人生的幸运,一个学校拥有好老师是学校的光荣,一个民族源源不断涌现出一批叉一批好老师则是民族的希望。”好老师关系到民族的振兴与发展,习近平总书记提出“四有”好老师,“四有”即有理想信念、有道德
如图所示,为测量珠穆朗玛峰上某点C的海拔高度,测量队选择了两个海拔高度相差100米的珠峰测量点A和B,测得∠ABC为90°,从A观测B、C的仰角分别为30°和45°,从B观测C的仰角也为30°,则C点的海拔高度比A点高:
根据以下资料,回答问题。(注:在职退休比指的是在职职工参保人数与退休职工参保人数之比)下列年份中,在职职工参保人数同比增速大小排序错误的是:
某军用加油站的储油罐装有甲、丙两条输入管和乙、丁两条输出管。要注满储油罐,单开甲管需要3天,单开丙管需要5天。要放空储油罐,单开乙管需要4天,单开丁管需要6天。现在储油罐内装有1/6罐油,如果按甲、乙、丙、丁的顺序轮流各开1天,那么注满储油罐需要(
随机试题
正常肾脏长轴与正中线夹角范围在
什么是内电路和外电路?
目前导致我国人群死亡的前10位疾病的病因和疾病危险因素中,比例最高的是
药品生产企业只能销售
A.血肌酐7.14mmol/LD.三者均是E.三者均不是肾功能不全代偿期()
自保险人向投保人签发保险单或者其他保险凭证时起,保险合同成立。( )
2012年安徽商业银行面试真题齐白石的话“学我者生,似我者死”,你怎么看?
普及历史知识,形式多种多样,可以是专业的史学论著,可以是各种形式的历史讲座,也可以是影视剧。但在多种多样的形式中,有一点应是_______的,即在处理历史题材、普及历史知识的时候需要尊重历史真实,需要对历史发展的大势抱有_______之心,而不能_____
Manywilldoubttobaccoindustryclaimsthatitissharpeningitssciencetoevaluate"healthiercigarettes".Butthat’swhatwi
Mostpeoplemanagetoreturnfromtheirholidayswithacoupleofamusinganecdotes.Notmanywilladmitthey’vehadabadtime.
最新回复
(
0
)