MOOC数据结构与算法Python版-第十二周测验
1 单选(2分)
下列关于Dijkstra算法的说法错误的有 C
-
A.Dijkstra算法的使用条件，要求整个图架构与所有边的权重均已知。
-
B.当图中存在负权边时，Dijkstra算法不一定能求出源点到所有点的最短路。
-
C.当图中存在负权边时，Dijkstra算法必定不能求出源点到所有点的最短路
-
D.当图中不存在负权边时，Dijkstra算法能求出每对顶点间最短路径。
2 单选(2分)
下列说法错误的是 C
-
A.一个图的邻接表表示是不唯一的
-
B.一个图的生成树必为该图的极小连通子图
-
C.一个无环有向图的拓扑排序序列必唯一
-
D.一个图的邻接矩阵表示是唯一的
3单选(2分)
下图中的强连通分支的个数为多少个？B
-
A.1
-
B.3
-
C.2
-
D.4
4 单选(2分)
无向图G=(V, E)，其中：V={a, b, c, d, e, f}, E={(a, b), (a, e), (a, c), (b, e), (c, f), (f, d), (e, d)}，对该图进行深度优先遍历（优先访问编号小的结点），得到的顶点序列为？D
-
A.abefdc
-
B.abecfd
-
C.abcefd
-
D.abedfc
5 单选(2分)
请使用Prim算法从结点0出发求下图的最小生成树，依次写出每次被加入到最小生成树中边的编号（如果同时存在多条边满足要求，选择编号最小的）。顶点a到顶点b (a < b)之间的边编号为ab，例如图中权值为1的边编号为02。C
-
A.02 35 14 25 12
-
B.其他选项都不对
-
C.02 25 35 12 14
-
D.02 14 25 35 12
6 多选(3分)
在有向图G的拓扑序列中，若顶点在顶点
之前，则下列情形可能出现的有 ABD
-
A.G中没有边(
，
)
-
B.G中有一条从
-
C.G中有一条从
-
D.G中有边(
7 多选(3分)
选出正确的叙述。AD
-
A.将有向图的一个强连通分量中的边全部反向仍然是强连通分量
-
B.对于有向图，所有结点的入度加起来一定是偶数
-
C.对于一个无向的连通图，一定存在一种给边指定方向的方案使得这个图变成强连通图
-
D.对于无向图，所有结点的度数加起来一定是偶数
8 多选(3分)
有向图G具有四个顶点1~4和三条边1->3, 2->4, 3->4，选出它可能的拓扑排序。ACD
-
A.2134
-
B.1342
-
C.1324
-
D.1234