首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2017-11-14
90
问题
对一个由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
学硕统考专业
相关试题推荐
苏联解体、东欧剧变的根本相同原因是()。
西汉末年,()对太初历作了系统的解释,并调整为三统历。这是中国第一部记载完整的历法。
明成祖时期大力推崇理学,以国家力量编写了几部理学的大部头著作,下面不属于其中的是()。
阅读材料,回答以下问题:一、大清帝国之皇统,万世不易。二、皇帝神圣,不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序,于宪法规定之。五、宪法由资政院起草议决,皇帝颁布之。六、宪政改正提案权,属于国会。七、上院议员,由国民于法定特别资格公选之。八、总
1534年英国议会宣布英国教会断绝与罗马教廷一切关系的文件是()。
阅读材料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合理解决,
下面哪项条约没有涉及德国的赔款问题?()
宋代至清代我国书籍印刷的主要方式是()
西周的官僚制度已经相当完备,官僚机构庞杂,职官名目繁多。周王室的官僚机构分为两大系统,分别是()。
某机字长32位,总线数据线宽度是16位,一个总线周期占用4个时钟周期,总线时钟频率为10MHz,则总线带宽是()。
随机试题
电磁流量计电源的相线和中线,励磁绕组的相线和中线以及变送器输出信号端子线是不能随意对换的。
在生产产品过程中发生的原材料、动力、职工薪酬等各种要素费用支出时,对于直接用于产品生产(指基本生产的产品)并且专门设有成本项目的费用,直接记入_________账户明细账中的“直接材料”、“燃料及动力”、“直接人工”等成本项目中。
治疗高渗性非酮症糖尿病昏迷,以下哪项措施是错误的
小管液中水的等渗性重吸收发生于
女,22岁,因肥胖闭经拟诊为多囊卵巢综合征。腹腔镜下检查卵巢主要表现有
除哪项外,均是车前子的功效
A、空腹静脉血糖B、空腹指尖血血糖C、糖化血红蛋白(HbAlc)D、葡萄糖耐量试验E、胰岛素释放试验调整胰岛素剂量最简便的检查是
建筑施工图包括()。[2007年考试真题]
A、B、C、D、A
抛锚式教学要求建立在有感染力的真实事件或真实问题的基础之上,也称为“基于问题的教学”,理论基础是建构主义教学理论。()
最新回复
(
0
)