中级数据库系统工程师
单选题任何一个基于"比较"的内部排序的算法中，若对6个元素进行排序，在最坏情况下所需的比较次数至少为（）A 10B 11C 21D 36
题目
10
11
21
36
相似问题和答案
第1题：
以下关于快速排序算法的描述中，错误的是( )。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素{12，25，30，45，52，67，85}构成，则初始排列为( )时，排序效率最高(令序列的第一个元素为基准元素)。
A．快速排序算法是不稳定的排序算法
B．快速排序算法在最坏情况下的时间复杂度为0(nlgn)
C．快速排序算法是一种分治算法
D．当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度
解析：最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：cmax=n(n-1)／2=O(2)在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlgn)
第2题：
对n个不同的排序码的元素进行冒泡排序，在(45)情况下比较的次数最少，其比较次数为(46)。在(47)情况下比较次数最多，其比较次数为(48)。
A．从大到小排列好的
B．从小到大排列好的
C．元素无序
D．元素基本有序
第3题：
A.10
B.11
C.21
D.36
第4题：
任何一个基于“比较”的内部排序的算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为(56)。
A．10
B．11
C．21
D．36
解析：对6个元素进行排序所需的比较次数至少为10次。
第5题：
以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下面的排序算法中，最坏情况下计算时间可以达到O(nlogn)的是(59)；该算法采用的设计方法是(60)。
A．归并排序
B．插入排序
C．选择排序
D．冒泡排序
解析：直接插入排序、简单选择排序和冒泡排序最坏情况下计算时间可以达到O(n2)，而归并排序的时间最坏情况下可以达到O(nlogn)。而归并排序也是分治策略的一个典型应用。
第6题：
度为10的线性表进行冒泡排序，在最坏情况下需要比较的次数为______。
45 解析：对于长度为n的线性表，在最坏情况下(即线性表中元素现在的顺序与目标顺序正好相反)，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。
第7题：
对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)／2的排序方法是（ ）。
A.快速排序
B.冒泡排序
C.直接插入排序
D.堆排序
D。【解析】首先知道有哪些排序的方法及各种排序方法在最坏情况下需要比较的次数，冒泡排序n(n-1)／2、希尔排序0(n1．5)、简单选择排序n(n-1)／2、堆排序O(nl0g2n)。
第8题：
在最坏情况下，堆排序需要比较的次数为 【2】 。
正确答案: 1.(O(nlog2n))
第9题：
任何一个基于比较的内部排序算法，若对 6个元素进行排序，最坏情况下所需要的比较
次数是几次。
第10题：
以关键字比较为基础的排序算法在最坏情况下的计算时间下界为
O(nlogn)。下面的排序算法中，在最坏情况下计算时间可以达到
O(nlogn)的是( 58 )；
A.归并排序
B.插入排序
C.选择排序
D.冒泡排序
记忆几类常见的排序算法的时间复杂度即可。