首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1(key2……>keyn); (3)奇数关键字顺序有序,偶数关键字
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1(key2……>keyn); (3)奇数关键字顺序有序,偶数关键字
admin
2014-12-08
73
问题
已知下列各种初始状态(长度为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
学硕统考专业
相关试题推荐
钱穆先生在《国史新论》中说:“汉代宰相是首长制,唐代宰相是委员制。”造成这一现象的原因主要是()的实行。
二战后,出现美苏两极新格局的根本原因是()。
提出历史发展具有其自身规律观点的是()。
波兰三次被瓜分的时间是()
北魏建立和统一的时间分别是()。
比较日本明治维新和中国戊戌变法的异同。
电子计算机的发展经过了四代,①电子数值积分计算机(ENIAC);②集成电路计算机;③大规模集成电路计算机;④晶体管计算机;⑤人工智能计算机,其先后顺序是()。
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
随机试题
关于测量膝关节屈曲角度,下列哪一项不正确
无效合同自订立时起就不具有法律效力,而不是从合同无效原因发现之日或合同无效确认之日起,合同才失去效力,这即是( )。
当高层建筑的玻璃幕墙安装与主体结构施工交叉作业时,在主体结构的施工层下方应设置()
普通发票由省、自治区、直辖市税务机关确定的企业印制,增值税专用发票由国家税务总局确定的企业印制。()
下列关于职业康复的表述,正确的有()。
教师在职业活动中要处理好各种各样的关系,其中最核心的关系是()
根据以下资料。回答101-105题。2006年浙江省外商直接投资项目数为3583个,合同外资金额为1910261万美元。实际外资金额为888935万美元。2007年直接投资项目数为2919个,合同外资金额为2040043万美元,实际外资金额为103
我国对非公有制经济在社会主义的存在、发展及其地位、作用的认识以及相关的方针政策,经历了一个曲折变化和不断深化的发展过程。改革开放以后,我国的所有制结构发生了巨大变化,经过20世纪80年代的发展,把私营经济、中外合资合作经济、外商独资经济同个体经济一起作为公
设平面区域D由直线及两条坐标轴所围成.记则有()
Asisknowntoall,theorganizationandmanagementofwagesandsalariesareverycomplex.Generallyspeaking,theAccountsDep
最新回复
(
0
)