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

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

admin2019-05-23  68
问题 任何一个基于“比较”的内部排序算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为(65)。
选项 A、10
B、11
C、21
D、36
答案A
解析 基于关键字的比较操作排序方法，其排序过程均可以利用判定树来描述。判定树上所有叶子结点恰好表示所有排序结果，每个初始序列经过排序达到有序所需要进行的比较次数，正好等于从树根到和该序列相应的叶子结点的路径长度。由于含n个记录的序列可能出现的初始状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶结点。因为，若少一个叶结点，则说明尚有两种状态没有分辨出来。由于若二叉树高度为h，则叶子结点的个数不超过2h-1个；反之，若有u个结点，则二叉树的高度至少为。因此，描述n个记录排序的判定树上必定存在一条长度为的路径。由此可知：任何一个借助比较进行排序的算法，在最坏情况下所需进行比较次数至少为。在本题中，n=6，因此，，因此，正确的答案为10次。
转载请注明原文地址:https://www.kaotiyun.com/show/8NTZ777K
本试题收录于： 数据库系统工程师上午基础知识考试题库软考中级分类
0

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

软考中级

相关试题推荐
随机试题
最新回复(0)