单项选择(2023年计算机统考

使用快速排序算法对数据进行升序排序, 若经过一次划分后得到的数据序列是 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。正确。

讨论

下列排序算法中,不稳定的是【 】。Ⅰ. 希尔排序Ⅱ. 归并排序Ⅲ. 快速排序Ⅳ. 堆排序Ⅴ. 基数排序

现有长度为 5,初始为空的散列表HT,散列函数H(k)=(k+4) mod 5, 用线性探查再散列法解决冲突。若将关键字序列 2022, 12, 25 依次插入HT中,然后删除关键字 25 ,则HT中查找失败的平均查找长度为【 】。

对含有 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 中包含非零元素的列数.

现有非空双向链表 L,其结点结构为:prer|data|next。prer 是指向前直接前驱结点的指针,next 是指向直接后继结点的指针。若要在 L 中指针 p 所指向的结点( 非尾结点) 之后插入指针 s 指向的新结点, 则在执行了语句序列: “s->next=p->next;p->next=s”后,还要执行【 】

下列对顺序存储的有序表 (长度为 n)实现给定操作的算法中平均时间复杂度为 O(1)的是【 】

回答问题并写出推导过程:对50个整数进行快速排序需进行关键字间比较次数可能达到的最大值和最小值各为多少?

在起泡(冒泡)排序过程中,有的关键字在某趟排序中可能朝着与最终排序相反的方向移动,请举例说明之。快速排序过程中有没有这种现象?

快速排序的最大递归深度是__________,最小递归深度是__________。

快速排序的速度在所有排序方法中为最快,而且所需附加的空间也最少。

如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序序列,用【 】方法最快

根据枢轴元素(或基准元素)划分序列而进行排序的是【 】。

对含有n (n>0)个记录的文件进行外部排序,采用置换-选择排序生成初始归并段时需要使用一个工作,工作区中能保存m个记录,请回答下列问题。(1) 如果文件中有19条记录,其关键字分别为:51,94,37,92,14,63,15,99,48,56,23,60,31,17,43,8,90,166,100,当m=4时,可生成几个初试归并段,各是什么?(2)对任意m (n≫m>0),生成的第一个初试归并段长度最大值和最小值分别多少?

已知有向图G采用邻接矩阵存储,其定义如下:typedef struct{//图的定义 int numberVertices,numEgges;//图中实际的顶点数和边数 char verticesList[maxV];//顶点表 int edge[maxV][maxV];//邻接矩阵}MGraph;将图中出度大于入度的顶点称为K顶点,如图,a和b都是K顶点,设计算法 int printVertices(MGraph G)对给定任意非空有向图G,输出G中所有K顶点,并返回K顶点的个数。(1)给出算法的设计思想。(2)根据算法思想,写出C/C++描述,并注释。

使用快速排序算法对数据进行升序排序, 若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88,则该次划分的轴枢【】。

使用快速排序算法对数据进行升序排序, 若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88,则该次划分的轴枢【】。