首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>key2>…>k
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>key2>…>k
admin
2023-02-06
29
问题
已知下列各种初始状态(长度为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://jikaoti.com/ti/3rPiFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
某校通过创设良好的环境,如提供美观清洁的校园、朴实庄重的校舍、明亮整洁的教室,营造良好的学风班风来对学生进行道德教育。这种做法体现的德育方法的是()。
教育实验分组设计中,组内设计是指一组被试中的每一个被试都接受整个实验的各种实验处理。组内设计的优点不包括()。
“六一”儿童节快到了,大班的文老师主动与幼儿园所在的社区联系,商量带班里的幼儿到社区开展游园活动;同时还积极与家长们沟通,希望能对游园活动建言献策。文老师的这种做法体现了幼儿教育的()。
语文课上,小希总是喜欢和周围的同学交头接耳,他还喜欢不停地做小动作,李老师多次提醒、制止他,但无济于事。时间长了,李老师开始责骂、讥讽、奚落他,有时也罚他站着听课,导致小希越来越不喜欢上语文课,甚至出现厌学情绪。小希家长找李老师询问原因,李老师说:“我教育
人们把自己是否能够成功地从事某一成就行为的主观判断称为自我效能感。()
材料一新春伊始,《新农村》记者小梁到基层调研,以下是他在两个村庄采访的片段。“村子真于净”,这是外来人对东各村的第一印象。村道上见不到一张纸片,家家院里院外也清清爽爽。79岁的高大妈笑着把小梁往屋里迎。冬季取暖煤改电以后,高大妈家装了地暖,外面再
深度学习是指在模仿人脑机制的神经网络中,对人工神经元的层进行了“多层处理”。深度学习不仅可以让AI(人工智能)读取大量图片,还可以让AI自主提取图片特征。得益于深度学习技术的面世,只要有大量数据,AI就能以极高的准确率进行学习,从而大幅度拓展了AI的应用范
我国全年降水量、河川径流量60%-80%集中在汛期;同时,降水和径流的年际变化显著,最大和最小年降水量南方地区相差2-4倍,北方地区相差3-6倍,径流量最大和最小年份相差10-15倍。天然来水过程与需水过程不匹配,很多地区出现旱涝急转。水资源开发利用难度加
①发动机为了持续提供稳定的动力,需要曲轴、机油过滤器、交流发电机、风扇、分电盘、阀门、线圈和气缸等零部件的配合②每一个零部件,都会增加动力的损耗③汽车是工业社会发展至今最复杂的工业产品,是数以千计机械部件的精密集合体④因为这么复杂的机械结构,机械汽车
在互联网社交化、移动化背景下,算法应用使广告的个性化、强互动和精准性特征变得非常突出,_________。一方面,广告效果归因变得更加复杂。用户在多个社交平台中积极互动,消费者跨设备、跨媒体、线上线下行为交叉的情况也越来越多,如何精确测量单一平台的广告效果
随机试题
管理本身不能直接创造价值,它必须借助于被管理者及其他各种条件,并通过他们来体现或实现管理的价值。这说明管理学是一门【】
在Excel2010中,若在单元格A6中输入“=A4/A5”,而在A4单元格中输入“15”,在A5单元格中输入“=1.1”,则单元格A6中显示________。
A.华法林B.氯吡格雷C.低分子肝素D.辛伐他汀E.硫氮酮急性冠脉综合征抗凝治疗首选
环保行政主管部门应在收到申请环保设施竣工验收之日起()日内完成验收。验收合格后,才能投入生产和使用。
根据《票据法》的规定,经当事人申请并提供担保,可以依法采取保全措施和执行措施的票据有()。
某理论认为员工的激励程度来源于对自己和参照对象的产出一投人比率的主观比较感觉。这一理论是()
《义务教育化学课程标准(2011年版)》,在第四部分“实施建议”中提出了“评价建议”。以下观点,不是其所提倡的是()。
确定我国经济体制改革目标的核心问题是正确认识和处理()。
在()情况下,不存在复议第三人参加复议的问题。
A、Informationonindividualsshouldnotbeusedwithoutauthorizedpurposes.B、Thestoredinformationshouldbekeptfromindivi
最新回复
(
0
)