首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>key2>…>k
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>key2>…>k
admin
2023-02-06
48
问题
已知下列各种初始状态(长度为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
学硕统考专业
相关试题推荐
教师职业道德评价是教师个人按照教师道德的要求所进行的自我锻炼、自我教育的过程。()
下列关于课程计划编制原则的说法正确的是()。
美国认知心理学家加德纳将人的智力分为音乐、数学、空间等八种智力,即“多元智能理论”。智力也就是人的认知能力,其核心是()。
无论是在社会主义社会,还是在资本主义社会,甚至是在其他的社会形态里,人们的某些行为规范是相同的,比如尊老爱幼,因此道德是没有阶级性之分的,是人类共有的行为规范。()
生产力的发展促进教学内容、教学方法和教学组织形式的变化。()
化学学习中,钾、钠等属于同一抽象和概括层次的金属元素在学习中互相影响。这种学习的迁移叫作()。
学校教育是由承担教育责任的教师和接受教育的学生共同参与进行的,这是学校活动中()的特殊性。
党的十九大报告指出,到中华人民共和国成立一百年时,基本实现现代化,把我国建设成社会主义现代化国家。综合分析国际国内形势和我国发展条件,从2020年到本世纪中叶可以分为两个阶段来安排,这两个阶段分别是()。
2020年,由软件产品、信息技术服务、信息安全产品和服务、嵌入式系统软件四大业务形态构成的我国软件和信息技术服务业持续恢复,收入保持较快增长,信息技术服务加快云化发展,软件应用服务化、平台化趋势明显。2020年,软件产品实现收入22758亿元,同
一个以向量V[n]存储的栈,其初始栈顶指针top为n+1,则对于x,其正确的进栈操作是()。
随机试题
下列报表中,不在账务处理系统中编制和输出的是()。
桔梗可用治癃闭、便秘,主要是因为
测定各种石灰的有效氧化钙含量,需要使用()试剂。
下列各项中,用以反映项目清偿能力的指标有()。
在存单二级市场上,决定存单转让价格的主要因素是利率、期限和本金。转让时市场利率低于原定利率,转让价格就低。()[2010年考题]
中国公民甲某2007年的收入情况如下:(1)2月份出版一本书,取得稿酬5000元。该书7月至9月被某晚报连载,7月份取得稿费1000元,8月份取得稿费1000元,9月份取得稿费1500元。因该书畅销,10月份出版社增加印数,又取得追加稿酬3000
根据迁移的性质不同,即迁移的影响效果的不同,学习迁移分为()。
公文的作用包括领导与指导作用和行为规范作用,其中领导与指导作用又称为“法规约束作用”。()
党的机关公文应当发给组织,由秘书部门统一管理,一般不发给个人。()
Atfirstshefounditamusingtogive______dressesandribbonstothemaids,butlater,shefounditdull.
最新回复
(
0
)