首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2019-08-15
21
问题
对一个由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://jikaoti.com/ti/LMGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
义和团发展到高潮的标志是()
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
在一个8级中断的系统中,硬件中断响应从高到低的优先顺序是1→2→3→4→5→6→7→8,通过中断屏蔽技术,将中断处理优先顺序设置为1→3→5→7→2→4→6→8,如果CPU在执行一个应用程序时有5、6、7、8级的四个中断同时到达,CPU在按优先顺序处理到第
Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是:仅当需要访问某页面时,如果它不在内存,把它调入内存。按照这个思路,将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理,也可以产生类似的算法,不妨
分时系统里,在条件相同的情况下,通常KLT(内核级线程)比ULT(用户级线程)得到更多的CPU时间,请简要解释之。
某中央处理器的数据通路如图所示。MDR为内存数据寄存器,PC为程序计数器,IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释:为什么要设置T暂存器?(3)假定指
假定不采用Cache和指令预取技术,且机器处于“开中断”状态,则在下列有关指令执行的叙述中,错误的是____。
下列关于RISC的叙述中,错误的是()。
下列选项中,用于提高RAID可靠性的措施有I.磁盘镜像Ⅱ.条带化Ⅲ.奇偶校验Ⅳ.增加cache机制
随机试题
在word中,段落格式的设置或修改将应用于()。
女性患SLE时以下处理哪项不妥
艾滋病防治的治标措施中最重要的是
A.半夏配桑白皮B.半夏配藿香C.半夏配黄连D.半夏配猪苓E.半夏配干姜患者,男,37岁。目眩耳聋,胸满胁痛,口苦,呕吐苦水,易怒,烦躁不寐,惊悸不宁,苔黄腻,脉弦滑。宜选
下列哪些是包衣的目的
在我国,依法设立的可经营证券业务的证券公司的主要业务有( )。
下图表示反射弧和神经纤维局部放大的示意图(图3为图2虚线框放大图,图4为图2中⑥的放大图),据图回答问题。问题:图3表示神经纤维受到刺激的瞬间膜内外电荷的分布情况,在a、b、c中兴奋部位是________。在兴奋部位和相邻的未兴奋部位之间由于电位差
__________的出现,标志着我国冶炼技术的成熟。
已知:如下图所示,反比例函数的图象经过点A、B,点A的坐标为(1,3),点B的纵坐标为1,点C的坐标为(2,0).求该反比例函数的解析式;
男子甲以一女子的口吻给乙的丈夫丙写了一封匿名信,诉说乙与“其”丈夫有不正当男女关系,乙因此与丈夫丙之间的夫妻感情不和。乙后来得知此信系男子甲所写。据此,下列表述正确的是()。
最新回复
(
0
)