首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键宇取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键宇取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2017-01-04
50
问题
对一个由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,Min B,最后Max={Max A,Max B}和Min={Min A,Min B}。对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/qLRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述鸦片战争的三个阶段。
罗斯福新政被称为是“3R”改革即Recovery(复兴)、Relief(救济)、Reform(改革),其中能反映Relief方面的内容是()。
法西斯党在意大利、纳粹党在德国得以上台执政的共同因素不包括()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
判断英国工业革命基本完成的主要依据是()
《萨利克法典》提及法兰克人的一项犯罪申诉习惯。即任何必须以汤釜神判法,判定犯罪嫌疑人要用右手从沸水中取出指定物品,这表明当时法兰克王国
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:请说明系统并不一定死锁。
若系统中有五个并发进程涉及某个相同的变量A,则变量A的相关临界区是由()临界区构成。
随机试题
HowdoyouexplaineconomicsinplainEnglish?TheFederalReserveBankofNewYorkhasbeenansweringthequestionwithaneven
中国共产党在社会主义事业中起到的作用是
下列哪项不是中风中经络的主症()
以下属于危险、有害因素辨识与分析工作内容的是()。
下列关于破产费用与共益债务清偿的表述中,符合企业破产法规定的有()。
下列不属于幼儿园教育任务的是()。
但在众多借此批评中国U16国家队及中国足球的声音当中,还是下意识地隐藏着一种不恰当的“大国沙文主义足球观”,还是有些高看了中国足球几眼的意思在里头。
美国媒体分析,特朗普安排了大量的高级助手,这些助手很可能将会凌驾于内阁部长之上。而这个由高级助手们组成的影子内阁将在各联邦机关内贯彻白宫的意志。
以下关于《天朝田亩制度》和《资政新篇》的说法,正确的是()
筷子的使用要追溯到古时候,那时候大部分中国人还是农民。那些农夫不想用脏手拿取食物,也不想被烫着,所以就开始用小树枝(twig)来夹取食物。因为中国人从小就使用筷子,所以他们觉得筷子效率很高,用起来很简单。筷子有木制的、竹制的和塑料制的,通常用右手使用。筷子
最新回复
(
0
)