首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1(key2……>keyn); (3)奇数关键字顺序有序,偶数关键字
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1(key2……>keyn); (3)奇数关键字顺序有序,偶数关键字
admin
2014-12-08
30
问题
已知下列各种初始状态(长度为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);②集成电路计算机;③大规模集成电路计算机;④晶体管计算机;⑤人工智能计算机,其先后顺序是()。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
随机试题
能加快反应速度的催化剂为正催化剂。
比较马斯洛的需求层次理论和赫茨伯格的双因素理论,马斯洛提出的五种需求中,属于保健因素的是()
充填完好的根管如果牙冠部分没有暂封,则()
下列有关实行从量定额与从价定率计征办法依据,说法正确的是( )。
如果说在线旅行服务企业面临着盈利压力,传统旅行社面临的其实是生存问题。传统旅行社还在用QQ、微信、传真、邮件、电话等传统方式进行供应链及内部运营管理。传统旅行社的业务离不开产品和渠道,与在线旅游服务企业相比,传统旅行社除了产品不够丰富。在用户体验、用户挖掘
2015年10月26日到29日,中国共产党第十八届中央委员会第五次全体会议在北京举行,审议通过了《中共中央关于制定国民经济和社会发展第十三个五年规划的建议》,会议强调:要实现到2020年全面建成小康社会的目标,必须牢固树立并切实贯彻的发展理念是()
下面各项关于世界科技史上近代科学革命的表述,错误的有:
(2012年下半年上午试题32)在屏蔽软件错误的容错系统中,冗余附加技术的构成不包括______。
以下程序的输出结果是()。 list=[[0,1,2],”123.0”,”python”] a=all(list[0]) b=list[1].split(”.”) c=ascii(list[2]) prin
Announcement(通知)GoodMorning,ladiesandgentlemen.MayIdrawyourattention(注意)tothebookSafetyinFlight?YouWillfindthe
最新回复
(
0
)