数据结构与算法-考研试题(暨南大学 2023年图的遍历)

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

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

A、G肯定不是完全图

B、G中一定有回路

C、G一定不是连通图

D、G有2个连通分量

答案解析

B

讨论

数据结构与算法

表达式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++描述，并注释。

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

图的遍历

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

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

图的遍历方式有__________和__________两种。

对于一个有向图，不用拓扑排序，如何判断图中是否存在环？

对于下图，从顶点1进行深度优先遍历时，不可能得到的遍历序列是【】

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

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

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

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

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

图

无向图的邻接矩阵是对称的，因此可只存储矩阵的下三角阵。

设计一数据结构，用来表示图的邻接矩阵存储结构(包括弧的结构和图的结构)。

对于给定的n个元素，可以构造的逻辑结构有__________、__________、__________和__________4种。

G是一个非连通无向图，共有28条边，则该图至少有【】个顶点。

在n个结点的无向图中，若边数>n-1，则该图必是连通图。

用DFS遍历一个无环有向图，并DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是【】。

有 n 个顶点的有向强连通图最多有多少条边？最少有多少条边？

若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。

试列中下列图中全部可能的拓扑排序序列。

Kruskal算法的时间复杂度为__________，它对__________图比较合适。