首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键宇取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键宇取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2017-01-04
68
问题
对一个由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,MaxB,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/qLRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
论述清末预备立宪运动
近代自然科学产生的条件及其发展情况。
19世纪中后期,民族主义的潮流在欧洲和亚洲各发生哪些具有代表性的事件?概括其各自的特点并分析形成这些特点的原因。
古代两河流域最具代表性的文学作品是()。
三大战役的先后顺序是()
1942年太平洋战争爆发后,日本先后夺取了焦作、开滦等煤矿,华北沦陷区每年向日本输送的原煤达800万吨。这说明日本在沦陷区进行经济掠夺的直接目的是()。
著名的绥靖政策文件《霍尔—赖伐尔协定》是英、法与意大利签订的,密谋发动()。
1925年10月签订《洛迦诺公约》后,法国外长白里安认为:“我国的安全比以往任何时候都更有保障了。”对此说法不正确的一项是()。
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时,就拒绝分配资源,但是,银行家算法要求的条件并不是必要的。例如,某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下:请说明系统并不一定死锁。
随机试题
黑白瓶法通过测定水体中某物质的浓度来测定水生生态系统的初级生产量,该物质是()
周围神经损伤后,为观察神经的修复情况,可进行下列哪几项检查
下列哪项不是缺铁性贫血的特殊表现
以房地产抵押贷款为目的的估价,其估价时点原则上为()。
某大型防洪工程由政府投资兴建。项目法人委托某招标代理公司代理施工招标。招标代理公司依据有关规定确定该项目采用公开招标方式招标,招标公告在当地政府规定的招标信息网上发布。招标文件中规定:投标担保可采用投标保证金或投标保函方式担保。评标方法采用经评审的最低投标
近代中国沦为半殖民地半封建社会的最主要原因是()。
选项四个图形中,只有一个是由题干的四个图形拼合(只能通过上、下、左、右平移)而成的,请把它找出来。
()不是唐代诗人李白的作品。
西汉末年,某地一男子偷盗他人一头牛并贩卖到外乡,回家后将此事告诉了妻子。其妻隐瞒未向官府举报。案发后,该男子受到惩处。依照汉代法律,其妻的行为应()。
在考生文件夹下已有customers(客户)、orders(订单)、orderitems(订单项)和goods(商品)四个表。(1)创建一个名为“订单管理”的数据库,并将已有的customers表添加到该数据库中。(2)利用表设计器为custome
最新回复
(
0
)