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

admin2017-11-14 29

问题对一个由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题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

光绪元年七月，清政府迫于()强烈要求派一位使臣到其国，()成为中国第一个驻外公使

为加强君权，皇太极时代开始直接控制的“上三旗”不包括()。

新石器时代的房屋建筑根据环境的不同形成了不同的类型，()地区多为干栏式建筑。

下列对1918年德国十一月革命说法不正确的是()。

1534年英国议会宣布英国教会断绝与罗马教廷一切关系的文件是()。

袁世凯在控制自己权力，实现对全国控制的过程中，主要颁布的法律不包括()。

基辅罗斯国家对居民征税的方式是()。

第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式。最早提出这种方式的是()。

古埃及第24朝法老波克利斯进行改革，宣布废除奴隶制，债权人只能索取债务人的财产作抵偿，而不能占有债务人的人身，因为财产属于个人，而公民人身属于国家，国家需要他们服役。该改革旨在

世界天文史上最早实地测量子午线的记录是由谁进行的?()

公司法中属于程序法范畴的是

Themonitor______theexaminationpaperstotheclassforhisteacher.

A、蛋白电泳B、免疫电泳C、免疫固定电泳D、免疫球蛋白定量E、尿本一周蛋白检测了解M蛋白的类型应做

下列犯罪，属于法条竞合的有(　　　)。

及时性要求企业对于已经发生的交易或者事项，应当及时进行确认、计量和报告，但可以提前或者延后。()

所谓(),是指利用不同国家或地区在短期内的利率差异,将资金从利率相对较低的国家或地区调往利率相对较高的国家或地区,从而赚取利差收益的外汇交易

平原盆地多形成(　　　)城市布局结构。

凡年满()，具有高中以上文化程度和完全民事行为能力的人员均可参加证券业从业人员资格考试。

下列各存储器中，存取速度最快的是()。

Depression[A]Inbed,youtossandturn,unabletogetagoodnight’ssleep.Youfeelanxiousandworried.There’splentytodo,

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

计算机408

学硕统考专业

光绪元年七月，清政府迫于()强烈要求派一位使臣到其国，()成为中国第一个驻外公使

为加强君权，皇太极时代开始直接控制的“上三旗”不包括()。

新石器时代的房屋建筑根据环境的不同形成了不同的类型，()地区多为干栏式建筑。

下列对1918年德国十一月革命说法不正确的是()。

1534年英国议会宣布英国教会断绝与罗马教廷一切关系的文件是()。

袁世凯在控制自己权力，实现对全国控制的过程中，主要颁布的法律不包括()。

基辅罗斯国家对居民征税的方式是()。

第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式。最早提出这种方式的是()。

古埃及第24朝法老波克利斯进行改革，宣布废除奴隶制，债权人只能索取债务人的财产作抵偿，而不能占有债务人的人身，因为财产属于个人，而公民人身属于国家，国家需要他们服役。该改革旨在

世界天文史上最早实地测量子午线的记录是由谁进行的?()

公司法中属于程序法范畴的是

Themonitor______theexaminationpaperstotheclassforhisteacher.

A、蛋白电泳B、免疫电泳C、免疫固定电泳D、免疫球蛋白定量E、尿本一周蛋白检测了解M蛋白的类型应做

下列犯罪，属于法条竞合的有( )。

及时性要求企业对于已经发生的交易或者事项，应当及时进行确认、计量和报告，但可以提前或者延后。()

所谓(),是指利用不同国家或地区在短期内的利率差异,将资金从利率相对较低的国家或地区调往利率相对较高的国家或地区,从而赚取利差收益的外汇交易

平原盆地多形成( )城市布局结构。

凡年满()，具有高中以上文化程度和完全民事行为能力的人员均可参加证券业从业人员资格考试。

下列各存储器中，存取速度最快的是()。

Depression[A]Inbed,youtossandturn,unabletogetagoodnight’ssleep.Youfeelanxiousandworried.There’splentytodo,

下列犯罪，属于法条竞合的有(　　　)。

平原盆地多形成(　　　)城市布局结构。