首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
admin
2018-08-12
35
问题
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)?
(1)关键字自小到大有序(key
1
<key
2
<…<key
n
);
(2)关键字自大到小逆序(key
1
>key
2
>…>key
n
);
(3)奇数关键字顺序有序,偶数关键字顺序有序(key
1
<key
3
<…,key
2
<key
4
<…);
(4)前半部分元素按关键字顺序有序,后半部分元素按关键字顺序逆序(key
1
<key
2
<…<key
m
,key
m+1
>
key
m+2
<…<key
n
,m为中间位置)。
选项
答案
本题主要考查直接插入法的算法思想及性能分析。 根据题目所给出的条件,最好情况下的比较次数即为最少比较次数。 (1)在关键字自小到大有序的情况下,插入第i个(2≤i≤n)元素的比较次数为1,因此,总的比较次数为1+1+1+…+1=n一1。 (2)在关键字自大到小有序的情况下,插入第i个(2≤i≤n)元素的比较次数为i,因此,总的比较次数为2+3+4+…+n=[n(n+1)/2]一1=(n一1)(n+2)/2。 (3)在奇数关键字顺序有序和偶数关键字顺序有序的情况下,比较次数最少的情况是所有记录关键字均按升序排列,这时,总的比较次数为n一1。 (4)在前半部分元素按关键字有序,后半部分按关键字逆序的情况下,后半部分元素的关键字均大于前半部分元素的关键字时比较次数最少,此时前半部分的比较次数为m—1,后半部分的比较次数为(n一m—1)(n一m+2)/2,因止匕,总的比较次数为m一1+(n一m一1)(n一m+2)/2=(n一2)(n+8)/8(假设n为偶数,m=n/2)。
解析
转载请注明原文地址:https://kaotiyun.com/show/gMRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
在蒙古向南扩张的同时,还发动了三次大规模的西征,三次西征中分别在位的大汗是()
曾经来华留学,并在日本大化改新中发挥重要作用的是()。
隋在统一全国的过程中,平定江南是一个重要的部分,帮助完成岭南一带平定的是()
下列城市:①南京②厦门③天津④杭州,按其在近代历史上开放为商埠的时间先后顺序排列应该是()
建立帝国财政收支总账和元首金库,直接控制和调节全国财政收支的是()。
下列不属于“一国两制”的基本内容的是()。
试析巴以冲突的历史根源。
1937年11月,继张家口、大同、归绥的三个伪政权后,日本又成立了(),将三个伪政权统一管辖。
已知某32位二进制机器数为11000000000000000000000000000000,试计算在下列各种编码方式下其代表的真值。(1)原码定点小数;(2)补码定点小数;(3)反码定点小数;(4)IEEE754标准短
某路由器的IP地址是125.45.23.12,它在以太网上的物理地址为2345AB4F67CD,它收到了一个分组,分组中的目的IP地址是125.11.78.10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。
随机试题
构建社会主义和谐社会,必须坚持以人为本( )。
小雅在课堂上学习了PowerPoint2010演示文稿软件的使用后,自己也制作了一个演示文稿,下图为第一张幻灯片的展示。请结合所学知识,回答下列问题。(3)小雅要为插入的“基本流程”图设置进入:飞入、强调:加深、退出:飞出动画效果,应进行哪些操作?
高血压病脑出血最常见的出血部位是
(2006年)获得高扬程水泵的方法有()。
管阻力的模型实验,原型与模型都用同一种油,几何比尺λ=2,模型流量中心线流速1m/s,原型中心线流速为()m/s。
水利工程施工项目招标分为()。
注册会计师在对被审计单位的应付账款进行审计时,一般应选择的函证对象有()。
下列项目中应在其他综合收益项目列报的是()。
RichardSatava,programmanagerforadvancedmedicaltechnologies,hasbeenadrivingforceinbringingvirtualrealitytomedic
A、正确B、错误A语义的理解和判断。根据原文Infact,mostofusspendagreatdealoftimetryingtogetotherpeopletodowillinglywhatwewantth
最新回复
(
0
)