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

admin2017-11-14 61

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

学硕统考专业

关于德国工业革命，说法不正确的是()。

在巴黎和会上获利最大的两个国家是()。

()时，为补充兵力，开拓财源，“料民于太原”(今山西西南部)。料民就是清查民数，以便于征兵，结果引起奴隶和平民的反抗。这表明西周王朝已失去了对社会的控制力量。

二里头文化是我国考古史上的重大发现，具有重大的意义。根据所学知识，回答问题：二里头文化在类型上可以分为()

在集中式总线仲裁中，()方式响应时间最快。

在请求分页存储管理中，若采用FIFO的页面淘汰算法，当分配的页面数增加时，缺页中断的次数()。

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

某机字长32位，总线数据线宽度是16位，一个总线周期占用4个时钟周期，总线时钟频率为10MHz，则总线带宽是()。

压力变送器是根据力平衡原理来测量的。

寒、热、痰、湿、瘀、郁，犯及冲任导致冲任阻滞，治宜疏通冲任，代表方有

对重度休克病人纠正代谢性酸中毒时，下列哪项不宜使用：

钢筋混凝土水处理构筑物的浇筑层高度一般为振捣器作用部分长度的1．25倍，最大不超过()mm。

“备案号”栏应填：“原产国”栏应填：

费率是指利率以外的银行提供信贷服务的价格，一般以信贷产品金额为基数，按一定比率计算。()(2010年上半年)

法是一种社会规范，同道德规范、职业规范相比，具有以下特点()。

班主任对一个班集体的发展起()。

下列VisualBasic变量名中，正确的是()。

描述计算机内存容量的参数，正确的是()。