首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
admin
2019-08-15
24
问题
已知下列各种初始状态(长度为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/kKCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
为了顺利开展武装起义的准备工作,在彼得格勒苏维埃中成立了()。
从“鲁尔危机”的发生到《道威斯计划》的实施,西方国际关系变化对当时有关国家的影响是()。①美国势力进一步向欧洲渗透②英国达到了限制法国、保持均势的目的③德国获得重建经济的有利时机④法国扩充实力争霸欧洲的计划遭
一战后,英国拒绝加入法国的安全保障体系,其原因是()。
卡诺莎事件
假设系统的所有资源是同类型的,系统中的进程每次申请资源数最多1个,那么,下面列出的4种情况中,()可能发生死锁。情况序号系统中进程数资源总量
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
给定单链表的结点结构typedefstructnode*link;structnode{intitem,linknext;);将两个升序单链表归并为一个升序单链表。
下列选项中,描述浮点数操作速度指标的是____。
假设有一个进程拥有两个线程(编号为0和1)需要去访问同一个共享资源,为了避免竞争状态的问题,必须实现一种互斥机制,使得在任何时候只能有一个线程在访问这个资源。假设有如下的一段代码:intflagL22;/*flag数组,初始化为FALSE*/
随机试题
移走原子中某轨道电子所需的最小能量,称为这个电子的
A.生长激素B.胰岛素C.甲状腺激素D.降钙素E.皮质醇()可提高基础代谢率,具有明显的增加产热作用
省级人民政府可以制定严于国家排放标准的地方排放标准,但制定()大气污染物地方排放标准严于国家排放标准的,须报国务院批准。
自然人甲与乙签订了年利率为30%、为期1年的1000万元借款合同。后双方又签订了房屋买卖合同,约定:“甲把房屋卖给乙,房款为甲的借款本息之和。甲须在一年内以该房款分6期回购房屋。如甲不回购,乙有权直接取得房屋所有权。”乙交付借款时,甲出具收到全部房款的收据
某地上16层商住楼,地下2层(未示出).系底层大空间剪力墙结构,如题图所示(仅表示1/2.另一半对称),2~16层均布置有剪力墙,其中第①、④、⑦轴线剪力墙落地,第②、③、⑤、⑥轴线为框支剪力墙。该建筑位于7度地震区,抗震设防类别丙类。设计基本地震加速度为
()是一种地质现象,主要是由于地球的内力作用而产生的一种地壳振动现象,其中绝大多数伴随岩层断裂错动的产生。
国内某产品生产商向我国商务部申请对从甲国进口的该产品进行反倾销调查,该产品的国内生产商共有100多家。根据对外贸易法律制度的规定,下列说法不正确的有()。
全国人大常委会每届任期同全国人大,它行使职权到()。
键盘可用于直接输入()。A.数据B.文本C.程序和命令D.图形、图像
ThemoreIreflectonthe23impressiveyearssincethesigningoftheMontrealProtocol,themoreIrealizewhatfar-reachingl
最新回复
(
0
)