首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1(key2……>keyn); (3)奇数关键字顺序有序,偶数关键字
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key1(key2……>keyn); (3)奇数关键字顺序有序,偶数关键字
admin
2014-12-08
47
问题
已知下列各种初始状态(长度为n)元素,试问当利用直接插入法进行排序时,至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)?
(1)关键字自小到大有序(key
1
(key
2
<……
n);
(2)关键字自大到小逆序(key
1
>key
2
>……>key
n
);
(3)奇数关键字顺序有序,偶数关键字顺序有序(key
1
3……,key
2
4<……)。
(4)前半部分元素按关键字顺序有序,后半部分元素按关键字顺序逆序(key
21
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一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/gOxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
新石器时代的房屋建筑根据环境的不同形成了不同的类型,()地区多为干栏式建筑。
义和团运动排外思想产生的根本原因是()。
国民政府对日宣战的时间是()。
“文化大革命”发动的两个纲领性文件是()。
二战后,出现美苏两极新格局的根本原因是()。
洪秀全以宗教手段组织起义,主要利用的是()。
我国第一部系统的史学理论著作是()。
洋务运动时期,首批赴欧海军留学生派出的时间是()。
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
随机试题
关于刑事案件的延期审理和中止审理,下列哪些说法是正确的?
5,9,17,33,()
汽车正常行驶过程中所受到的滚动阻力,主要是由于车轮滚动时轮胎与路面的变形产生的,其数值的大小与汽车总质量、轮胎结构和气压以及路面的性质有关。()
为了把XML能够以可视化的形式呈现给最终用户,XML还需要的可扩展语言有()
不属于与地下工程施工有关的基础技术是()。
下列()属于利用绿色清洁技术生产的产品。
本期所得税费用与本期递延所得税费用相等。()
甲因乙不能偿还欠款将其告上法庭,并称有关证据被公安机关办理其他案件时予以扣押,故不能提供证据。法官负责任地到公安机关调查,并复制了相关证据材料。此举使甲最终胜诉。运用法理学的知识分析该法官的行为是否适当。
A和B都是n阶矩阵.给出下列条件①A是数量矩阵.②A和B都可逆.③(A+B)2=A2+2AB+B2.④AB=cE.⑤(AB)2=A2B2.则其中可推出AB=BA的有()
Ifpollutioncontinuestoincreaseatthepresentrate,formationofaerosols(浮质)intheatmospherewillcausetheonsetofan
最新回复
(
0
)