数据结构与算法-考研试题(暨南大学 2023年基数排序)

单项选择（2023年暨南大学）

算法的时间复杂度不是O(nlogn)的算法是【】

A、快速排序

B、归并排序

C、堆排序

D、基数排序

答案解析

D

讨论

数据结构与算法

如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是【】

表达式a*(b+c)-d 的后缀表达式是【】

深度优先遍历类似于二叉树的【】

任何一个无向连通图的最小生成树【】

按照二叉树的定义，具有3个结点的二叉树有【】种。

将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为35的结点的左孩子编号为【】。

循环链表的主要优点是【】

若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是【】

对含有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++描述，并注释。

基数排序

用邻接表表示图进行广度优先遍历时，通常采用【】来实现算法。

在一棵二叉树中，中序遍历的第一个结点，是二叉树的最左下结点。

顺序表查找指的是在顺序存储结构上进行查找。

已知一颗二叉树的先序序列和后序序列，一定能构造出该树。

在一棵树中，堂兄弟的双亲是兄弟关系。

不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。

冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。

分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。

一个图按广度优先遍历的结果是唯一的。

由树转化为二叉树，该二叉树的右子树不一定为空。

内部排序

一组记录的排序码为(45，35，71，51，20，26，61，12)，则利用快速排序的方法，以第一个记录为基准得到的第一次划分结果为____________________.

设一组初始记录关键字序列为(41，35，52，17，8，50，22，38)，请分别给出第5趟简单选择排序和第4趟直接插入排序的结果。

试编写一个算法，在链式存储结构上实现直接插入排序算法。

下列排序算法中，哪些时间复杂度不会超过nlogn【】。

若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，应该选【】。

若需在O(log2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是【】。

若待排序记录按关键字基本有序，则宜采用的排序方法是【】。

对于n个元素的关键码序列{k1,k2,…,kn}，当且仅当满足下列关系时称其为堆。或以下关键码序列中，【】不是堆。

若要求对大小为n的数组进行排序的时间复杂度为 O(nlog2n)，且是稳定的(即如果待排序的序列中两个数据元素具有相同的值，在排序前后它们的相对位置不变)，则可选择的排序方法是【】

搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询串的长度不超过255 字节。假设目前有一千万个查询记录(重复度比较高，其实互异的查询串不超过三百万个；显然，一个查询串的重复度越高，说明查询它的用户越多，也就是越热门)。现要统计最热门的 10 个查询串，且要求使用的内存不能超过 1GB。以下各方法中，可行且效率最高的方法是【】。