首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)。 (1)关键字自小到大有序(key1<key2<……<keyn); (2)关键字自大到小逆序(
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)。 (1)关键字自小到大有序(key1<key2<……<keyn); (2)关键字自大到小逆序(
admin
2013-12-31
78
问题
已知下列各种初始状态(长度为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://www.kaotiyun.com/show/wvxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
略论中国近现代历史上的“军阀”问题。(北京大学2003年中国通史真题)
试分析第二次世界大战的历史地位。
简述第二国际建立的历史条件。
1928年2月召开的国民党二届四中全会,规定()为国民政府军政最高机关。
无产阶级登上历史舞台的主要标志是()。
毛泽东认为,社会主义这个阶段可分为两个阶段,包括()。
晚清时期清帝年号的正确排序是()
阅读下列材料,回答问题:材料一:列宁说:“我们在夺取政权时便知道,不存在将资本主义制度具体改造成社会主义制度的现存方法……我不知道哪位社会主义者处理过这类问题……我们必须根据实践作出判断。”——摘自《苏联
把中国第一次工人运动的高潮推向顶点的是()。
某主机的MAC地址为00.15.C5.C1.5E.28,IP地址为10.2.128.100(私有地址)。题47-a图是网络拓扑,题47-b图是该主机进行Web请求的1个以太网数据帧前80B的十六进制及ASCII码内容。请参考图中的数据回答以下问题。
随机试题
TTL与门电路正常工作时能带动同类与非门的最大数目称为扇出系数。()
A.脂性肾病B.膜性肾病C.膜增生性肾小球肾炎D.系膜增生性肾小球肾炎引起儿童肾病综合征的最常见原因是
患者男,54岁。因右上颌第一磨牙颊侧牙龈长期瘘管、反复面颊部肿胀而就诊,抗感染治疗后面颊部肿胀消退。本次就诊临床检查见右上颌第一磨牙残冠,牙体破坏严重,患者自诉20年前曾充填(治疗方法不详),现充填物脱落,周围牙龈无明显红肿,颊侧龈近根尖区仍见瘘管,无明显
接受婚前医学检查的人员对检查结果持有异议的
患者,男性,64岁,肝衰竭。为患者做口腔护理时,护士应重点观察的内容是
特许经营项目合作者选择方式中,()最能体现公开、公平和公正的原则。
下列不属于行政诉讼提起应具备的条件是()。
A公司记账本位币为人民币,2012年有关业务如下:(1)A公司通过收购,持有香港甲上市公司发行在外有表决权股份的80%从而拥有该公司的绝对控制权,甲公司的记账本位币为港币。(2)与境外某公司合资在上海浦东新建乙公司,乙公司的记账本位币为美元,A公司参与
疟疾热寄生虫的血红细胞在120夭后被排除出入体。由于这种寄生虫无法转移到新一代的血红细胞内,在一个人迁移到一个没有疟疾的地区120天后;发生在这个人身上的任何发烧情况都不是由疟疾热寄生虫引起的。以下哪一项如果正确,将最严重地削弱以上的结论?
WCS的3个优点是什么?A、无线规划B、无线设计C、无线管理D、无线RF标识(tag)
最新回复
(
0
)