首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1(key2……>keyn); (3)奇数关键字顺序有序,偶数关键字
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1(key2……>keyn); (3)奇数关键字顺序有序,偶数关键字
admin
2014-12-08
80
问题
已知下列各种初始状态(长度为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
学硕统考专业
相关试题推荐
清政府实行“闭关锁国”政策的根本原因是()。
中共十六届五中全会提出,建设社会主义新农村的要求是生产发展和()。
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
新王朝时期出现了什么类型的墓?()
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
随机试题
肾肿瘤的肾外表现不包括【】
毒性剧烈,治疗剂量与中毒剂量相近,使用不当会致人中毒或死亡的药品是直接作用于中枢神经系统,使之兴奋或抑制,连续使用能产生依赖性的药品是
某省电视剧制作中心摄制的作品《星空》正式播出前,邻省的某音像公司制作了盗版光盘。制作中心发现后即向音像公司所在地的某区法院起诉,并在法院立案后,请求法院裁定音像公司停止生产光盘。音像公司在接到应诉通知书及停止生产光盘的裁定后,认为自己根本不是盗版,故继续生
某企业拟拆除该单位的污水处理设施,下列叙述中,不符合环境保护法要求的是()。
关于期货交易所的总经理和副总经理的说法正确的是( )。
一般法人投资者申请开户,应当具备符合企业实际的参与股指期货交易的决策机制和操作流程,决策机制是()。
操作风险评估通常从()两个角度开展。
动物每年的迁徙都是______的,但这就是一个优胜劣汰的自然过程。在“职场动物园”也一样,你的存在是因为被需要、具有价值,如果一个人成为团队的__________,即使团队成员竭力保护你,也难保不会被虎视眈眈的鳄鱼_________。因此,独立、自强、强烈
将一篇在电脑上打好的文章按一定格式排版所属的学习类型是()。
仅以单项选择题的形式出现的问卷属于()
最新回复
(
0
)