首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
admin
2019-08-15
30
问题
已知下列各种初始状态(长度为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/kKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
为了顺利开展武装起义的准备工作,在彼得格勒苏维埃中成立了()。
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭
以下是二战后美国经济发展的排列组合,其中最正确的一组是()
以下()协议完成了从网卡到IP地址的映射。
就绪队列中有n个进程等待使用一个CPU,那么,如果采用不同的调用算法,就有()种调度顺序。
路由器采用()方式来发送IP分组。
下面元件存取速度最快的是()。
循环队列用数组A[0..m~1]存放其元素值,已知其头尾指针分别为front和rear,则当前元素个数为()。
随机试题
甲公司持有乙公司3%股权,对乙公司不具有重大影响。甲公司在初始确认时将对乙公司股权投资指定为以公允价值计量且其变动计入其他综合收益的金融资产。2×18年5月,甲公司对乙公司进行增资,增资后甲公司持有乙公司20%股权,能够对乙公司施加重大影响。不考虑其他因素
鸡传染性支气管炎的病原是
头痛是哪些疾病的先兆症状()。
甲县某烟草公司去相邻的乙县收购烟叶,2017年6月9日支付烟叶收购价款80万元,另对烟农按收购价款的10%支付了价外补贴,下列纳税事项的表述中,正确的是()。
实践中,我国境内商业银行可以向外籍自然人发放个人住房贷款。()
对生产计划的监督、检查和控制,发现偏差及时调整的过程可称为()。
随着社会的飞速发展和二胎时代的到来,家长“望女成凤”“望子成龙”的希望没有丝毫的减退。家长们都不希望自己的子女输在起跑线上,在幼儿园阶段就已经纷纷攀比起来,尤其是部分家长的“神童”情结泛滥。他们给孩子报了大量的补习班,导致这些孩子在掌握了大量的知识的同时也
以下社会组织属于财团法人的是()。
TheCapitalAirportisthelargestoneinChina.TheCapitalAirportis______anyotherairportinChina.
I.Q.standsfor"IntelligenceQuotient"whichisameasureofaperson’sintelligencefoundbymeansofanintelligencetest.I
最新回复
(
0
)