首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1(key2……>keyn); (3)奇数关键字顺序有序,偶数关键字
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1(key2……>keyn); (3)奇数关键字顺序有序,偶数关键字
admin
2014-12-08
77
问题
已知下列各种初始状态(长度为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
学硕统考专业
相关试题推荐
新石器时代的房屋建筑根据环境的不同形成了不同的类型,()地区多为干栏式建筑。
据史料记载,隋唐时“民间佛经多于六经数十百倍”,造成这一现象的原因是()①统治者推崇佛教②佛经浅显易懂③雕版印刷佛经④人们盼望安定
比绿林军动稍后,琅琊人()在莒县暴动,为了作战时与敌人相区别,农民军把眉毛涂红,被称为赤眉军。
晚清时期下列武装力量出现的先后顺序是
洪秀全以宗教手段组织起义,主要利用的是()。
日本明治维新和中国戊戌变法一成一败的原因。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
随机试题
《张中丞传后叙》中抨击的人物是________。
男,67岁,肺癌术后3个月,自觉全身多处骨骼疼痛。X线检查,胸、背部和腰部骨骼未见明显异常。如果上述检查未能证实有肿瘤骨转移,应要求患者做什么
25岁男性,左下后牙疼痛8天,逐渐加重,现张口度仅0.5cm,阻生,左侧咬肌区红肿,颌下淋巴结肿大压痛,体温37.8℃,最可能的诊断是
20岁未婚女性,早孕自行药物流产,妊娠产物排出情况不明,此后阴道淋漓出血20天不净,则以下处理中哪项最合适
赵某因绑架罪被甲省A市中级人民法院判处死刑缓期两年执行,后交付甲省B市监狱执行。死刑缓期执行期间.赵某脱逃至乙省C市实施抢劫被抓获.C市中级人民法院一审以抢劫罪判处无期徒刑。赵某不服判决,向乙省高级人民法院上诉。乙省高级人民法院二审维持一审判决。此案最终经
沥青混合料车辙试验是在规定条件下,测量试件每增加1mm变形需要行车的次数。()
用浆液灌入岩体裂隙中以提高岩体的整体性和抗变形能力的灌浆称为()灌浆。
虚假同感偏差又称“虚假一致性偏差”,指的是人们常常会高估或夸大自己的信念、判断及行为的普遍性。当遇到与此相冲突的信息时,这种偏差使人坚持自己的社会知觉。根据上述定义,下列不属于虚假同感偏差的是:
简述同伴关系的作用。
A、Hewon’tbeabletofinishtheworksoon.B、Thewomanmustwaitforalongtime.C、Hewillfinishthepapersoon.D、Thewoman
最新回复
(
0
)