首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)。 (1)关键字自小到大有序(key1<key2<……<keyn); (2)关键字自大到小逆序(
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)。 (1)关键字自小到大有序(key1<key2<……<keyn); (2)关键字自大到小逆序(
admin
2013-12-31
36
问题
已知下列各种初始状态(长度为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-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://jikaoti.com/ti/P9ajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
略论中国近现代历史上的“军阀”问题。(北京大学2003年中国通史真题)
简述土地革命时期中共土地政策的演变过程。
英国长达190年殖民统治在印度结束的标志是()。
1928年2月召开的国民党二届四中全会,规定()为国民政府军政最高机关。
()的创建是清朝兵制的重大改革,对晚清政治产生了深刻的影响。
关于荷马时代的叙述,不正确的是()。
《汉谟拉比法典》中规定:如果奴隶胆敢对主人说:“你不是我的主人。”他的耳朵就要被割掉。这部法典诞生于()。
二月革命后,俄国为什么会出现两个政权并存的局面?
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
某模型机的通路结构如下图所示,用寄存器传送语句(如PC→MAR),拟出下列指令从读取到执行的完整流程。(1)数据传送指令MOVX(R0),Y(R1),源和目的操作数地址均采用变址寻址,第1个参数X为源操作数的形式地址,第2个参数为目的操作数的形
随机试题
当出现中断事件后,将断点信息保护起来的做法是
didn’tcome,hascome,can’tcome,at,around,withPutthefoodwherethecat____________it.
以下哪项不是风湿性关节炎的临床特点
下列不属于注册城市规划师执业考试大纲要求应掌握的法规文件是()。
【案例四】背景材料:某市政桥梁工程采用钻孔灌注桩基础;上部结构为预应力混凝土连续箱梁,采用钢管支架法施工。支架地基表层为4.5m厚杂填土,地下水位位于地面以下0.5m。主墩承台基坑平面尺寸为10m×6m,挖深为4.5m,采用9
甲公司共有20名总部管理人员。2016年1月1日甲公司向上述管理人员出售的住房,平均每套购买价为280万元,出售的价格为每套160万元。售房协议规定,职工在取得住房后必须在该公司服务满10年(含2016年1月)。2016年7月15日甲公司将本公司生产的笔记
外商投资企业和外国企业接受捐赠的资产,适用的税收政策有()。
卖出汇率是客户向银行卖出外汇时所使用的汇率。()
有两个作业A和B,分别在7:00和8:30到达系统,它们估计的计算时间分别为0.8h和0.1h,系统在9:00开始以响应比高者优先算法进行调度,请问在单道执行时A、B两道作业被选中时的响应比()。
Bynowyouknowthat【C1】______yourmoney’sworthisnotjustamatterofluck.Itismoreoftenthe【C2】______of’buyingskill.【
最新回复
(
0
)