《数据结构》习题及答案 袁凌 - 第6--9章.docx

第六章

一、选择题

1．设无向图G的顶点数为n（n≥2），边数为e（e≥1），下列关于该无向图的叙述中正确的是D 。

A．至少有一个顶点的度为奇数 B．当e≥n-1时，无向图G是连通图

C．至少有一个顶点的度为偶数 D．所有顶点的度之和为偶数

2．设有5个结点的无向图，该图至少应有 C 条边才能确保是一个连通图。

A．5 B．6 C．7 D．8

3．用有向无环图描述表达式(a+b)*c+(a+b+c)*d，至少需要 B个顶点。

A．8 B．9 C．10 D．11

4．已知某无向图有20条边，其中度为4的顶点个数为2、度为3的顶点个数为6、度为2的顶点个数为4、其他顶点的度均不超过1，则该图所含的顶点个数至少是B 。

A．17 B．18 C．19 D．20

5．若将n个顶点e条弧的有向图采用邻接矩阵存储，则拓扑排序算法的时间复杂度是D 。

A．O(nloge) B．O(n?e) C．O(n+e) D．O(n2)

6．若用邻接矩阵存储有向图，邻接矩阵为上三角矩阵（或下三角矩阵），则关于该图的结论是D 。

A．该图可能有回路 B．该图一定没有回路，有唯一的拓扑排序

C．该图不存在拓扑排序 D．该图一定没有回路，拓扑排序不一定唯一

7．图6.29所示为AOE网，下列不是其拓扑排序的选项是C 。

A．1,2,3,4,5,6 B．1,3,2,5,4,6 C．1,4,3,2,5,6 D．1,3,2,4,5,6

8．图6.29中有9个活动的AOE网，活动a5的最早开始和最迟开始时间分别是B 。

A．6、6 B．6、8 C．7、13 D．13、15

9．使用迪杰斯特拉（Dijkstra）算法求图6.30中从顶点1到其他各顶点的最短路径，依次得到各最短路径的目标顶点是 C。

A．1,2,3,4,5,6 B．1,3,5,6,4,2 C．1,4,2,6,5,3 D．1,3,2,4,5,6

10．从图6.30所示顶点1出发进行深度优先遍历，不能得到的顶点序列是A 。

A．1,2,3,4,5,6 B．1,3,4,2,6,5 C．1,4,2,6,5,3 D．1,3,5,4,2,6

11．可借助A 算法判断有向图中是否存在回路。

A．拓扑排序 B．迪杰斯特拉 C．Floyd D．Prim

12．对图6.31所示的无向连通网，使用Prim算法求从顶点A出发，得到的最小生成树是 C。

二、填空题

有n个顶点的强连通图至少有n条弧。

有n个顶点的无向图最多n(n-1)/2条边。

在有向图的邻接矩阵中，每一行包含的“1”的个数为对应顶点的__出度_____。

n个顶点e条边的有向图采用邻接表存储，求某结点度的算法时间复杂度为O(n)。

设有一个稀疏图，则采用邻接表存储比较节省存储空间。

十字链表适用于有向图（网），邻接多重表适用于无向图（网）。

对n个顶点e条边的无向连通图进行深度优先有哪些信誉好的足球投注网站遍历的路径上，经过n-1条边。

图的深度优先遍历类似于二叉树的___先根____遍历。

按广度优先有哪些信誉好的足球投注网站遍历图的算法需要借助的辅助数据结构是队列。

可以借助于图的遍历算法算法求出无向图的所有连通分量。

Prim算法适用于稠密图，Kruskal算法适用于稀疏图。

可以借助于拓扑排序算法判断一个有向图是否为DAG图。

三、问答题

求解图6.32所示有向图的全部强连通分量

答案：利用遍历算法求出4个强连通分量

已知无向图G=（V，R），G的邻接表如图6.33所示。=1\*GB3①画出该无向图；=2\*GB3②根据该存储结构保存的顶点和边的次序，从顶点A出发，进行深度优先有哪些信誉好的足球投注网站遍历，依次写出访问到的顶点序列；=3\*GB3③进行广度优先有哪些信誉好的足球投注网站遍历，依次写出访问到的顶点序列。

图6.33无向图的邻接表

解答：

=1\*GB3①

=2\*GB3②ABDCEF

=3\*GB3③ABCDEF

简述图的广度优先有哪些信誉好的足球投注网站遍历与二叉树的按层遍历的异同点。

相同点：都需要借助队列完成遍历

相异点：图中可能存在回路，遍历过程中可能再次到达已经访问过的顶点，所以需要visited数组，而二叉树是不需要的。

如图6.34所示无向连通网，使用Prim算法，从顶点A出发，其最小生成树。

图6.34无向连通网