超星 - 单元测试五：图 - 查题吧

单选题

设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（）。

A. 1，2，3，4
B. 2，3，4，1
C.1，4，2，3
D. 1，2，4，3

单选题

下列说法中不正确的是（）。

A. 无向图的极大连通子图称为连通分量
B. 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
C. 连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
D. 有向图的遍历不可采用广度优先搜索算法

单选题

在用邻接表表示图时, 对图进行深度优先搜索遍历的算法的时间复杂度为（）。

A. Ｏ(n)
B.Ｏ(n+e)
C. Ｏ(n2)
D. Ｏ(n3)

单选题

在一个具有n个顶点的无向图中，每个顶点度的最大值为（）。

A. n
B. n-1
C. n+1
D. 2(n-1)

判断题

若一个有向图无环，则它一定有唯一的拓扑序列。

A. 对
B. 错

判断题

最小生成树的KRUSKAL算法是一种贪心法。

A. 对
B. 错

判断题

无向图G（设G中至少有2个顶点）采用邻接矩阵存储，若从某顶点开始对无向图G进行广度优先遍历,则所得的遍历序列总是唯一的。

A. 对
B. 错

判断题

图的深度优先遍历是通过使用队列队列来实现的。

A. 对
B. 错

判断题

如在一棵生成树中增加一条边，则必定构成环。

A. 对
B. 错

判断题

如在一棵生成树中去掉一条边，则连通图变为不连通的。

A. 对
B. 错

1