首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>key2>…>k
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>key2>…>k
admin
2023-02-06
24
问题
已知下列各种初始状态(长度为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/lbwD777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
个体身心的某些方面在较早的年龄就已达到较高的发展水平,而有些方面则需要到较晚的年龄阶段才能达到成熟水平。这一特点要求()。
在其他条件相等的情况下,往往一个学习材料两端的项目学习快、记得牢,而中间部分总是学的慢、记得差些。可用于解释这种知识遗忘的理论是()。
迈克尔·富兰在其著作《变革的力量:透视教育改革》中这样生动地写道:“当教师在学校里坐在一起研究学生学习情况的时候,当他们把学生的学业状况和如何教学联系起来的时候,当他们从同事和其他外部优秀经验中获得认识、进一步改进自己教学实践的时候,他们实际上就是处在一个
教师的知识结构的核心是()。
给定资料1.“分类型垃圾桶网上卖断货了”“工作太忙只能求助爸妈或保姆,家人多了很多话题”“公司里个人座位旁的垃圾桶都没有了,扔垃圾人都跑瘦了”……近日,强制垃圾分类成为网络热门话题,一些个人生活习惯悄然改变。上海的宋女士说,为减少垃圾分类错误,已经开始少
2020年,由软件产品、信息技术服务、信息安全产品和服务、嵌入式系统软件四大业务形态构成的我国软件和信息技术服务业持续恢复,收入保持较快增长,信息技术服务加快云化发展,软件应用服务化、平台化趋势明显。2020年,软件产品实现收入22758亿元,同
下列关于地图的叙述正确的是:
文化是怎么来的?似乎是一些学者、作家、艺术家、宗教家折腾出来的,其实这一看法过于________。往深层次看,所有文化形态后面都有某种生态的条件和诱因,广义的生态元素——包括地理、气候、物种等——总是参与对文化形成的制约和________。填入画横线部分
2018年我国全年规模以上港口完成货物吞吐量133亿吨,同比增长2.7%,其中外贸货物吞吐量42亿吨,同比增长2.0%。规模以上港口集装箱吞吐量24955万标准箱,同比增长5.2%。2018年我国各种运输方式货物运输总量同比增量从高到低排序正确的是
已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1..2h-1]中,请写一非递归算法,产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。
随机试题
RecentresearchhasshownthatthestresshormoneCortisol(皮质醇)damagescertainneuronsinthebrainandcannegativelyaffect
《金鲤鱼的百裥裙》先写孙女发现百裥裙,再叙写百裥裙的来历,这种叙述方式是()
Pickouttheappropriateexpressionfromtheeightchoicesandcompletethefollowingdialoguebyblackeningthecorrespondingl
对高层建筑的施工测量应在风力不大于( )级时进行,以保证施工安全和测量数据的准确。
甲企业生产并销售A产品,2016年销售量(正常经营条件下)5000件,单价100元/件,单位变动成本为50元/件,固定成本为130000元。不考虑其他因素,下列说法不正确的是()。
根据《民法通则》规定,如果公民在战争期间下落不明,申请宣告其失踪的法定期间应自()起计算。
单位犯罪的主体包括()
Imaginebeingaskedtospendtwelveorsoyearsofyourlifeinasocietywhichconsistedonlyofmembersofyourownsex.Howw
面向对象系统设计的内容不包括()。
Agoodmodernnewspaperisanextraordinarypieceofreading.Itisremarkablefirstforwhatitcontains:therangeofnewsfro
最新回复
(
0
)