首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
admin
2017-01-04
37
问题
已知下列各种初始状态(长度为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/vLRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
遵义会议后,中央军委决定成立三人军事指挥小组,负责军事行动,这三人是()。①毛泽东②王稼祥③张闻天④周恩来
西汉末年,()对太初历作了系统的解释,并调整为三统历。这是中国第一部记载完整的历法。
隋唐时的冶铸业已普遍采用的技术包括()①切削②抛光③焊接④使用机械动力
1543年,发表了解剖学专著《人体结构》的是()。
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
试析第三次科学技术革命对人类社会和历史进程的影响。
第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式。最早提出这种方式的是()。
我国第一部系统的史学理论著作是()。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
举例说明P、V操作为什么要求设计成原语(即对同一信号量上的操作必须互斥)。P(S)操作:S.value--;If(S.value<0){AddthisprocesstoS.L;Block();
随机试题
意义学习需要具备哪些条件?
下列关于甲状腺激素对物质代谢影响的叙述,正确的是
A.膀胱俞、中极、行间、内庭B.阴谷、肾俞、三焦俞、气海、委阳C.脾俞、胃俞、足三里、血海D.三阴交、阴陵泉、膀胱俞、中极E.关元、中极、足三里、肾俞治疗癃闭湿热下注证,应首选()
下列主体中,不能作为票据保证人的有()。
一位教师讲“生物与环境”一节时,结合教学讲解了我国目前需要解决的环境保护和生态平衡等有关的知识,激发了学生的学习兴趣。这体现了生物学的()教学原则。
教育与生产相脱离,教育具有阶级性、道统性、专制性、刻板性和象征性等。这些属于()的特征。
对文艺复兴、宗教改革、天主教改革三者关系表述正确的一项是()
根据《宪法》和《民族区域自治法》的规定,下列既有权制定自治条例,也有权制定地方性法规的是()。
MakingYourselfaGoodRecordIfyouareanAmericanandyouthinkyoumightneedtoborrowmoneysomeday,thebestthingtodo
A、Hecan’thelpthewoman,becauseit’stoodarktosee.B、Hecan’tmeetthewoman,becausehegoestotheinterview.C、Hecan’t
最新回复
(
0
)