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

admin2023-02-06 20

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

学硕统考专业

《中华人民共和国义务教育法》规定：“家长应当依法保障适龄儿童、少年接受义务教育权利的实现”。这种法律规范属于()。

现代心理学研究表明，如果教学目标是传递言语信息，那么，在有现成的文字教材的条件下，对中学生而言，最适当的方法是()。

IQ与学业成绩存在中等程度的相关，其相关系数在小学阶段为()。

“十三五”时期，我国航天发射次数占全球的比重为：

设100件产品中有次品4件，从中任取5件产品，不可能的事件是()

下面关于胃溃疡的叙述不正确的是

设计图纸是设计工作的最终成果，监理工程师应对设计图纸进行审核，施工图重点审核的内容有(　　)。

变形测量的基准点分为()。

由于销售的持续上升加上成本控制，成熟阶段利润达到()。

下列说法正确的是()。

“走转改”(复旦大学2018年研；北大2012年研)

根据《宪法》的规定，国家发展劳动者休息和休养的设施，规定()。

1927年大革命失败后，在国民党的统治下中国社会的性质是

AccordingtoRobertFranek,thePrincetonReviewrankingsaredifferentfromotheronesbecause

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

计算机408

学硕统考专业

《中华人民共和国义务教育法》规定：“家长应当依法保障适龄儿童、少年接受义务教育权利的实现”。这种法律规范属于()。

现代心理学研究表明，如果教学目标是传递言语信息，那么，在有现成的文字教材的条件下，对中学生而言，最适当的方法是()。

IQ与学业成绩存在中等程度的相关，其相关系数在小学阶段为()。

“十三五”时期，我国航天发射次数占全球的比重为：

设100件产品中有次品4件，从中任取5件产品，不可能的事件是()

下面关于胃溃疡的叙述不正确的是

设计图纸是设计工作的最终成果，监理工程师应对设计图纸进行审核，施工图重点审核的内容有( )。

变形测量的基准点分为()。

由于销售的持续上升加上成本控制，成熟阶段利润达到()。

下列说法正确的是()。

“走转改”(复旦大学2018年研；北大2012年研)

根据《宪法》的规定，国家发展劳动者休息和休养的设施，规定()。

1927年大革命失败后，在国民党的统治下中国社会的性质是

AccordingtoRobertFranek,thePrincetonReviewrankingsaredifferentfromotheronesbecause

设计图纸是设计工作的最终成果，监理工程师应对设计图纸进行审核，施工图重点审核的内容有(　　)。