首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2016-03-29
70
问题
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
选项
答案
将n个元素对称比较,即第一个元素与最后一个元素比较,第二个元素与倒数第二个元素比较……比较中的小者放前半部,大者放后半部,用了n/2次比较。再在前后两部分中分别简单选择最小和最大元素,备用(n/2)一1次比较。总共用了(3n/2)一2次比较。显然,当n≥3时,(2n一3)>(3n/2)一20 用分治法求解再给出另一参考答案。 对于两个数x和y,经一次比较可得到最大值和最小值;对于三个数x,y,z,最多经3次比较可得最大值和最小值;对于n个数(n>3),将分成长为n一2和2的前后两部分A和B,分别找出最大者和最小者:Max A,Min 4,Max B,MinB,最后Max={Max A,Max B}和Min={Min A,Min B}。对A使用同样的方法求出最大值和最小值,直到元素个数不超过3。 设C(n)是所需的最多比较次数,根据上述原则,当孔>3时有如下关系式: [*] 通过逐步递推,可以得到:C(n)=(3n/2)一2。显然,当n>3时,2n一3>(3n/2)一2。事实上(3n/2)一2是解决这一问题的比较次数的下限。
解析
转载请注明原文地址:https://kaotiyun.com/show/GnRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
春秋战国时代,小农经济出现的最主要的条件是()
1837年倡导用无机肥料来补充土壤中耗去的化学元素的化学家是()。
法国《人权宣言》的主要内容有哪些?
1920年,苏俄农民中流传着这样的说法:“土地属于我们,面包却属于你们;水属于我们,鱼却属于你们;森林属于我们,木材却属于你们”,它反映的是战时共产主义政策()。
以下选项中中原王朝对西藏管辖设置机构对应有误的一项是()。
三国时期,魏、蜀、吴三国灭亡的历史顺序是()。
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
桌上有一空盘,只允许放入一个水果。爸爸专向盘中放苹果,妈妈专向盘中放橘子,女儿专等着吃盘中的苹果,儿子专等着吃盘中的橘子。试用P,V原语实现爸爸、妈妈、儿子和女儿间能同步的程序。
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
随机试题
关于协调性宫缩乏力,正确的是
A.右室容量负荷增加B.左室容量负荷增加C.右室压力负荷增加D.左室压力负荷增加E.双室容量负荷均增加
A.坂口反应,麦芽糖反应B.绿奎宁反应C.茚三酮反应D.火焰焰色反应E.三氯化铁显色反应
A.白及B.白芍C.五灵脂D.人参E.京大戟甘草反()。
案例T市G钢铁有限公司成立于1993年,注册资金40316.76万美元,集烧结、炼铁、炼钢、轧钢于一体的大型钢铁联合企业。主要生产设备设施包括炼铁高炉10座(450m。高炉8座、1780m3高炉2座)、炼钢转炉8座(50t转炉3座、80t转炉3座、120
背景某单层工业厂房工程施工,拆除顶层钢模板时,将拆下的25根钢管(每根长4.5m)和扣件运到井字架的吊篮上,6名工人准备随吊篮一起从屋顶下落到地面。此时恰好操作该吊篮的专职司机上厕所不在岗,临时由附近施工的一名普工开动卷扬机。在卷扬机下降过程中,钢丝绳
当一张软盘写保护后,对盘中文件不可以操作的有()。
当前,我国社会主义建设进入了新的时期。在新世纪、新阶段,公安机关的总任务是()。
根据以下资料,回答问题。某公司招来一批实习生,其中有三名男生,高原、郭建和李涛;五名女生,晓静、李爽、刘丽、宋莹和王芳。经过三个月的考核,公司有五个转正名额,准备从三名男生中选出两名,从五名女生中选出三名来转正。有如下要求:(1)高原和
如果变量x和变量y之间的相关系数为-0.85,这说明两变量之间是()
最新回复
(
0
)