首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1<key2<…<keyn); (2)关键字自大到小逆序(key1>
admin
2018-08-12
52
问题
已知下列各种初始状态(长度为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
学硕统考专业
相关试题推荐
曾被日本维新派人士视为“枕中鸿宝”,对日本明治维新产生重要影响的著作是()。
简述马歇尔计划的客观作用。
明代初年,废中书省,“六部”直接向皇帝负责,分割了宰相的权力,同时与“六部”合称为“七卿”,与六部地位不相上下的是()。
南朝“寒人掌机要”的现象及其历史背景与影响。
系统地阐明道家思想的著作《淮南鸿烈》,也叫《淮南子》,是汉武帝时()集宾客写成的。《淮南子》问世时,黄老思想在政治上已不占支配地位了。
在3~4世纪蛮族入侵罗马帝国的时候,袭击不列颠海岸的是()。
马克思说:巴黎公社“只不过是在特殊条件下的一个城市起义”。其含义是()。
汉章帝会群儒于白虎观,讨论经义,由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书,这部书系统地吸收了阴阳五行和谶纬之学,形成今文经学派的主要观点。
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
随机试题
在世界范围内,实行两党制的国家有()
细菌基因的转移和重组方式不包括
关于急性胰腺炎的腹痛特点叙述正确的是()
处方中h.S是指处方中p.o是指
在抵押权人同意,抵押人转让抵押物时,转让所得的价款,应当向抵押权人提前清偿所担保的债权或者向与抵押权人约定的第三人提存。()
按《公路工程竣(交)工验收办法》的规定,公路工程(合同段)进行交工验收应具备的条件包括()
下列脚手架工程中,其专项施工方案需要进行专家论证的是()。
下列企业融资方式中,属于间接融资的有()。Ⅰ.发行股票Ⅱ.银行贷款Ⅲ.发行债券Ⅳ.从国际金融机构借款
居民身份证及其他人口证件的签发和验证工作属于抬安行政管理工作中的一项内容。( )
阅读材料回答问题:材料1社会主义的本质,是解放生产力,发展生产力,消灭剥削,消除两极分化,最终达到共同富裕。就是要对大家讲这个道理。走社会主义道路,就是要逐步实现共同富裕。共同富裕的构想是这样提出的:一部分地区有条件先发展起来,一部分地区发展慢点,先
最新回复
(
0
)