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

admin2019-05-23 31

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

选项 A、10
B、11
C、21
D、36

答案A

解析基于关键字的比较操作排序方法，其排序过程均可以利用判定树来描述。判定树上所有叶子结点恰好表示所有排序结果，每个初始序列经过排序达到有序所需要进行的比较次数，正好等于从树根到和该序列相应的叶子结点的路径长度。由于含n个记录的序列可能出现的初始状态有n!个，则描述n个记录排序过程的判定树必须有n!个叶结点。因为，若少一个叶结点，则说明尚有两种状态没有分辨出来。由于若二叉树高度为h，则叶子结点的个数不超过2^h-1个；反之，若有u个结点，则二叉树的高度至少为