首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2016-03-29
76
问题
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
选项
答案
将n个元素对称比较,即第一个元素与最后一个元素比较,第二个元素与倒数第二个元素比较……比较中的小者放前半部,大者放后半部,用了n/2次比较。再在前后两部分中分别简单选择最小和最大元素,备用(n/2)一1次比较。总共用了(3n/2)一2次比较。显然,当n≥3时,(2n一3)>(3n/2)一20 用分治法求解再给出另一参考答案。 对于两个数x和y,经一次比较可得到最大值和最小值;对于三个数x,y,z,最多经3次比较可得最大值和最小值;对于n个数(n>3),将分成长为n一2和2的前后两部分A和B,分别找出最大者和最小者:Max A,Min 4,Max B,MinB,最后Max={Max A,Max B}和Min={Min A,Min B}。对A使用同样的方法求出最大值和最小值,直到元素个数不超过3。 设C(n)是所需的最多比较次数,根据上述原则,当孔>3时有如下关系式: [*] 通过逐步递推,可以得到:C(n)=(3n/2)一2。显然,当n>3时,2n一3>(3n/2)一2。事实上(3n/2)一2是解决这一问题的比较次数的下限。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/GnRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
同盟会影响下发生的第一次大规模武装起义的地点在()。
西巴比伦王国存在的时间很短,不足90年,其中哪位国王在位的40年是该国最强盛的时期。()
论述门户开放政策及其影响
列举二战全面爆发、扩大、进一步扩大及达到最大规模的标志性事件。
解析两个战场的地位、作用及相互关系。
以下关于阿兹特克文化的叙述,不正确的是()。
洪秀全以宗教手段组织起义,主要利用的是()。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
三类线程search、insert、delete共享(访问)单链表,利用P、V原语操作实现这三类线程。限定如下:(1)search可以与同类线程同时执行;(2)insert类线程之间互斥,但是可以与任意多search同时执行;(3)del
假定变量i、f和d的数据类型分别为int、float和double(int用补码表示,float和double分别用IEEE754单精度和双精度浮点数格式表示),已知i=785,f=1.5678e3,d=1.5e100。若在32位机器中执行下列关系表达式,
随机试题
A、压腹试验B、压颈试验C、脑血管造影D、透视E、椎管穿刺能提示椎管有不同程度的阻塞的是()
社区卫生服务利用以前的调查数据时需注意
通常把系统开发过程分为()。
承包方提出的索赔事件的成立条件是()。
甲公司因无法偿还乙公司(股份有限公司)4000万元货款,于2016年8月1日与乙公司签订债务重组协议。协议规定甲公司通过增发1700万股普通股(每股面值1元)抵偿上述债务,股票发行价为2800万元。乙公司已对该应收账款计提了360万元坏账准备,并将取得的股
毫无疑问,在今日武断批判中医的人中。不乏以“科学”代言人自居者,将各种自己不懂的知识系统一棍子打死,归入__________。这种态度不能不使人怀疑其言论与知识的讨论无关,另有用意。不过,在抗拒这种学霸的同时,我们也不必非要陷入相反的__________。
2010年8月15日是中国人民抗日战争胜利65周年纪念日。()
在直径为D的大圆内作两两外切的n个小圆,小圆的圆心都在大圆的同一直径上,两端的小圆又分别内切于大圆(如图5所示是n=4的情形).若第k个小圆的周长为lk,则().
TheOnlyWayIsUpThinkofamoderncityandthefirstimagethatcomestomindistheskyline.Itisfullofgreatbuildin
"Themoregadgetsthereare,the【C1】______thingsseemtoget."saidHonoreErvin,co-authorofTheEtiquetteGirls:ThingsYou
最新回复
(
0
)