首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2017-11-14
52
问题
对一个由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题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
最早测量子午线的长度,并主持修订了当时最先进历法《大衍历》的是僧人()。
1934年9月苏联加入国联,对此说法错误的一项是()。
苏联“十四大”、“十五大”后经济建设的核心内容是()
汉章帝会群儒于白虎观,讨论经义,由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书,这部书系统地吸收了阴阳五行和谶纬之学,形成今文经学派的主要观点。
在巴黎和会上获利最大的两个国家是()。
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
下列排序算法中不能保证每趟排序至少能将一个元素放到其最终的位置上的是()。
随机试题
在制定读者俱乐部章程时,除应符合国家的相关法律、法规、政策外,更应注意语言的精准和内容解释的()。
Bothresult-adjunctsandpurpose-adjunctscanbeintroducedby50that.Howcanwetellthedifference?
一年轻妇女正常阴道分娩刚结束,检查脐带血管,下列哪项是正确的
持力层承载力与( )项值接近。软弱层顶面的附加压力与( )项值接近。
钢质锥塞锚具、夹片锚具属于()锚固。
砌筑混凝土小型空心砌块时,按净面积计算水平灰缝的砂浆饱满度最小值是()%。
在教育目标的分类中,美国教育心理学家布鲁姆就学生学习结果划分的三大领域是()。
降低大气中二氧化碳的含量,植树造林是比较好的措施,因为植物在光合作用时可大量地吸收二氧化碳,释放出氧气。植物吸收的这些二氧化碳在细胞内的哪个部位被合成了有机物?()
有以下程序:#include<stdio.h>main()(intstlm=10,n=1;while(n<3){sum=sum—n;n++;}printf("%d,%d
Nuclearscienceshouldbedevelopedtobenefitthepeople______harmthem.
最新回复
(
0
)