早教吧 育儿知识 作业答案 考试题库 百科 知识分享
早教吧考试题库频道 --> 计算机类考试 -->软考中级 -->

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

题目

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

A.10

B.11

C.21

D.36

参考答案
正确答案:A
解析:基于关键字的比较操作排序方法,其排序过程均可以利用判定树来描述。判定树上所有叶子结点恰好表示所有排序结果,每个初始序列经过排序达到有序所需要进行的比较次数,正好等于从树根到和该序列相应的叶子结点的路径长度。由于含n个记录的序列可能出现的初始状态有n!个,则描述n个记录排序过程的判定树必须有n!个叶结点。因为,若少一个叶结点,则说明尚有两种状态没有分辨出来。由于若二叉树高度为h,则叶子结点的个数不超过2h-1个;反之,若有u个结点,则二叉树的高度至少为。因此,描述n个记录排序的判定树上必定存在一条长度为的路径。由此可知:任何一个借助比较进行排序的算法,在最坏情况下所需进行比较次数至少为。在本题中,n=6,因此,,因此,正确的答案为10次。
看了任何一个基于“比较”的内部排序...的网友还看了以下: