求解最短路径的Floyd算法的时间复杂度为（）。A．O（n)B．O（n+c)C．O（n2)D．O（n3)

v6)11，(v2，v5)1，(v4，v5)4，(v4，v6)6，(v5，v7)7，(v6，v7)3}(注：顶点偶对括号外的数据表示边上的权值)，从源点v1到顶点v7的最短路径上经过的顶点序列是（ ）。

A．v1，v2，v5，v7

B．v1，v3，v4，v6，v7

C．v1，v2，v3，v4，v5，v7

D．v1，v2，v5，v4，v6，v6

以下叙述正确的是（ ）。

A．最短路径一定是简单路径

B．Diikstra算法不适合求有回路的带权图的最短路径

C．Diikstra算法不适合求任意两个顶点的最短路径

D．Floyd算法求两个项点的最短路径时，pathk-1一定是pathk的子集

以下叙述中正解的是（ ）。

A．只要无向连通图中没有权值相同的边，则其最小生成树唯一

B．只要无向图中有权值相同的边，则其最小生成树一定不唯一

C．从n个顶点的连通图中选取n-1条权值最小的边，即可构成最小生成树

D．设连通图G含有n个顶点，则含有n个顶点n-1条边的子图一定是G的生成树

用Prim算法和Kruskal算法构造图的最小生成树，所得到的最小生成树（ ）。

A．相同

B．不相同

C．可能相同，可能不同

任何一个无向连通图的最小生成树（ ）。

A．有一棵或多棵

B．只有一棵

C．一定有多棵

D．可能不存在

对图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。

A．4

B．3

C．2

D．1

使用DFS算法递归地遍历一个无环有向图，并在退出递归时输出相应顶点，这样得到的顶点序列是（ ）。

A．逆拓扑有序

B．拓扑有序

C．无序的

D．都不是

判断有向图中是否存在回路，除了可以利用拓扑排序外，还可以利用（ ）。

A．求关键路径的方法

B．求最短路径的Diikstra算法

C．深度优先遍历算法

D．广度优先遍历算法

若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是( )。【2013年全国试题8(2分)】

A．h，c，a，b，d,e，g,f

B．e，a,f,g，b，h，c，d

C．d,b，c，a，h，e，f,g

D．a，b，c，d，h，e,f,g

设图的邻接矩阵A如下所示。各顶点的度依次是( )。【2013年全国试题7(2分)】

A．1，2，1，2

B．2，2，1，1

C．3，4，2，3

D．4，4，2，2