首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)。 (1)关键字自小到大有序(key1<key2<……<keyn); (2)关键字自大到小逆序(
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)。 (1)关键字自小到大有序(key1<key2<……<keyn); (2)关键字自大到小逆序(
admin
2013-12-31
79
问题
已知下列各种初始状态(长度为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-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://www.kaotiyun.com/show/wvxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
林则徐的反英国侵略的策略思想不包括()。
两极格局最终形成的标志是()。
分析英、法、美三国资产阶级革命的特点。
从1939年春天起,国共双方军队在驻防结合部的摩擦冲突不断升级,不是这一时期惨案的是()
穆斯林定居印度后,形成以阿拉伯语字母为基础的语言是()
一战后,凡尔赛条约规定了国际联盟管理15年的德国地区是()
前期罗马帝国时期,关于罗马东方行省的传统手工业产品的叙述,不正确的是()。
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
随机试题
根据外汇管理法律制度的规定,下列关于直接投资项下外汇管理的表述中,不正确的有()。
Tomisoneoftheboys______alwaysontime.
能治疗痈肿疮毒的药物有
患者,男,58岁。近半年来出现尿频、尿急,夜间明显。问题2:首选的影像学检查方法是
掺入引气剂能使混凝土()。
当隧道出现()时,应立即按规定预警并启动应急方案,进行工程抢险。
甲集团有限公司(以下简称甲集团)是一家专注于小家电研发、生产和销售的现代化企业。目前该集团已形成跨区域的管理架构,在南方多地建有多个生产基地,现已成为小家电行业著名企业。ABC会计师事务所承接了甲集团2017年度财务报表审计工作。甲集团共有四家全资子公司,
某兴趣活动小组利用物质问的互变,设计成一个平面魔方,如下图所示:已知:①A、B、C、D、G含有同种元素。②③E是通常情况下密度最小的气体;B与硝酸银溶液反应生成不溶于稀硝酸的白色沉淀,也能将一种氧化物氧化为F,F是含有三种元素的化合物,与A反应生成
在发生重大自然灾害后,现场控制的首要原则是()。
A、ThejetwasinterceptedbyUSairforce.B、Theplane’stranspondermistakenlytransmittedcode.C、Thepilotsrepeatedlytoldc
最新回复
(
0
)