首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
任何一个基于“比较”的内部排序算法,若对6个元素进行排序,则在最坏情况下所需的比较次数至少为(65)。
任何一个基于“比较”的内部排序算法,若对6个元素进行排序,则在最坏情况下所需的比较次数至少为(65)。
admin
2019-05-23
31
问题
任何一个基于“比较”的内部排序算法,若对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://jikaoti.com/ti/AEx7FFFM
本试题收录于:
数据库系统工程师上午基础知识考试题库软考中级分类
0
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
(2012下项管)在设计和实现软件系统的功能模块时,______最不利于软件维护。
(2011上监理)以下关于数据存储的理解中,说法正确的是______。
(2011上集管)在项目整体管理过程中监督和控制项目是一个关键环节,下列不属于监督和控制过程组的是______。
(2014上项管)某ERP项目的生产管理子系统进行安装调试时,项目经理发现车间操作员的实际操作方式与最初客户确定的操作方式有较大不同。为了解决这个问题,首先应______。
(2008下项管)某公司欲开发一个在线交易系统。为了能够精确表达用户与系统的复杂交互过程,应该采用UML的______进行交互过程建模。
(2013上项管)一个项目经理被分配到一个高优先度的新项目,只有5个可用的资源,因为其他资源已经被承诺给别的项目,完成项目的资源可用时间不足所需时间的一半,并且这个项目经理不能说服管理层改变项目的结束日期,此时,项目经理应______。
(2007下项管)组织是由人和其他各种用以实现一系列目标的资源组成的正式集合。所有的组织都包含有一系列的增值过程,如内部后勤、仓库和存储、生产、市场、销售、客户服务等等,这些是______(1)的组成部分,信息系统在增值过程中,______(2)。组织适应
十六进制本质上是(1),它是把每(1)个二进位划分成小段,以便于阅读。
如果“2X”的补码是“90H”,那么X的真值是_____。
假设一个有3个盘片的硬盘,共有4个记录面,转速为7200r/min,盘面有效记录区域的外直径为30cm,内直径为10cm,记录位密度为250位/mm,磁道密度为8道/mm,每磁道分16个扇区,每扇区512字节,则该硬盘的非格式化容量和格式化容量约为(50)
随机试题
A.一倍以上三倍以下的罚款B.一倍以上五倍以下的罚款C.二倍以上三倍以下的罚款D.二倍以上五倍以下的罚款E.三倍以上五倍以下的罚款生产、销售劣药的,没收违法生产、销售的药品和违法所得,并处违法生产、销售药品货值金额
狂犬病毒经过系列传代适应特定宿主后可称之为
下列属于胶片感光特性的参数是
枳壳中主含挥发油,其挥发油中主要含有的成分是()。
甲的妻子遭遇车祸,造成严重脑震荡,甲为筹集巨额治疗费用,不得不将自己的一块名表出售于乙。乙见甲处境困顿,明知该表价值10万元,却提出以1万元购买。甲讨价还价再,乙始终不让步,甲无奈于2006年2月1日将该表以1万元的价格出售于乙。半年后,甲妻病故。甲于20
在渐开线齿廓上,()圆上的压力角为零,()圆上的压力角最大。
企业销售商品时代垫的运杂费应记入()科目。
下列对销项税额的处理,错误的是()。
3
Readthefollowingtextanddecidewhichanswerbestfitseachspace.Forquestions26-45,markoneletterA,B,CorDony
最新回复
(
0
)