首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2017-11-14
54
问题
对一个由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
学硕统考专业
相关试题推荐
北庭都护府
希腊化时代控制希腊半岛的是()。
义和团爆发的直接原因是()。
洋务派创办军事工业的方式是()。
在欧盟发展历史上,促使欧盟正式成立的文件是()。
古希腊是西方文明的发源地,古希腊雅典的民主政治则开启了两方民主制度的先河。下列关于雅典民主政治的说法,符合史实的有()。①民主政治时期的雅典没有国王②公民大会是雅典国家的最高决策机构③伯里克利时期,雅典民主政治达到了顶峰④包括妇女在内的
陈云在哪次会议上发表了《目前财政经济的情况和克服困难的若干办法》的重要讲话?()
以下不属于国民党控制金融的“四行”的是()。
《凡尔赛条约》中,战胜国以()方式处置德国的全部海外殖民地。
一个字节多路通道连接D1、D2、D3、D4、D5共5台设备,这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求,请回答下列问题:(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字
随机试题
A.随机观察、会谈法B.定式访谈法C.定式观察法D.评定量表法E.心理测验
肺癌所致阻塞性肺炎有以下临床征象.除了
申请成为国家圃或专业圃的受理及审核机构均为直属检验检疫局。( )
下列税种中,属于财产税的是()。
心智技能与操作技能相比,具有()特点。
下面标点符号使用正确的一项是()。
在世界杯金靴奖的争夺中,如果斯内德没有获得金靴奖并且穆勒助攻次数比斯内德多的话,弗兰将获得金靴奖。补充以下哪项,能够推出斯内德获得了金靴奖?
设z=f(2x-y)+g(x,xy),其中函数f(t)二阶可导,g(u,v)具有二阶连续偏导数,求
Besides"American"characteristics-individualism,self-reliance,informality,punctualityanddirectness,therearealsosome"n
CurrentChallengesConfrontingU.S.HigherEducationThefirstchallenge:forceofthemarketplace•Currentsituation:—pr
最新回复
(
0
)