首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
admin
2017-01-04
67
问题
已知下列各种初始状态(长度为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/vLRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简要回答国民经济恢复的表现、原因和意义。
试述18世纪末至19世纪末美国西进运动的进程及对美国近代化的影响。(华东师范大学1999年世界近现代史真题)
试述十月革命的特点、道路和意义。
以北宋三大发明为例简述北宋科学技术的特征。
1946年5月,中共中央发布的实现“耕者有其田”政策的重要文件是()。
下列对1918年德国十一月革命说法不正确的是()。
唐代在广州设立管理对外商务的是()。
下列不属于延安整风运动的文件是()。
列宁在()报告中论证了在俄国实现和平过渡的可能性和必要性。
临界区是指()。
随机试题
脑中氨的主要去路是()
下列哪型白斑恶变倾向最小
在基本建设项目竣工财务决算表中,属于资金占用项目的是()。
在法定减免税之外.国家按照困际通行规则和我国实际情况,制定发布的有关进出口货物减免关税的政策,称为特定或政策性减免税。下列货物属于特定减免税的有()。
下列关于正态分布的描述,正确的是()。
甲公司生产的手表,因质量上乘、款式新颖、价廉物美而深受消费者的喜爱。乙公司大量购入这种手表后,未经甲公司同意,将手表上甲公司的注册商标换成乙公司的注册商标予以销售。对乙公司的行为,下列说法哪些是正确的?
华盛顿国立气象研究所的墙上有这么一句话:“当我们做对了,没有人会记得;当我们做错了,没有人会忘记。”气象研究所的墙上写这句话的目的是()。
仔细观察会发现,苍蝇在落下之后,经常把两只前腿蹭来蹭去,这样做的原因是为了()。
在秦朝司法审判结束之后宣读判决书被称为()
(09年)设(I)求满足Aξ2=ξ1,A2ξ3=ξ1的所有向量ξ2,ξ3;(Ⅱ)对(I)中的任意向量ξ2,ξ3,证明ξ1,ξ2,ξ3线性无关.
最新回复
(
0
)