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

admin2023-02-06 70

问题对一个由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

学硕统考专业

()是个体品德的核心部分，指一个人面对矛盾冲突的情景能自觉意识到是非善恶，进而能就行动做出缜密周到的抉择。

以下选项除了()都是教师仪容仪态需要遵守的要求。

问题解决是个体在日常生活中思维活动最普遍、最重要的形式。从19世纪末开始，心理学家就不断使用实验方法来研究问题解决。以下属于问题解决研究的实验有()。

一个教师道德修养达到高度自觉程度的标志是()。

利用逐点插入建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，要查找元素30要进行元素间的比较次数是()。

双向链表中有两个指针域，即prior和next，分别指向前驱及后继，设P指向链表中的一个结点，q指向一个待插入结点，现要求在P前插入q，则正确的插入为()。

有关腹膜炎的治疗，最重要的措施是

以病人为本，以健康为本，确保生产、销售、使用的药品安全、有效、经济、合理是在执业过程中知晓的他人的秘密，不得无故泄漏是

《刑法》第14条规定“故意犯罪，应当负刑事责任”，而第15条规定“过失犯罪，法律有规定的才负刑事责任”，这样的规定：

下列情形中应当数罪并罚的是：()

下列收益还原法的基本公式中，未来若干年后的土地价格已知的条件下的计算公式为()。

当系统采用串联校正时，校正环节为Gc(s)=，则该校正环节对系统性能的影响是()。

消防设施施工前，需要具备一定的技术、物质条件，以确保施工需求，保证施工质量。下列不属于消防设施施工前需要具备的基本条件的是()。

(2016年)下列关于无形资产摊销会计处理的表述中，正确的有()。