首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
admin
2018-08-12
22
问题
已知下列各种初始状态(长度为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/gMRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
()用铜制造了人体模型,并统一了人体的穴位。
关于德意志宗教改革的说法不正确的是()
第二次工业革命引起的生产关系方面最突出的变化是()。
在引进西方科学知识的过程中,李善兰作出的贡献是()
红色割据和军阀割据的本质区别是()。
简述西欧专制制度的特点。
下列有关《布列斯特和约》的说法中,错误的一项是()。
“二战期间,美国研制了原子弹并用于实践;1946年美国投入的第一台电子计算机最初是用于计算炮弹弹道;德国人研制成功的远程液体火箭是用于空袭英国的。”以上史实说明()。
支持多道程序的操作系统,区别于其他操作系统的主要特征为()。
著名的网络OSI七层模型是由()组织提出来的。
随机试题
A.IgAB.IgGC.IgDD.IgEE.IgM天然的ABO血型抗体为
简述定量研究的特点。
符合卵巢恶性肿瘤特点的是
国家规定的有关城乡规划的方针政策的内容不应包括()。
下列关于汇率风险的叙述中,有误的一项是()。
布鲁纳认为,无论我们选择何种学科,都务必使学生理解该学科的基本结构,依此而建立的课程理论是()。
班长、团支书、学习委员去参加全省的文科知识竞赛。文科知识竞赛分为语文、政治和历史三科,每人只参加一科。张老师、王老师、赵老师作了以下猜测:张老师:班长参加了语文竞赛,团支书参加了政治竞赛。王老师:学习委员没参加政治竞赛,团支书参加了语文竞赛。赵老师:班长没
指出下列表述中的正确的表述()。
Mostparents,Isuppose,havehadtheexperienceofreadingabedtimestorytotheirchildren.Andtheymustrealizehowdifficu
FlagDay,June14,isthebirthdayofAmericanflag.Onthisdatein1777,theContinentalCongress【C1】______aresolutionstatin
最新回复
(
0
)