首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1(key2……>keyn); (3)奇数关键字顺序有序,偶数关键字
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1(key2……>keyn); (3)奇数关键字顺序有序,偶数关键字
admin
2014-12-08
79
问题
已知下列各种初始状态(长度为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://www.kaotiyun.com/show/gOxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
清政府实行“闭关锁国”政策的根本原因是()。
黎公社失败的根本原因是()。
下列对春秋时期各国称霸的顺序描述错误的选项是()
外国侵略者通过不平等条约取得的特权中,按时间先后顺序排列应是()。①外国商船和军舰可以在长江各口岸自由航行②外国人可以在通商口岸开设工厂③可在通商口岸建立教堂④领事裁判权和片面最惠国待遇
北魏建立和统一的时间分别是()。
洪秀全以宗教手段组织起义,主要利用的是()。
洋务运动时期,首批赴欧海军留学生派出的时间是()。
关于俄国工业革命的特点,正确的是()。①外国资本和技术在工业革命中起着重要的作用②工业革命发展极不平衡③企业资本有机构成低,技术落后④工业革命所需的资金主要来自对海外殖民地的掠夺
欧洲历史上第一部系统完备的法典是()。
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
随机试题
某企业有大量的对外投资业务,计划设计包括投资取得、持有期间利息及股利的收取、期末计价、投资收回等全过程的会计核算控制制度。要求:(1)代为设计投资取得控制制度;(2)代为设计投资保管控制制度;(3)代为设计投资收益控制制度;
Successfor99CentsHowdoyousellthingsinatimewhentheeconomyisdownandpeoplejustdon’twantto【B1】________?
阴离子表面活性剂有非离子表面活性剂
证券投资咨询机构及其投资咨询人员,应当完整、客观、准确地运用有关信息、资料向投资人或者客户提供投资分析、预测和建议,()。I.引用有关信息、资料时,应当注明出处Ⅱ.引用有关信息、资料时,应当注明著作权人Ⅲ.不得篡改有关
全国社会保险基金预算草案的编制工作由()完成。
李老师一个学期对父亲是副乡长的小壮家访了8次,却从未对需要帮助的留守儿童小龙家访过。李老师的做法()。
MarketShare
Goodhygienehelpsto________theriskofinfection.
选做题Ⅰ阅读下列材料材料1恩格斯:“我们不要过分陶醉于我们人类对自然界的胜利。对于每一次这样的胜利,自然界都对我们进行报复”。“因此,我们每走一步都要记住……我们对于自然界的全部统治力量,就在于我们比其他一切生物强,能够认识和正确运用自然
A、 B、 C、 D、 A
最新回复
(
0
)