首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
admin
2018-08-12
49
问题
已知下列各种初始状态(长度为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/gMRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
中国洋务运动所采取的“自强”、“求富”的途径是()
资产阶级改良道路行不通,资产阶级共和国方案夭折,其共同原因在于()。①中国封建势力的强大②帝国主义列强的直接破坏③资产阶级的软弱妥协④没有充分地发动人民群众
下列不属于“一国两制”的基本内容的是()。
中国近代第一所外语学校、同时也是新式学堂的是()。
下列选项中不属于《国际联盟盟约》内容的是()。
我国历史上一次有周密计划、经过长期准备并利用宗教形式组织和发动的农民起义是()。
一个客户机利用FTP协议从服务器上下载文件,如下图所示为整个过程中协议交换的过程,请回答如下问题:(1)该协议层图中第四层协议是什么?(2)如果FTP客户端采用了LIST命令来获得FTP服务器上的文件列表,该列表采用什么端口传输?
某模型机的通路结构如下图所示,用寄存器传送语句(如PC→MAR),拟出下列指令从读取到执行的完整流程。(1)数据传送指令MOVX(R0),Y(R1),源和目的操作数地址均采用变址寻址,第1个参数X为源操作数的形式地址,第2个参数为目的操作数的形
一台模型机共有7条指令,主频25MHz,各指令的使用频率与CPI如下表所示,该机有8位和16位两种指令字长,采用2—4扩展操作码。8位字长指令为寄存器一寄存器(R—R)二地址类型,16位字长指令为寄存器~存储器(R—M)二地址变址类型(地址码范围在一12
驱动调度算法中,()算法可能会随时改变移动臂的运动方向。
随机试题
卵泡发育的过程中,不包括以下哪项
急性胰腺炎时,血清淀粉酶变化的特点,下列哪项不正确()
枳术丸的功用是
既含蟾酥又含雄黄的中成药有()。
某公司承建一滨海电厂的输煤系统改扩建工程,该电厂要求输煤系统能尽快投入生产,因此该工程工期非常紧张。施工单位按业主要求编制施工组织设计并加快施工速度,昼夜赶工,按合同要求施工内容已全部完工,并进入试运转的尾声。为了下一步顺利进行竣工验收的检查工作
一般认为,基金起源于()。
多样化投资分散风险的风险管理策略行之有效的前提条件是()。
根据合伙企业法律制度的规定,有限合伙人的下列行为,不视为执行合伙事务的有()。
设A为m阶实对称矩阵且正定,B为m×n实矩阵,BT为B的转置矩阵,试证:BTAB为正定矩阵的充分必要条件是r(B)=n.
Here______apen,afewenvelopesandsomepaperforyou.
最新回复
(
0
)