首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2019-08-01
23
问题
对一个由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>3),将分成长为n一2和2的前后两部分A和B,分别找出最大者和最小者:Max A,Min A,Max B,Min B,最后Max={Max A,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/w8Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
中国第一个资产阶级革命团体兴中会建立的时间是()。
促成中国近代史上第一次思想解放潮流的是()。
北宋在统一南方割据势力的过程中特设(),把征南所得的财富统一存放,以作日后恢复幽燕之费。
顽固派破坏百日维新的手段有()①对变法诏令阳奉阴违托词抗命②把京津地区的兵权都抓在手中③改总理衙门为外务部讨好列强④慈禧太后直接控制人事任免权
IP数据报的报文格式如下图所示。在没有选项和填充的情况下,报头长度域的值为()。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
某机字长32位,总线数据线宽度是16位,一个总线周期占用4个时钟周期,总线时钟频率为10MHz,则总线带宽是()。
序列的“中值记录”指的是:如果将此序列排序后,它是第n/2个记录。试写出一个求中值记录的算法。
给定序列{3,5,7,9,11,13,15,17),(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情
某图形显示器的分辨率为640×480,刷新频率为50Hz,且假定水平回扫期和垂直回扫期各占水平扫描周期和垂直扫描周期的20%,试计算图形显示器的行频、水平扫描周期、每个像素的读出时间和视频带宽。若分辨率提高到1024×768,刷新频率提高到60Hz,再次计
随机试题
简述公务员辞退的特点。
痉挛型双瘫脑瘫是指
支气管扩张最有意义的体征是()
以下列入国家一级保护野生药材物种的是
用人单位招用劳动者,不得扣押劳动者的居民身份证和其他证件,不得要求劳动者提供担保或者以其他名义向劳动者收取财物。()(2011年)
大冷公司是一家拥有80多年历史的中医药公司,其使用国家级保密配方配制的某种药品,具有清热、利尿、祛痰、凉血、解毒的功效。从20世纪90年代推出以来,疗效显著,一直深受患者欢迎。大冷公司拥有的具有不可模仿性的资源属于()。
我国古代最著名的地下宫殿是()。
鲤鱼整天都想跳过龙门,把自己变成龙,是因为( )。鲤鱼变成的龙发觉自己跟过去没有两样,是因为( )。
美国长期受益于美元的主导地位,以美元换取资源、产品和服务,美国在用美元从其他国家购买商品的同时,也通过货币贬值透支消费,______,将其金融风险输送至全世界。因此,美联储________把握加息节奏,加强与其他经济体和金融市场的政策________,符合
下列程序的执行结果为PrivateSubCommand1_Click()DimFirStrAsString FtrSt="abcdef" PrintPat(FirStr)EndSubPriv
最新回复
(
0
)