首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2019-08-15
26
问题
对一个由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={Max A,Max B}和Min={Min A,Min B}。对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/VKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一,为重新认识三代的历史与文化奠定了基础,开辟了坦途,可称之为中国文化史的里程碑。根据所学知识回答问题:在甲骨文的研究流域,对甲骨文研究作出了重大贡献,被后人称为“甲骨四堂”的四位学者是(
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭
书院制度,始于唐而盛于宋,根据所学知识。回答问题:南宋书院的复起,是由朱熹开始的。他重建白鹿洞书院,亲自到书院讲学,还亲手制定()
中山舰事件
(1)所有事件的最早发生时间如下:Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3,ve(3)+6}=12Ve(5)=max{ve(3)+3,ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve
以下()协议完成了从网卡到IP地址的映射。
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,-1,4,-4,…,j2,-j2(j<=m/2)。当di>0时,Hi=(H(key)+di)%m当di<0时,Hi=(H(key)+di+m)%m散列
某中央处理器的数据通路如图所示。MDR为内存数据寄存器,PC为程序计数器,IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释:为什么要设置T暂存器?(3)假定指
TCP使用()机制来进行流量控制。
某计算机系统字长为32位,包含2个选择通道和1个字节多路通道,每个选择通道上连接了2台磁盘机和2台磁带机,字节多路通道上连接了2台行式打印机、2台读卡器、10台终端。假定各设备的传输率如下:磁盘机:800KB/s磁带机:200KB/s
随机试题
清肝养血明日退翳的药物是()(1991年第27题)
氧化钙是衡量黄酒品质的重要指标,国家标准中规定,黄酒中氧化钙的含量应小于或等于()。
1937年8月,中国共产党提出抗日基本主张的会议是()
A.清热解毒,佐以透发B.辛凉透表,清宣肺卫C.养阴益气,清解余邪D.清营解毒,平肝熄风E.清热解毒,利咽消肿
发票的存根联和发票登记簿,一般应保存()。
某公司全年需用X材料18000件,计划开工360天。该材料订货日至到货日的时间为5天,保险储备量为100件。该材料的再订货点是()件。
某普通合伙企业合伙人陈某死亡,其合法继承人小陈不愿成为该合伙企业的合伙人。对陈某在该合伙企业中的财产份额,应在全体合伙人之间平均分配。()
氢化过程会使脂肪酸的一部分顺式双键变成反式结构。
学生采用SQ3R阅读法进行阅读,提高了阅读效率。依据加涅的学习结果分类,SQ3R阅读法属于()。
为了防止一个用户的工作不适当地影响另一个用户,应采取______。
最新回复
(
0
)