首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2017-11-14
62
问题
对一个由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
学硕统考专业
相关试题推荐
《颜氏家训》
中共八届九中全会提出的恢复和调整国民经济的方针是()。
年鉴学派开创了总体史研究方法,其代表人物马克·布洛赫研究中世纪的代表作是()
()是二战后一个调整各国贸易关系的法律框架,又是一个进行多边贸易谈判、争夺市场的场所,还是一个调解和解决争议的机构。
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
古埃及第24朝法老波克利斯进行改革,宣布废除奴隶制,债权人只能索取债务人的财产作抵偿,而不能占有债务人的人身,因为财产属于个人,而公民人身属于国家,国家需要他们服役。该改革旨在
一个使用选择性重传协议的数据链路层协议,如果采用了5位的帧序列号,那么可以选用的最大窗口是()。
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
某计算机字长16位,采用16位定长指令字结构,部分数据通路结构如下图所示。图中所有控制信号为1时表示有效、为0时表示无效。例如控制信号MDRinE为1表示允许数据从DB打入MDR,MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一直处于使能状
下列排序算法中,时间复杂度为O(nlogn)且占用额外空间最少的是()。
随机试题
郑某等人多次预谋通过爆炸抢劫银行运钞车。为方便跟踪运钞车,郑某等人于2012年4月6日杀害一车主,将其面包车开走(事实一)。后郑某等人制作了爆炸装置,并多次开面包车跟踪某银行运钞车,了解运钞车到某储蓄所收款的情况。郑某等人摸清运钞车情况后,于同年6月8日将
设A是m×n的非零矩阵,B是n×l非零矩阵,满足AB=0,以下选项中不一定成立的是()。
图示三铰支架上作用两个大小相等、转向相反的力偶m1和m2,其大小均为100kN·m,支架重力不计。支座B的反力RB的大小和方向为( )。
能反映一个组织系统中各项工作之间逻辑关系的组织工具是()
某连锁娱乐企业是增值税一般纳税人,主要经营室内游艺设施。2021年11月经营业务如下:(1)当月游艺收入价税合计636万元,其中门票收入为300万元、游戏机收入为336万元。当月通过税控系统实际开票价款为280万元。(2)当月以融资性售后回租形式融资,
1990年,我们党的十四大报告进一步系统地阐述了建设有中国特色社会主义理论的主要内容。( )
根据《合同法》规定,违反合同一方要承担违约责任,下列不属于承担违约责任方式的是()。
8个人比赛国际象棋,约定每两人之间都要比赛一局,胜者得2分,平局得1分,负的不得分。在进行了若干局比赛之后,发现每个人的分数都不一样。问最多还有几局比赛没比?()
数据字典是各类数据描述的集合,它通常包括5个部分,即数据项、数据结构、数据流、【】和处理过程。
Lightlevelsarecarefullycontrolledtofallwithinanacceptablelevelfor______readingconvenience.
最新回复
(
0
)