对一个由n个关键字不同的记录构成的序列，能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?

admin2023-02-06 51

问题对一个由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，MinB，最后Max={Max A，MaxB}和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/uIwD777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

对一个由n个关键字不同的记录构成的序列，能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?

计算机408

学硕统考专业

为了便于学校管理和体现公平，学校应制订共性的统一的要求，以相同的模式要求学生。()

2012年7月1日实施的《党政机关公文格式》规定，公文中成文日期的书写用阿拉伯数字将年月日标全。()

十八届四中全会指出，健全依法决策机制，就是要把公众参与、专家论证、风险评估、合法性审查、集体讨论决定确定为重大行政决策法定程序。()

课程设计就是对课程的各种内容进行组织与开发。教师按照课程设计的总体思路，对某一个年级或几个年级设置的各门学科课程的内容，严格按照排定的课题顺序一个接一个地进行下去的课程设计方式是()。

关于传播的定义，大体上可分为哪几种类型?

国际商务谈判中的技术风险包括()

设函数z=x4—2xy+y2+1，则=_________．

在PowerPoint2010中，不能完成对个别幻灯片进行设计或修饰的是()

心理活动的内容来自于

A．牛蒡子B．龟甲C．天南星D．自然铜E．琥珀处方直接写药名，需调配清炒品的是

某公司准备向不特定对象发行证券，下列发行计划必须由承销团承销的是()。

根据对外贸易法律制度的规定，下列关于临时反倾销措施的表述中，正确的有（）。

Ourresultswereinconsistent.Theprogramobviouslycontainsanerror.Arevisionoftheprogramisrequired.

TCP协议在重发数据前需要等待的时间为()。