首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? 前半部分元素按关键字顺序有序,后半部分元素按关键字顺序逆序(key1<key2<…<keym,keym+1>key
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? 前半部分元素按关键字顺序有序,后半部分元素按关键字顺序逆序(key1<key2<…<keym,keym+1>key
admin
2019-08-01
34
问题
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)?
前半部分元素按关键字顺序有序,后半部分元素按关键字顺序逆序(key
1
<key
2
<…<key
m
,key
m+1
>key
m+2
>…>key
n
,m为中间位置)。
选项
答案
在前半部分元素按关键字有序,后半部分按关键字逆序的情况下,后半部分元素的关键字均大于前半部分元素的关键字较次数最少,此时前半部分的比较次数为m一1,后半部分的比较次数为(n一m一1)(n—m+2)/2,因此,总的比较次数为m一1+(n一m一1)(n一m,m+2)/2=(n-1)(n+8)/8(假设n为偶数,m=n/2)。
解析
转载请注明原文地址:https://kaotiyun.com/show/EtCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述十字军东侵的原因和影响。
某新石噐遗址发现大量稻谷壳和稻草,红士,防洪水城垣,此遗址可能是
全国高校院系调整的具体时间是()。
中国第一条自行设计修建的铁路是在()。
20世纪30年代,美国推行“中立”的外交政策。对这一政策的正确表达是()。①适应国内外形势,维护自身利益②反映国际形势走向缓和③维护凡尔赛一华盛顿体系④不利于地区冲突的缓和与解决⑤不关心美洲地区以外
《中国国民党改组宣言》发表的时间是()。
西周的分封制相当发达,是西周的重要政治制度,也是西周历史的一个显著特点。根据所学知识,回答问题周初分封的诸侯有一类是古代帝王的后代,下列国家:①焦②蓟③陈④祝,属于此类的是()
试比较脱机I/O和联机I/Oo
随机试题
简述观察法的特点和局限。
在Excel2010中,公式“=SUM(B1:B4)”等价于_____________。
下列行为中,哪项不构成犯罪?( )
气体燃烧根据在燃烧前可燃气体和氧的混合状况不同,其燃烧方式有()。
从长期来看,随着国民收入的增加,国民边际消费倾向的变化是()。
未完成计划的品种占()。创产值最多的产品是()。
设λ1,λ2是矩阵A的两个不同的特征值,对应的特征向量分别为α1,α2,则α1,A(α1+α2)线性无关的充分必要条件是
WhatisBecky’sfamilyname?WheredoesBeckylive?
Thepopularnotionaboutmarriageandloveisthattheyaresynonymous,thattheyspringfromthesamemotives,andcoverthes
A、Upgradeitsnetworkcapacity.B、Improvecustomerservices.C、Developnewproducts.D、MarketmoreiPhones.A信息明示题。由AT&Tplanst
最新回复
(
0
)