任何一个基于“比较”的内部排序算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为(65)。

admin2019-05-23 48

问题任何一个基于“比较”的内部排序算法，若对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)

任何一个基于“比较”的内部排序算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为(65)。

数据库系统工程师上午基础知识考试

软考中级

(2013下项管)表示需求和别的系统元素之间的联系链的最普通的方式是使用需求跟踪能力矩阵。如果软件开发人员发现，有一个孤立的设计元素在需求跟踪能力矩阵中不能回溯到需求，但其表明一个正当的功能，则说明______。

(2007上监理)按照软件配置管理的原始指导思想，受控制的对象应是_(1)。实施软件配置管理包括4个最基本的活动，其中不包括_(2)。(1)

(2010上监理)某磁盘阵列共有14块硬盘，采用RAID5技术时的磁盘利用率是______。

(2012下项管)依照招标投标法，项目公开招标的资格预审阶段，在《资格预审须知》文件中可以______。

(2007上系分)UML提供了5种对系统动态方面建模的图，其中(1)对系统行为组织和建模；(2)对系统功能建模，它强调对象之间的控制流；__(3)之间是同构的。(3)

(2010下网规)为防止服务器遭攻击，通常设置一个DMZ。外网、DMZ、内网三者之间的关系，应满足(1)。如果在DMZ中没有(2)，则访问规则可更简单。(2)

(2014下集管)目前，在电子商务交易过程中支付方式很多。按照支付的流程不同，主要存在四种电子商务支付模式：支付网关模式、网上银行模式、第三方支付模式和手机支付模式。______不属于第三方支付模式。

(2009上集管)目前企业信息化系统所使用的数据库管理系统的结构，大多数为______。

(2010下网工)通过ADSL访问Internet，在用户端通过(1)和ADSLModem连接PC机，在ISP端通过(2)设备连接因特网。(1)

为了解决进程间的同步和互斥问题，通常采用一种称为(24)机制的方法。若系统中有5个进程共享若干个资源R，每个进程都需要4个资源R，那么使系统不发生死锁的资源R的最少数目是(25)。

风湿病

患儿出麻疹2天，皮疹密集成片，遍及全身，色紫红，壮热不退，烦躁不安，神昏谵语，抽搐。治疗应首选（　　）。

(2005)对选址范围内古树名木的理解和处理方式，下列叙述中哪项是不正确的?

在所有的工程中必须配置的工人有()。

完成一些日常事务性的工作，如手续的办理、政策的解答和申诉的接受等，这属于人力资源部门的()。

2001年我国颁布的《基础教育课程改革纲要(试行)》明确规定，我国基础教育课程实行()。

“临时之政府，革命时代之政府也。”这是在南京临时政府发表的()中庄严提出的。

Howmanycompanycataloguesareleft?

Haveyouanyotherreasons______theonesyoujustmentionedabove?

WhatarethechallengesfacingmultinationalsthatwanttobuildtheirbrandsinChina?—Ithinkthefirstthingisignorance.T

任何一个基于“比较”的内部排序算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为(65)。

数据库系统工程师上午基础知识考试

软考中级

(2013下项管)表示需求和别的系统元素之间的联系链的最普通的方式是使用需求跟踪能力矩阵。如果软件开发人员发现，有一个孤立的设计元素在需求跟踪能力矩阵中不能回溯到需求，但其表明一个正当的功能，则说明______。

(2007上监理)按照软件配置管理的原始指导思想，受控制的对象应是_____(1)。实施软件配置管理包括4个最基本的活动，其中不包括_____(2)。(1)

(2010上监理)某磁盘阵列共有14块硬盘，采用RAID5技术时的磁盘利用率是______。

(2012下项管)依照招标投标法，项目公开招标的资格预审阶段，在《资格预审须知》文件中可以______。

(2007上系分)UML提供了5种对系统动态方面建模的图，其中______(1)对系统行为组织和建模；______(2)对系统功能建模，它强调对象之间的控制流；______(3)之间是同构的。(3)

(2010下网规)为防止服务器遭攻击，通常设置一个DMZ。外网、DMZ、内网三者之间的关系，应满足______(1)。如果在DMZ中没有______(2)，则访问规则可更简单。(2)

(2014下集管)目前，在电子商务交易过程中支付方式很多。按照支付的流程不同，主要存在四种电子商务支付模式：支付网关模式、网上银行模式、第三方支付模式和手机支付模式。______不属于第三方支付模式。

(2009上集管)目前企业信息化系统所使用的数据库管理系统的结构，大多数为______。

(2010下网工)通过ADSL访问Internet，在用户端通过______(1)和ADSLModem连接PC机，在ISP端通过______(2)设备连接因特网。(1)

为了解决进程间的同步和互斥问题，通常采用一种称为(24)机制的方法。若系统中有5个进程共享若干个资源R，每个进程都需要4个资源R，那么使系统不发生死锁的资源R的最少数目是(25)。

风湿病

患儿出麻疹2天，皮疹密集成片，遍及全身，色紫红，壮热不退，烦躁不安，神昏谵语，抽搐。治疗应首选（ ）。

(2005)对选址范围内古树名木的理解和处理方式，下列叙述中哪项是不正确的?

在所有的工程中必须配置的工人有()。

完成一些日常事务性的工作，如手续的办理、政策的解答和申诉的接受等，这属于人力资源部门的()。

2001年我国颁布的《基础教育课程改革纲要(试行)》明确规定，我国基础教育课程实行()。

“临时之政府，革命时代之政府也。”这是在南京临时政府发表的()中庄严提出的。

Howmanycompanycataloguesareleft?

Haveyouanyotherreasons______theonesyoujustmentionedabove?

WhatarethechallengesfacingmultinationalsthatwanttobuildtheirbrandsinChina?—Ithinkthefirstthingisignorance.T

(2007上监理)按照软件配置管理的原始指导思想，受控制的对象应是_(1)。实施软件配置管理包括4个最基本的活动，其中不包括_(2)。(1)

(2007上系分)UML提供了5种对系统动态方面建模的图，其中(1)对系统行为组织和建模；(2)对系统功能建模，它强调对象之间的控制流；__(3)之间是同构的。(3)

(2010下网规)为防止服务器遭攻击，通常设置一个DMZ。外网、DMZ、内网三者之间的关系，应满足(1)。如果在DMZ中没有(2)，则访问规则可更简单。(2)

(2010下网工)通过ADSL访问Internet，在用户端通过(1)和ADSLModem连接PC机，在ISP端通过(2)设备连接因特网。(1)

患儿出麻疹2天，皮疹密集成片，遍及全身，色紫红，壮热不退，烦躁不安，神昏谵语，抽搐。治疗应首选（　　）。