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

admin2023-02-06 74

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

学硕统考专业

进行课程管理时，应该强化课程意识，提高学校课程建设与管理的功能，构建重基础、多样化、有层次、综合性的课程结构。()

自学指导法包括指导学生预习、阅读参考书等，这一方法最突出的特点是指导学生合作学习。()

根据我国教育法的规定，下列不属于设立学校及其他教育机构必须具备的基本条件的是()。

课外辅导是帮助和指导学生学习的活动。下列关于课外辅导的说法错误的是()。

个体将在一种学习中习得的一般原理、方法、策略和态度等迁移到另一种学习中去叫作()。

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

布鲁纳在结构教学观中提出的教学原则不包括()。

在时间上，家庭教育是()。

急救过程中需要争分夺秒立刻进行胸部减压排气的气胸类型是【】

电化学发光免疫分析(ECLIA)常采用的标记物是

固定式地脚螺栓埋设在混凝土基础里，是不可拆卸的，常用固定式地脚螺栓下部一般制成(　　)。

记账凭证是根据审核无误的()填列的。

下列有关增加股东财富的表述中，正确的是()。

已知{an}是由非负整数组成的无穷数列，该数列前n项的最大值记为An,第n项之后各项an+1，an+2．…的最小值记为Bn,dn=An－Bn．若{an}为2，l，4，3，2，1，4，3，…，是一个周期为4的数列(即对任意n∈N*，an+4=an)，写出

以下关于新中国成立以来制定的四部宪法中有关公民基本权利的条款数量的说法正确的是()。

下列程序将x、y和z按从小到大的顺序排列，横线处应添加语句()。template＜classT＞voidfun(______){Ta;if(x＞y){a=x;x=y;y=a;}

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

计算机408

学硕统考专业

进行课程管理时，应该强化课程意识，提高学校课程建设与管理的功能，构建重基础、多样化、有层次、综合性的课程结构。()

自学指导法包括指导学生预习、阅读参考书等，这一方法最突出的特点是指导学生合作学习。()

根据我国教育法的规定，下列不属于设立学校及其他教育机构必须具备的基本条件的是()。

课外辅导是帮助和指导学生学习的活动。下列关于课外辅导的说法错误的是()。

个体将在一种学习中习得的一般原理、方法、策略和态度等迁移到另一种学习中去叫作()。

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

布鲁纳在结构教学观中提出的教学原则不包括()。

在时间上，家庭教育是()。

急救过程中需要争分夺秒立刻进行胸部减压排气的气胸类型是【】

电化学发光免疫分析(ECLIA)常采用的标记物是

固定式地脚螺栓埋设在混凝土基础里，是不可拆卸的，常用固定式地脚螺栓下部一般制成( )。

记账凭证是根据审核无误的()填列的。

下列有关增加股东财富的表述中，正确的是()。

已知{an}是由非负整数组成的无穷数列，该数列前n项的最大值记为An,第n项之后各项an+1，an+2．…的最小值记为Bn,dn=An－Bn．若{an}为2，l，4，3，2，1，4，3，…，是一个周期为4的数列(即对任意n∈N*，an+4=an)，写出

以下关于新中国成立以来制定的四部宪法中有关公民基本权利的条款数量的说法正确的是()。

下列程序将x、y和z按从小到大的顺序排列，横线处应添加语句()。template＜classT＞voidfun(______){Ta;if(x＞y){a=x;x=y;y=a;}

固定式地脚螺栓埋设在混凝土基础里，是不可拆卸的，常用固定式地脚螺栓下部一般制成(　　)。