使用快速排序算法对数据进行升序排序, 若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88,则该次划分的轴枢【】。
A、11
B、70
C、80
D、81
使用快速排序算法对数据进行升序排序, 若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88,则该次划分的轴枢【】。
A、11
B、70
C、80
D、81
D
【解析】
快速排序算法通过多次比较和交换来实现,其排序流程如下:
(1)首先设定一个分界值,通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右边部分中各元素都大于或等于分界值。
(3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。
A选项,枢轴为11 ,左边 68 > 11 。错误。
B选项,枢轴为70 ,右边 23 < 70 。错误。
C选项,枢轴为80,右边 48 < 80 。错误。
D选项,枢轴为81。正确。
下列排序算法中,不稳定的是【 】。Ⅰ. 希尔排序Ⅱ. 归并排序Ⅲ. 快速排序Ⅳ. 堆排序Ⅴ. 基数排序
对含有 600 个元素的有序顺序表进行折半查找,关键字之间的比较次数最多是【 】
下列关于非空 B 树的叙述中,正确的是【 】Ⅰ. 插入操作可能增加树的高度Ⅱ. 删除操作一定会导致叶结点的变化Ⅲ. 查找某关键字一定是要查找到叶结点Ⅳ. 插入的新关键字最终位于叶结点中
已知无向连通图 G 中各边的权值均为 1,下列算法中一定能够求出图 G 中从某顶点到其余各个顶点最短路径的是【 】Ⅰ.普利姆算法;Ⅱ.克鲁斯卡尔算法;Ⅲ.图的广度优先搜索
已知一棵二叉树的树形如图,若其后序遍历为 f、d、b、e、c、a,则其先序列为【 】
在有 6 个字符组成的字符集 S 中,各个字符出现的频次分别为 3、4、5、6、8、10,为 S 构造的哈夫曼树的加权平均长度为【 】
若采用三元组表存储结构存储系数矩阵 M.则除三元组外,下列数据中还需要保存的是【 】Ⅰ. M 的行数;Ⅱ. M 中包含非零元素的行数;Ⅲ. M 的列数;Ⅳ. M 中包含非零元素的列数.
回答问题并写出推导过程:对50个整数进行快速排序需进行关键字间比较次数可能达到的最大值和最小值各为多少?
在起泡(冒泡)排序过程中,有的关键字在某趟排序中可能朝着与最终排序相反的方向移动,请举例说明之。快速排序过程中有没有这种现象?
快速排序的最大递归深度是__________,最小递归深度是__________。
快速排序的速度在所有排序方法中为最快,而且所需附加的空间也最少。
如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序序列,用【 】方法最快
使用快速排序算法对数据进行升序排序, 若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88,则该次划分的轴枢【】。
使用快速排序算法对数据进行升序排序, 若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88,则该次划分的轴枢【】。
对长度为10的线性表进行冒泡排序,最坏情况下需要比较的次数为__________。
初始序列为1 8 6 2 5 4 7 3一组数采用堆排序,当建堆(小根堆)完毕时,堆所对应的二叉树中序遍历序列为【 】。
若需在O(log2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是【 】。
在文件“局部有序”或文件长度较小的情况下,最佳内部排序的方法是【 】。
下述排序算法中,所需辅助存储量最多的是__________,所需辅助存储量最少的是__________,平均速度最快的是__________。A. 快速排序 B. 归并排序 C. 堆排序
若有n个元素已构成一个小根堆,那么如果增加一个元素Kn+1,请用文字简要说明如何在log2n的时间内将其重新调整为一个堆。
如果待排序序列中两个数据元素具有相同的值,在排序前后它们的位置发生颠倒,则称该排序算法是不稳定的,【 】就是不稳定的排序算法。