首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
对一个由n个关键字不同的记录构成的序列,能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
admin
2017-11-14
86
问题
对一个由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={MaxA,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/P3Ri777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
关于“尊王攘夷”运动,不正确的说法是()。
义和团爆发的直接原因是()。
1925年爆发的当时世界上罢工时间最长的一次斗争是()。
戈尔巴乔夫上台后,在和平共处五项原则基础上,推动苏中关系正常化,这一做法主要表明了()。
三国鼎立局面的关键性战争是()。
唐朝流传着一句“三十老明经、五十少进士”,这说明了唐代科举()。
某系统中n个相互独立的生产者进程为一个消费者进程提供数据,假设每个生产者提供的数据写入各不相同的缓冲区,且生产者写缓冲区的速度比消费者读缓冲区的速度快,则缓冲区个数的最优值应为()。
给定单链表的结点结构typedefstructnode*link;structnode{intitem,linknext;);将两个升序单链表归并为一个升序单链表。
下列排序算法中,时间复杂度为O(nlogn)且占用额外空间最少的是()。
假设有k个关键字互为同义词,若用线性探查法把这k个关键字存入,至少要进行的探查次数是()。
随机试题
A.鱼精蛋白B.维生素KC.去铁胺D.红细胞生成素E.肝素过量铁剂中毒应选用
我国《刑事诉讼法》规定,被取保候审的犯罪嫌疑人应当遵守的规定有()。
关于子宫生理缩复环,正确的是()。
下图所示的盲道砖不应设置在盲道的什么部位?
某人贷款10万元,贷款利率8%,3年后还本付息,如果按复利法和单利法分别计息,则二者利息总额的差额为( )万元。
某石化生产企业为增值税一般纳税人,2015年6月生产经营业务如下:(1)开采原油50万吨,对外销售原油8万吨并取得不含税销售收入9600万元,用开采的同类原油30万吨加工生产成汽油7.2万吨。(2)进口原油40万吨,用于加工生产成汽油1
P国的政府宣称:六大城市之一的拓尔城是今年P国的所有城市中唯一保持了强劲就业增长势头的城市。然而很明显,那里的任何就业增长纯粹是虚构的,实际上,拓尔城今年的失业人数就多于去年。反对政府的宣称的论述取决于下列哪一个假设?
Justasthebuilderisskilledinthehandlingofhisbricks,______theexperiencedwriterisskilledinthehandlingofhisword
A、Ithelpspeoplegetupearly.B、ItproducesVitaminD.C、Itkillscoldviruses.D、Itenablesustolookhealthy.BB为两次提及的明示信息,
A、Sheshouldgototheconcert.B、Sheoughttodoexperimentsinthelaboratory.C、Sheshouldputonhershoes.D、Sheshouldtak
最新回复
(
0
)