首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
admin
2017-01-04
38
问题
已知下列各种初始状态(长度为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/9JfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
论述魏晋南北朝历史更替的线索.并评价这个时期的政权情况。(东北师范大学2013年历史学综合真题)
1946年5月,中共中央发布的实现“耕者有其田”政策的重要文件是()。
遵义会议后,中央军委决定成立三人军事指挥小组,负责军事行动,这三人是()。①毛泽东②王稼祥③张闻天④周恩来
光绪元年七月,清政府迫于()强烈要求派一位使臣到其国,()成为中国第一个驻外公使
下列选项中,不属于选官制度的是()
在欧盟发展历史上,促使欧盟正式成立的文件是()。
著名的绥靖政策文件《霍尔—赖伐尔协定》是英、法与意大利签订的,密谋发动()。
在巴黎和会上,法国要求严厉制裁德国的目的是()。
编写判定给定的二叉树是否是二叉排序树的函数。
支持多道程序的操作系统,区别于其他操作系统的主要特征为()。
随机试题
利用并行接口芯片8255A的PA口采集8个开关量:K0一K7开关状态,该PB口输出给8个发光二极管,开关状态0不发光,1状态发光,8255A的端口地址为90H一93H,完成程序,画出框图。
以下防治术后肺不张的措施中,错误的是()。
在医用X线诊断中,X线与物质相互作用主要涉及的是
某一挥发油经分馏法分离,从其200~230℃的馏分中用GirardT试剂分离得到一化合物是,该化合物属于
如病人自述误服毒物为敌百虫,忌用下列哪种溶液洗胃如病人出现昏迷,不能用下列哪种方式解毒
患儿表实证的脉象是小儿表虚证脉象是
期货公司变更注册资本,应当经中国证监会审核,期货公司应当确保提交的模拟计算的变更注册资本后的( )满足风险监管指标标准。
ABC公司是一家商业企业,目前正在对2020年的现金管理和应收账款管理进行规划,有关资料如下:资料一:ABC公司2019年年末的资产负债表如下(为简化计算,假设资产负债表各项目的期末余额可代表其全年平均余额):资料二:2019年的信用政策是40天内全
()是美国教育管理普遍采用的基层管理形式。
A、Becausetheywanttoincreasetheirworkingexperience.B、Becausetheydonotyetknowwhatkindofpermanentjobtheywant.C
最新回复
(
0
)