首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
admin
2018-08-12
31
问题
已知下列各种初始状态(长度为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
学硕统考专业
相关试题推荐
克里特文明的文字类型是()。
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
第一国际成立前,各国无产阶级强烈要求加强国际团结的直接原因是()。
论述隋朝加强中央集权和巩固统一的措施。
简述汉光武帝加强中央集权制度的措施。
解放军渡江战役中横渡长江的东西两个攻击点是()。
明代张居正推行的“一条鞭法”,是继“两税法”之后赋役制度的又一次重大改革。该法在全面推行前曾在南方部分地区试行,最早出现于()
“两强标准”
某机字长32位,主存容量32MB,按字节编址;该机的Cache采用4路组相联映射方式,Cache容量为16KB,块长为4个字,试回答下列问题:(1)主存地址位数为多少?(2)画出主存地址格式示意图,注明各字段名称及位数。(3)设该Ca
一个在以太网中的主机试图发送一个帧,当它尝试了16次仍然失败之后,它应该()。
随机试题
下列情形中,社会工作者不宜采用小组工作方法的有()。
当一种可变投入的平均产量曲线与边际产量曲线相交时()
MATLAB也是一种能用于数值计算的高级程序设计语言。()
红舌和绛舌皆主
成年女性耻骨弓的角度平均是:
治疗痢疾表邪未解而里热已盛者,应首选()
企业年金计划的举办方式中,企业代表职工与保险公司签订保险合同,企业职工的养老责任由保险公司承担的方式属于()。
论述皮亚杰的道德发展阶段论。
PublicStorageisaninternationalself-storagecompany.Itrentsspaces,rangingfromcloset-sized(橱柜大小的)unitstoonesthatcan
Whatthepassagetellsuscanbesummarizedbythestatementthat______.Accordingtothepassage,thosewholiveinatraditi
最新回复
(
0
)