若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图（）

单项选择题若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图（）

A.是个有根有向图
B.是个强连通图
C.含有多个入度为0的顶点
D.含有顶点数目大于1的强连通分量

1.单项选择题对于有n个顶点e条边的有向图，求最短路径的Floyd算法的时间复杂度为（）。

A.O（n）
B.O（ne）
C.O（n²）
D.O（n³）

2.单项选择题对于有n个顶点e条边的有向图，求最短路径的Dijkstra算法的时间复杂度为（）。

A.O（n）
B.O（n+e）
C.O（n²）
D.O（ne）

3.单项选择题用Prim和Kruskal两种算法构造图的最小生成树，所得到的最小生成树（）。

A.是相同的
B.是不同的
C.可能相同，也可能不同
D.以上都不对

4.单项选择题 已知一个图的邻接表如图所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）。

A.0 1 3 2
B.0 2 3 1
C.0 3 2 1
D.0 1 2 3

5.单项选择题 已知一个图的邻接表如图所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（）。

A.0 1 3 2
B.0 2 3 1
C.0 3 2 1
D.0 1 2 3

6.单项选择题一个无向图中包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用（）次深度优先遍历算法。

A.k
B.1
C.k-1
D.k+1

7.单项选择题图的广度优先遍历算法中用到辅助队列，每个顶点最多进队（）次。

A.1
B.2
C.3
D.不确定

8.单项选择题若一个图的邻接矩阵是对称矩阵，则该图一定是（）。

A.有向图
B.无向图
C.连通图
D.无向图或有向图

9.单项选择题n个顶点的强连通图中至少有（）条边。

A.n
B.n-1
C.2n
D.n（n-1）

10.单项选择题有8个顶点的有向完全图有（）条边。

A.14
B.28
C.56
D.112