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

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

1、一个无向连通图的生成树是含有该连通图的全部顶点的（ ）。

A、极小连通子图

B、极小子图

C、极大连通子图

D、极大子图

2、设给定权值总数有n个，其哈夫曼树的结点总数为（ ）。

A、不确定

B、2n

C、2n+1

D、2n-1

3、链表不具有的特点是（ ）。

A、可随机访问任一元素

B、插入删除不需要移动元素

C、不必事先估计存储空间

D、所需空间与线性表长度成正比

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

A、按层遍历

B、后序遍历

C、中序遍历

D、先序遍历

5、n个顶点的强连通图至少有（ ）条边。

A、n

B、n+1

C、n-1

D、n(n-1)

1、试题答案：A

试题解析：

一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。故本题选A。

2、试题答案：D

试题解析：

根据树的性质可知，结点个数n=n0+n1+n2（结点数量）=n1+2n2+1（边数量+1）。由于哈夫曼树不存在度为1的结点，因此哈夫曼树的结点总数为2n-1。故本题选D。

3、试题答案：A

试题解析：

链表不具有的特点是可随机访问任一个元素。链表是一种线性结构，元素的访问只能从头结点或尾结点开始，沿着指针一个一个遍历，无法像数组一样通过下标随机访问任意一个元素。故本题选A。

4、试题答案：D

试题解析：

深度优先遍历算法是图的遍历方式之一，其遍历过程类似于二叉树的先序遍历。在深度优先遍历中，我们从某个顶点开始遍历，依次访问该顶点的所有邻接顶点，然后依次对每个邻接顶点进行递归遍历，直到所有能到达的顶点都被访问到。这个过程就类似于二叉树的先序遍历，先访问根节点，再递归遍历左子树和右子树。故本题选D。

5、试题答案：C

试题解析：

一个强连通图表示其中任意两个顶点都有至少一条有向路径相互连通。当一个有向图中存在一个简单环，并且它包含了图中的所有结点，那么这个图就是一个强连通图，并且只有n条边。故本题选C。