首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
任何一个基于“比较”的内部排序算法,若对6个元素进行排序,则在最坏情况下所需的比较次数至少为(65)。
任何一个基于“比较”的内部排序算法,若对6个元素进行排序,则在最坏情况下所需的比较次数至少为(65)。
admin
2019-05-23
67
问题
任何一个基于“比较”的内部排序算法,若对6个元素进行排序,则在最坏情况下所需的比较次数至少为(65)。
选项
A、10
B、11
C、21
D、36
答案
A
解析
基于关键字的比较操作排序方法,其排序过程均可以利用判定树来描述。判定树上所有叶子结点恰好表示所有排序结果,每个初始序列经过排序达到有序所需要进行的比较次数,正好等于从树根到和该序列相应的叶子结点的路径长度。由于含n个记录的序列可能出现的初始状态有n!个,则描述n个记录排序过程的判定树必须有n!个叶结点。因为,若少一个叶结点,则说明尚有两种状态没有分辨出来。由于若二叉树高度为h,则叶子结点的个数不超过2
h-1
个;反之,若有u个结点,则二叉树的高度至少为
。因此,描述n个记录排序的判定树上必定存在一条长度为
的路径。由此可知:任何一个借助比较进行排序的算法,在最坏情况下所需进行比较次数至少为
。在本题中,n=6,因此,
,因此,正确的答案为10次。
转载请注明原文地址:https://kaotiyun.com/show/8NTZ777K
本试题收录于:
数据库系统工程师上午基础知识考试题库软考中级分类
0
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
(2007上监理)按照软件配置管理的原始指导思想,受控制的对象应是_____(1)。实施软件配置管理包括4个最基本的活动,其中不包括_____(2)。(2)
(2011下集管)某供电企业在信息化过程中先后构建了多个部门级的信息系统应用。由于历史原因,这些应用大多采用不同的语言开发,并且运行在多种平台之上,现在该企业希望将这些系统集成起来,实现在各个系统之间快速传递可定制格式的数据包。如果有新数据到达,接收系统能
(2009下项管)《信息技术软件产品评价质量特性及其使用指南GB/T16260-1996》中对软件的质量特性做出了描述,以下描述错误的是______。
(2007下项管)在层次化网络设计方案中,通常在______实现网络的访问策略控制。
(2008下项管)在管理信息系统项目的实施过程中,不仅需要管理过程,也需要技术过程、支持过程、过程改进和商务过程等,它们分别来自项目管理知识、项目环境知识、通用的管理知识和技能、软技能或人际关系技能以及______。
(2009下软设)极限编程(XP)由价值观、原则、实践和行为四个部分组成,其中价值观包括沟通、简单性、______。
(2009上项管)关于项目收尾与合同收尾关系的叙述,正确的是______。
(2009下架构)面向对象的设计模型包含以______(1)表示的软件体系结构图,以______(2)表示的用例实现图,完整精确的类图,针对复杂对象的状态图和用以描述流程化处理的活动图等。(1)
(2014下集管)某公司与客户签定了一个系统集成项目合同,对于项目的范围和完成时间做出了明确的规定。在制定进度计划时,项目经理发现按照估算的活动时间和资源编制的进度计划无法满足合同工期,为了达到合同要求,项目经理不宜采用的方法是______。
(2009上网工)两个公司希望通过Internet传输大量敏感数据,从信息源到目的地之间的传输数据以密文形式出现,而且不希望由于在传输结点使用特殊的安全单元而增加开支,最合适的加密方式是______(1),使用会话密钥算法效率最高的是______(2)。
随机试题
良好医患关系的重要性体现在
人生什么事最苦呢?贫吗?不是;失意吗?不是;老吗?死吗?都不是。我说人生最苦的事,莫苦于身上背着一种未来的责任。人若能知足,虽贫不苦;若能安分(不多作分外希望),虽失意不苦;老、病、死,乃人生难免之事,达观的人看得很平常,也不算什么苦。独是凡人生活在世间一
环磷酰胺的不良反应是()。
A、凡例部分B、附录部分C、沿革部分D、正文部分E、索引部分盐酸滴定液配制与标定的方法应收载药典的()
当存在巨额贸易顺差时,紧缩的货币政策能够提高利率,进而使本币升值,导致(),有助于恢复贸易平衡。
施工过程质量控制的内涵包括()。
远期利率合同()。
集成创新的主体是()。
组织
Whatdoesthewomanwantthemantodo?
最新回复
(
0
)