首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1(key2……>keyn); (3)奇数关键字顺序有序,偶数关键字
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1(key2……>keyn); (3)奇数关键字顺序有序,偶数关键字
admin
2014-12-08
50
问题
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)?
(1)关键字自小到大有序(key
1
(key
2
<……
n);
(2)关键字自大到小逆序(key
1
>key
2
>……>key
n
);
(3)奇数关键字顺序有序,偶数关键字顺序有序(key
1
3……,key
2
4<……)。
(4)前半部分元素按关键字顺序有序,后半部分元素按关键字顺序逆序(key
21
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://kaotiyun.com/show/gOxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
列宁认为,既然俄国无法直接过渡到社会主义,那么就“应该利用资本主义作为小生产和社会主义的中间环节”。为此而采取的政策是()。
二战后,出现美苏两极新格局的根本原因是()。
中共十六届五中全会提出,建设社会主义新农村的要求是生产发展和()。
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
欧洲历史上第一部系统完备的法典是()。
新王朝时期出现了什么类型的墓?()
比较日本明治维新和中国戊戌变法的异同。
克里特文明的文字类型是()。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
随机试题
求函数f(χ)=χe-χ在定义域内的最大值和最小值。
属于胆碱能受体的是
A.单体酶B.寡聚酶C.结合酶D.多功能酶E.单纯酶(2002年)由丁基因融合,形成由一条多肽链组成却具有多种不同催化功能的酶是
患者,女,26岁。每次过马路遇到红灯时总有冲动朝疾驰的车跑去,虽然没有这么做过,但这种冲动不断出现,患者非常不安。护士评估时考虑为
肉眼血尿为1000ml尿中血的毫升数为
观察瞳孔的变化应包括()。
在会计软件运行之前,企业应该根据国家统一的()来选择相应的运行控制参数,以符合企业核算的要求。
Valentine’sDaymaycomefromtheancientRomanfeastofLupercalia.(1)_____thefiercewolvesroamednearby,theoldRomansca
Apostman’sjobmustbeaboringone.
祝福
最新回复
(
0
)