● 以下关于快速排序算法的描述中,错误的是 (64) 。在快速排序过程中,需要设立基准元素并划分序列
● 以下关于快速排序算法的描述中,错误的是 (64) 。在快速排序过程中,需要设立基准元素并划分序列来进行排序。若序列由元素{12,25,30,45,52,67,85}构成,则初始排列为 (65) 时,排序效率最高(令序列的第一个元素为基准元素)。
(64)A. 快速排序算法是不稳定的排序算法
B. 快速排序算法在最坏情况下的时间复杂度为O(n1gn)
C. 快速排序算法是一种分治算法
D. 当输入数据基本有序时,快速排序算法具有最坏情况下的时间复杂度
(65)A. 45,12,30,25,67,52,85
B. 85,67,52,45,30,25,12
C. 12,25,30,45,52,67,85
D. 45,12,25,30,85,67,52
试题(64)、(65)分析
本题考查快速排序算法。
快速排序算法是一种经典的排序算法,其基本思想是选择一个基准元素(通常选择第一个元素或者最后一个元素),通过一趟排序将待排序序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置;然后再递归地排序划分的两部分,因此本质上快速排序是一种分治算法。由于在排序的过程中,各元素与基准元素比较大小,若小于基准元素则与基准元素交换位置,因此该算法是不稳定的排序算法。当每一趟排序进行后,选择的基准元素恰好最大或者最小时,就把序列分成极端不均衡的两部分,即一部分为空,另一部分为待排序序列的元素个数减1,此时算法处于最坏情况,其时间复杂度为O(n2)。当输入数据基本有序或者所有元素值相等时,不论选择第一个元素还是最后一个元素作为基准元素,都恰好把序列分成极端不均衡的两部分,快速排序算法具有最坏情况下的时间复杂度。
对于选项A,以45作为基准元素进行第一趟划分,先从后向前找出比45小的元素,67、52、85这三个元素保持不动,找到25,将其与45交换后,第一趟划分完成,序列为25,12,30,45,67,52,85。第二趟先对子序列25,12,30进行划分,使得25与12对调,形成子序列12,25,30;然后对67,52,85进行划分,使得67与52交换,形成子序列52,67,85。至此,整个排序过程完成。期间,第一趟划分中元素的比较次数为6次、交换1次,第二趟划分中元素的比较次数共4次、交换次数为2次,因此,排序过程中比较次数共10次,交换次数为3次。
对于选项B,以85作为基准元素,因12比它小,所以将85与12交换,由于剩下的元素都比85小,因此保持不动,第一趟划分之后的元素序列为12,67,52,45,30,25,85,期间元素比较次数为6次、交换1次,第二趟对85之前的6个元素进行划分,由于67、52、45、30、25都比基准元素12大,因此它们保持不动,完成第二趟划分,形成的子序列为12,67,52,45,30,25,期间比较次数为5、交换次数为0。接下来第三趟对子序列67,52,45,30,25进行划分,以67为基准元素,情况与第一趟相同,进行4次比较、l次交换后,形成子序列25,52,45,30,67。第四趟对子序列25,52,45,30进行划分,情况与第二趟相同。依此类推,完成排序时比较次数为21次(6+5+4+3+2+1)。
对于选项C,以12作为基准元素,因为后面的所有元素都比它大,所以所有元素是持不动,第一趟划分之后的元素序列为12,25,30,45,52,67,85,期间元素比较次数为6次、交换0次。第二趟对子序列25,30,45,52,67,85进行划分,以25作为基准元素,因为后面的所有元素都比它大,所以所有元素保持不动,第一趟划分之后的元素序列为25,30,45,52,67,85,期间元素比较次数为5次、交换0次。接下来对子序列30,45,52,67,85进行划分,同理,元素保持不动,期间元素比较次数为4次、交换0次。依此类推,完成整个排序比较次数为21次、交换0次。
对于选项D,以45作为基准元素进行第一趟划分,先从后向前找出比45小的元素,85、67、52这三个元素保持不动,找到30,将其与45交换后,第一趟划分完成,序列30,12,25,45,85,67,52,期间元素比较次数为6次、交换1次。第二趟先对子序列30,12,25进行划分,以30为基准元素,30与25交换,经过2次比较、1次交换后子序列为25,12,30,需要再次对子序列25,12进行划分;同理,对子序列85,67,52进行划分后,结果为51,67,87,还需对子序列51,67进行划分。排序过程中比较次数共12次。
参考答案
(64)B(65)A
一部书,有上中下三册,上册比中册贵两元中册比下册贵了共售价64元上中下册各多少元? 数学 2020-04-26 …
34)有以下程序,程序中库函数islower(ch)用以判断ch中的字母是否为小写字母#inclu 其他 2020-05-16 …
34)有以下程序,程序中库函数islower(ch)用以判断ch中的字母是否为小写字母#inclu 其他 2020-05-16 …
下列花序中,花的开放次序由上向下的是()。A.轮伞花序B.蝎尾状花序C.穗状花序D.伞房花序E.A和 学历类考试 2020-05-25 …
棵二叉树的先序、中序和后序序列分别如下,其中有一部分未显示出来,试指出下面(19)图才是该二叉树。 计算机类考试 2020-05-26 …
二叉树顺序遍历问题!找出所有二叉树,其节点在下列两种次序下恰好都以同样的次序出现.①先序和中序,② 其他 2020-06-15 …
以下生物题求详解!1茎表皮细胞的外壁常具有(C)A木质华B具凯氏点C具通道细胞D维管束排成不连续的 语文 2020-06-19 …
O(n1.5)与O(nlog2n)中的O是什么意思?希尔排序中提到:如果选取增量序列,则在最坏的情 数学 2020-07-23 …
下面的程序是求如下表达式的值。S=sqrt(ln(1)+ln(2)+ln(3)+......+ln 其他 2020-07-23 …
下列中国教育发展历程中的几件大事,按时间先后顺序排序正确的是()①创办京师下列中国教育发展历程中的几 历史 2020-11-04 …