对某个无向图的邻接矩阵来说,下列叙述正确的是()。

A. 第i行上的非零元素个数和第i列上的非零元素个数一定相等
B. 矩阵中的非零元素个数等于图中的边数
C. 第i行与第i列上的非零元素的总数等于顶点vi的度数
D. 矩阵中非全零行的行数等于图中的顶点数

设连通图G中的边集E={(a,b), (a,e), (a,c), (b,e), (e,d), (d,f), (f,c)},则从顶点a出发得到的深度优先遍历的顶点序列错误的是()。

A. abedfc
B. acfebd
C. aebdfc
D. aedfcb

对含有n个顶点、e条边的带权图求最短路径的Dijkstra算法的时间复杂度为( )。

A. O(n)
B. O(n+e)
C. O(n*n)
D. O(n*e)

在用邻接表表示有N个结点E条边的图时,深度优先遍历算法的时间复杂度为( ),在用邻接矩阵表示有N个结点E条边的图时,深度优先遍历算法的时间复杂度为( )。

A. O(N*E),O(N*N)
B. O(N+E),O(N*E)
C. O(N+E),O(N*N)
D. O(N*N),O(N*N)

若要检查有向图中有无回路,除了可以利用拓扑排序算法外,下列哪种算法也可以用?

A. 广度优先搜索
B. 深度优先搜索
C. Prim算法
Dijkstra算法

无向图的邻接矩阵是对称矩阵,所以可采用压缩存储法(下三角),其存储空间只需。