考研数据结构A在线题库每日一练（六十七）

本文提供考研数据结构A在线题库每日一练，以下为具体内容

1、G是一个连通图，共有28条边，则该图至少有（ ）个顶点。

A、6

B、7

C、8

D、9

2、一棵含有18个结点的二叉树的高度至少为（ ）。

A、3

B、4

C、5

D、6

3、已知一个图如下所示，从顶点a出发进行深度优先遍历可能得到的序列为（ ）。

A、acefbd

B、acbdfe

C、acbdef

D、acdbfe

4、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ ）。

A、按层遍历

B、先序遍历

C、中序遍历

D、后序遍历

5、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，该树共有（ ）个结点。

A、

B、

C、

D、

1、试题答案：A

试题解析：

当该图为有向的完全连通图时，图的顶点数最少，此时图的顶点和边数满足n*（n-1）=e，带入边数=28，n*（n-1）≥28，解得n为6，则故本题选A。

2、试题答案：C

试题解析：

当这棵二叉树为完全二叉树时，二叉树的高度最小。根据完全二叉树的性质可知，具有n个结点的完全二叉树的深度为⎿log₂n⏌+1，将n=18代入，解得树的高度至少是5，故本题选C。

3、试题答案：A

试题解析：

图的深度优先遍历的方法为：从图中某顶点v出发，访问顶点v，依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问。若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。根据该思想，选项B和C在遍历b之后应当遍历e或f，选项D在遍历d之后遍历e或f，故本题选A。

4、试题答案：A

试题解析：

广度优先遍历算法是一种遍历图的算法，用于按照广度优先的顺序遍历图中所有顶点。该算法通过邻接表存储的图，从指定的起始顶点开始，首先访问与其相邻的所有顶点，然后按照它们的访问顺序依次访问它们的相邻顶点，直到遍历完整个图。类比于二叉树，广度优先遍历算法类似于按层遍历。在按层遍历二叉树时，也是从根节点开始，依次访问每一层的节点，直到遍历完整个树。故本题选A。

5、试题答案：A

试题解析：