首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
admin
2017-01-04
69
问题
已知下列各种初始状态(长度为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
学硕统考专业
相关试题推荐
明朝在防御蒙古贵族方面采取了哪些重大措施?其代价和影响如何?
1916年研究短波无线电通信,为现代远距离无线电通信奠定了基础的发明家是()。
埃及曾两次被波斯帝国征服,波斯第二次征服埃及的时间是()。
纳粹德国公开撕毁《凡尔赛和约》的步骤有()。①大量扩展陆军,重建空军,建造军舰②迫害犹太人③退出国联④开进莱茵非军事区
隋统一全国时,与隋军平定岭南地区有关的人员是()。①洗夫人②慕容三藏③孙夫人④裴矩
战时共产主义政策中对后来的工农联盟最能构成威胁的是()。
武则天时期,为了管理天山以北的广大区域而设立了()。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
编写一个算法,实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
可重定位内存分区的目的为了()。
随机试题
影响时间知觉的因素。
肝气郁结证患者的闻诊特点多为
女,42岁。间断发热、腰痛伴尿频2年,每次发作应用抗生素治疗可好转。近半年来夜尿增多。尿常规:尿比重1.015,RBC0~2/HP,WBC3~5/HP。静脉肾盂造影见肾盂肾盏狭窄变形,肾小盏扩张。首先考虑的诊断是()
运用股指期货等工具保护战略投资组合,以限制下跌的风险的投资方式是()。
该公司2002年12月15日采购的甲原材料的单位成本为()元。该公司2002年12月完工产品成本中材料费用总额为()元。
甲公司与乙公司投资设立合营企业A公司,持股比例各占50%,共同控制A公司。甲、乙公司约定对A公司同比例增资。甲公司与乙公司签订增资协议的同时,甲公司与A公司签订技术投资及技术出租协议。具体情况如下:(1)2×16年1月1日,甲公司以M技术(无形资产)作为
国务院和地方各级人民政府根据()的原则,领导和管理教育工作。
有如下程序:#includeusingnamespacestd;classAA{public:AA(){cout
Readthefollowingpassageandchoosethebestwordforeachspace.Forquestions26~45,markoneletterA,B,CorDonthe
WhatisthemainpurposeofPresidentObama’svisittoRepublicofKorea?
最新回复
(
0
)