首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>key2>…>k
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>key2>…>k
admin
2023-02-06
46
问题
已知下列各种初始状态(长度为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
学硕统考专业
相关试题推荐
有些学生喜欢把作业拖到最后一刻才开始做,考试前的复习也尽可能拖延到最后一天才开始。学生的上述现象属于()。
现代教学中采用多种辅助的教学组织形式。下列不属于辅助教学组织形式的是()。
“挂钥匙儿童”是指因父母出去工作,放学后独自在家、无人照看的孩子。这是()对孩子带来的负面影响。
目前社会上各类课外补习班层出不穷。许多家长认为只要孩子成绩能得到提高,他们愿意花费大量的金钱和精力让各式补习班“充实”孩子的周末和假期。但参加补课的大部分中小学生表示,他们并非自愿而是被家长强制接受课外补课的,频繁的补课让他们不堪重负。目前这一趋势正向低年
音爆是飞行器在突破音障时,由于对空气的压缩无法迅速传播,会逐渐形成激波面,激波面上高度集中的声学能量引起巨大响声,让人耳感受到短暂而极其强烈的爆炸声。音爆只有在突破音障即超音速飞行时才会产生。音爆云则是以飞行器为中心轴、从机翼前段开始向四周均匀扩散的圆锥状
在高山相夹的谷底,有时能直观地看到地形对云的________:气流翻山越岭被抬升形成波动气流,在气流的波峰与波谷之前,云也随之上下扭曲。在一些情况下,大气温度和高度呈反比,处于波谷处的温度更高,达不到云________的温度,而波峰处的温度可以形成云,这样
《中共中央国务院关于加快建设全国统一大市场的意见》于2022年4月发布。提出从全局和战略高度加快建设全国统一大市场。下列做法符合建设全国统一大市场要求的是:
某地打算在绿地上建两个圆形花坛,如下图所示,大圆的直径为6米,小圆的直径为2米,修建期间暂时在外围设置围栏。已知围栏呈矩形,大圆与围栏的三条边相切,小圆与围栏的两条边相切,且两圆相切,那么矩形围栏的面积是多少平方米?
在互联网社交化、移动化背景下,算法应用使广告的个性化、强互动和精准性特征变得非常突出,_________。一方面,广告效果归因变得更加复杂。用户在多个社交平台中积极互动,消费者跨设备、跨媒体、线上线下行为交叉的情况也越来越多,如何精确测量单一平台的广告效果
随机试题
乳腺癌最多见于乳腺的
《医疗机构制剂许可证》项目中,由药品监督管理部门核准的许可事项为
建设单位收到监理工程师签发的《工程款支付证书》以后,应()向承包单位支付工程款。
我国个人所得税的纳税人分为居民和非居民。居民是指()的个人。
强烈和持久的应激反应会()。
我国是统一的多民族国家。下列关于我国国家结构形式的表述错误的是()。
被调查人既涉嫌严重职务违法或者职务犯罪,又涉嫌其他违法犯罪的,一般应当由监察机关为主调查,其他机关予以协助。()
声音:音乐
《明史.刑法志三》:“内官同法司录囚,始于正统六年,命何文渊、王文审行在疑狱,敕同内官兴安。周忱、郭瑾往南京,敕亦如之。时虽未定五年大审之制,而南北内官得与三法司刑狱矣……成化八年,命司礼太监王高、少监宋文毅两京会审,而各省恤刑之差,亦以是岁而定。十七年辛
圆x2+y2-2x-2y+1=0上的点到直线x-y=2的距离的最小值是()
最新回复
(
0
)