早教吧考试题库频道 --> 计算机类考试 -->软考中级 -->
任何一个基于“比较”的内部排序算法,若对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次。
解析:基于关键字的比较操作排序方法,其排序过程均可以利用判定树来描述。判定树上所有叶子结点恰好表示所有排序结果,每个初始序列经过排序达到有序所需要进行的比较次数,正好等于从树根到和该序列相应的叶子结点的路径长度。由于含n个记录的序列可能出现的初始状态有n!个,则描述n个记录排序过程的判定树必须有n!个叶结点。因为,若少一个叶结点,则说明尚有两种状态没有分辨出来。由于若二叉树高度为h,则叶子结点的个数不超过2h-1个;反之,若有u个结点,则二叉树的高度至少为。因此,描述n个记录排序的判定树上必定存在一条长度为的路径。由此可知:任何一个借助比较进行排序的算法,在最坏情况下所需进行比较次数至少为。在本题中,n=6,因此,,因此,正确的答案为10次。
看了任何一个基于“比较”的内部排序...的网友还看了以下:
● WLAN采用扩频技术传输数据,下面哪一项不是扩频技术的优点? (65(65)A. 对无线噪声不敏 计算机类考试 2020-05-25 …
●电子商务系统的总体规划无需考虑(65) 。(65)A.对相关信息技术的预测 B.系统的总目标和发展 计算机类考试 2020-05-26 …
设集合M满足条件,若对任意实数a属于M,则f(a)=a/(2a+1)属于M,且f(f(a))属于M 数学 2020-06-03 …
一批货物,每次运95箱,则4次运不完,5次又不够运,每次运75箱,则6次运不完7次又不够运,如果每 数学 2020-06-24 …
五个同学平均每分钟跳65下,其中3个同学每分钟跳绳一共是185下,剩下的2个同学每分钟跳的同样多. 数学 2020-07-18 …
请问下对于氯离子含量2100的地下水怎么处理成净水温度是65度处理成自来水就行了 化学 2020-11-21 …
65.下列属于投标人之间串通投标的行为是()65.下列属于投标人之间串通投标的行为是()A.招标人在 其他 2020-11-27 …
对下列各分数进行分类;3分之21,14分之1,7分之9,100分之99,17分之68,8分之8,13 数学 2020-12-17 …
若a大于b,则根号下a大于根号下b正确不?原因说清楚下列命题中,正确的一个是()A,若a大于b,则根 数学 2020-12-24 …
最近,你班就“学校是否应该对老师进行民主测评”召开了一次主题班会。讨论情况如下:赞成:65%反对:3 英语 2021-01-12 …