首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
任何一个基于“比较”的内部排序算法,若对6个元素进行排序,则在最坏情况下所需的比较次数至少为(65)。
任何一个基于“比较”的内部排序算法,若对6个元素进行排序,则在最坏情况下所需的比较次数至少为(65)。
admin
2019-05-23
64
问题
任何一个基于“比较”的内部排序算法,若对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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
(2014下项管)软件设计包括软件的结构设计、数据设计、接口设计和过程设计,其中结构设计是指______。
(2013上项管)某公司采用邀请招标的方式选择承建单位,实施过程中发生了如下事件:①该公司向3家单位发出了招标邀请函,其中包括该公司的股东公司;②该公司8月1日发出邀请函,要求对方在8月16日提交投标书;③该公司外聘了1名法律
(2010下项管)在软件开发项目中强调“个体和交互胜过过程和工具,可以工作的软件胜过全面的文档,客户合作胜过合同谈判,响应变化胜过遵循计划”,是______的基本思想。
(2014下项管)在UML图形上,把一个泛化关系画成______。
(2009下系管)______是类元之间的语义关系,其中的一个类元指定了由另一个类元保证执行的契约。
(2011下集管)配置项的版本号规则与配置项的状态相关,以下叙述中正确的是______。
(2010下项管)某开发团队由多个程序员组成,需要整合先前在不同操作系统平台上各自用不同编程语言编写的程序,在Windows操作系统上集成构建一个新的应用系统。该开发团队适合在Windows操作系统上选择______作为开发平台。
(2014上集管)在对一个系统进行需求分析后,通常会建立实体关系模型(E-R)图,在E-R图中,表示实体的图形是______。
常见软件开发生命周期中,瀑布模型、迭代模型和快速原型3种模型各有优缺点,主要表述如下。优点:A.强调开发的阶段;B.强调早期计划及需求调查;C.强调产品测试;D.开发中的经验教训能及时反馈;E.信息反馈及时;P.销售工作有可能提前进行;G.采取早期预防措施
假设一个有3个盘片的硬盘,共有4个记录面,转速为7200r/min,盘面有效记录区域的外直径为30cm,内直径为10cm,记录位密度为250位/mm,磁道密度为8道/mm,每磁道分16个扇区,每扇区512字节,则该硬盘的非格式化容量和格式化容量约为(50)
随机试题
患者,女,68岁。有健忘病史多年,如今计算力、定向力明显减退,神情呆钝,词不达意,头晕耳鸣,腰酸骨软,舌瘦色淡,苔薄白,脉沉细弱。治疗应选用的方剂是()
某一小组由15名刚进入大学校门,但却表现出对大学生活明显适应不良的学生组成,社会工作者将通过向他们传授相应的应对方法,以协助组员尽快适应并融入大学校园生活。该小组为()。
下列关于社会团体法人的表述,正确的是()。
金属材料的物理性能包括________、导热性和磁性等。
证券投资
下列选项中,不是太阳蓄水证临床表现的是
下列关于建设项目环境影响评价分类管理的说法,正确的有()。
中国节日受到冷落,西方节日受到热捧,你怎么看?
材料1谈到人的价值,有一点许多人会困惑:万物都以其本身的品质来衡量,惟独人是例外。一匹马,我们赞扬的是它的矫健灵活,而不是它的鞍鞯;一条猎狗,我们赞扬的是它的速度,而不是它的项圈;一只鸟儿,我们赞扬的是它的翅膀,而不是它的牵绳或者脚铃。对于一个人
A、Heagreeswithit.B、Hedisagreeswithit.C、Hedoesn’tcareaboutit.D、Hewillthinkofitcarefully.B对话中,女士说她想请假,男士反问女士怎么能
最新回复
(
0
)