首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
admin
2019-08-15
31
问题
已知下列各种初始状态(长度为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
学硕统考专业
相关试题推荐
希特勒打出民族主义的旗号而获得群众的广泛支持,主要原因是()。
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭
下列内容,与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张,从经济上瓜分世界
二里头文化是我国考古史上的重大发现,具有重大的意义。根据所学知识,回答问题:对于二里头文化的发现的意义,下列选项表述最准确的是()
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:随着商业的发展,唐朝在货币和金融方面有一些重要的进步,以下表述全面的是()
米勒兰事件
波士顿倾茶事件
若二叉树的前序序列为DABCEFG,中序序列为BACDFGE,则其层次序列为()。
下面元件存取速度最快的是()。
下列选项中,用于提高RAID可靠性的措施有I.磁盘镜像Ⅱ.条带化Ⅲ.奇偶校验Ⅳ.增加cache机制
随机试题
根据埃里克森的理论,当个体开始考虑“我是谁”这一问题时,表明个体正处于()阶段。
男性,35岁,司机,臀部及大腿根内侧皮肤瘙痒伴水疱,反复抓挠后皮肤增厚。切片见表皮内不同程度的灶性细胞间水肿和细胞水肿,有海绵形成及混合性炎细胞的浸润,诊断为
A、出生后即刻B、3~6个月C、6~12个月D、1~2岁E、9~11岁双侧完全性唇裂修复术最佳时机为
甲型肝炎病程中,传染性最强的阶段是
药典五号标准药筛相当于工业用筛目数是
A、酸碱滴定法B、非水溶液滴定法C、沉淀滴定法D、氧化还原滴定法E、配位滴定法;以下滴定液所适用的方法是硫酸铈滴定液
焊接是管道安装的重要工序,焊工作业应符合作业证中的允许范围,不能超出范围焊接。下列项目中属于焊接前必须审核内容的是()。
2018年1月1日,甲公司对外转让一项无形资产,协议约定转让期3年,总价款为60万元,于每年年末收取当年使用费20万元。该无形资产每年计提摊销额14万元,假定不考虑其他因素,则甲公司2018年12月31日应确认的其他业务收入为()万元。
A、youfeeltheimportanceoftheoccasionB、youdon’tloseanyoftheatmosphereC、yougetabetterviewofthegameD、youfeel
Decidewhichofthechoicesgivenbelowwouldbestcompletethepassageifinsertedinthecorrespondingblanks.Itisallv
最新回复
(
0
)