对于一个长度为n的任意表进行排序，至少需要进行的比较次数是( )。

admin2019-07-18 41

问题对于一个长度为n的任意表进行排序，至少需要进行的比较次数是( )。

选项 A、O(n)
B、O(n²)
C、O(log n)
D、O(nlog n)

答案D

解析在排序过程中，每次比较会有两种情况出现，若整个排序过程中至少需要t次比较，则显然会有2’种情况，由于n个记录总共有n!种不同的排列，因而必须有n!种不同的比较路径，于是有：2^t≥n!，即t≥log₂(n!)。因为log₂(n!)≈nlog₂n，所以t≥nlog₂n。

转载请注明原文地址:https://kaotiyun.com/show/5JCi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

维多利亚时代
周王室的两大官僚系统是()。
第三次科技革命初期，苏联领先于美国的新兴科学技术成就是()。
严复翻译的《天演论》一书的出版时间是()。
第二次工业与第一次工业革命相比较，其新特点是()。①科学和技术真正结合起来②第二次工业革命几乎同时发生在几个先进的资本主义国家③与第一次工业革命交叉进行④使社会第一次分裂为工人阶级和资产阶级
商朝号称青铜时代，下列叙述不符合当时的历史情况的是()
设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离｜w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。
在机器数中，正数的符号位用“1”表示的是()。
快速排序算法中，如何选取一个界值(又称为轴元素)，影响着快速排序的效率，而且界值也并不一定是被排序序列中的一个元素。例如，我们可以用被排序序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速排序方法。
网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。

随机试题

阅读戴望舒《雨巷》中的一节：撑着油纸伞，独自彷徨在悠长，悠长又寂寥的雨巷，我希望逢着一个丁香一样地结着愁怨的姑娘。
Forsometimescientistshavebelievedthatcholesterolplaysamajorroleinheartdiseasebecausepeoplewithfamilialhyperch
帕金森病的发病年龄常在
40岁女性，农民，述乘车时头晕不适、恶心呕吐，反复发作。下车后可迅速恢复。查体：血压120／70mmHg，脉搏80次／分。神经系统检查无阳性体征，脑电图、肌电图、脑部CT无异常。该患者的诊断可能性最大的是()
合同履行的前提和依据是()。
食品添加剂，指为改善食品品质和色、香、味以及为防腐、保鲜和加工工艺的需要而加入食品中的人工合成或者天然物质。下列有关食品添加剂的说法正确的是：
当下，媒介发展一日千里，如何认识媒体、对待媒体，已成为执政者执政素养_______的部分。尤其随着互联网的崛起，跨人社交媒体时代，网络的去中心化、去权威化和参与性、互动性的增强，极大地_______了媒体环境。适应这样一个全新的媒体时代，理应成为必备的执政
下列对应错误的是()。
设有4道作业，它们的提交时间及执行时间如表所示。在单道程序环境下，若采用先来先服务调度算法，其平均周转时间为(15)，平均带权周转时间为(16)。
Ethernet交换机是利用“端口/MAC地址映射表”进行数据交换的。交换机采用()方法动态建立和维护端口/MAC地址映射表。

最新回复(0)

对于一个长度为n的任意表进行排序，至少需要进行的比较次数是( )。

计算机408

学硕统考专业

维多利亚时代

周王室的两大官僚系统是()。

第三次科技革命初期，苏联领先于美国的新兴科学技术成就是()。

严复翻译的《天演论》一书的出版时间是()。

第二次工业与第一次工业革命相比较，其新特点是()。①科学和技术真正结合起来②第二次工业革命几乎同时发生在几个先进的资本主义国家③与第一次工业革命交叉进行④使社会第一次分裂为工人阶级和资产阶级

商朝号称青铜时代，下列叙述不符合当时的历史情况的是()

设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离｜w属于V(G))如果v是有向图G中具有的最小偏心度的顶点，则称顶点v是G的中心点。

在机器数中，正数的符号位用“1”表示的是()。

网络如图所示。链路旁边注明的数字代表链路的长度(假想单位)。试利用Dijk-stra算法求出从结点A到所有其他结点的最短路由。

阅读戴望舒《雨巷》中的一节：撑着油纸伞，独自彷徨在悠长，悠长又寂寥的雨巷，我希望逢着一个丁香一样地结着愁怨的姑娘。

Forsometimescientistshavebelievedthatcholesterolplaysamajorroleinheartdiseasebecausepeoplewithfamilialhyperch

帕金森病的发病年龄常在

40岁女性，农民，述乘车时头晕不适、恶心呕吐，反复发作。下车后可迅速恢复。查体：血压120／70mmHg，脉搏80次／分。神经系统检查无阳性体征，脑电图、肌电图、脑部CT无异常。该患者的诊断可能性最大的是()

合同履行的前提和依据是()。

食品添加剂，指为改善食品品质和色、香、味以及为防腐、保鲜和加工工艺的需要而加入食品中的人工合成或者天然物质。下列有关食品添加剂的说法正确的是：

下列对应错误的是()。

设有4道作业，它们的提交时间及执行时间如表所示。在单道程序环境下，若采用先来先服务调度算法，其平均周转时间为(15)，平均带权周转时间为(16)。

Ethernet交换机是利用“端口/MAC地址映射表”进行数据交换的。交换机采用()方法动态建立和维护端口/MAC地址映射表。