超星 - 第八章图课后测试 - 查题吧

单选题

在图采用邻接表存储时,求最小生成树的 Prim 算法的时间复杂度为( )。

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

单选题

下列说法不正确的是( )。

A.图的遍历是从给定的源点出发每一个顶点仅被访问一次
B.遍历的基本算法有两种:深度遍历和广度遍历
C.图的深度遍历不适用于有向图
D.图的深度遍历是一个递归过程

单选题

一个有n个结点的图,最少有1个连通分量,最多有( )个连通分量。

A.0
B.1
C.n-1
D.n

单选题

一个有向无环图的拓扑排序序列( )是唯一的。

A.一定
B.不一定

单选题

下列哪一种图的邻接矩阵是对称矩阵?( )

A.有向图
B.无向图
C.AOV网
D.AOE网

单选题

设无向图的顶点个数为n,则该图最多有( )条边。

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

单选题

下列关于AOE网的叙述中,不正确的是( )。

A.关键活动不按期完成就会影响整个工程的完成时间
B.任何一个关键活动提前完成,那么整个工程将会提前完成
C.所有的关键活动提前完成,那么整个工程将会提前完成
D.某些关键活动提前完成,那么整个工程可能会提前完成

单选题

一个n个顶点的连通无向图,其边的个数至少为( )。

A.n-1
B.n
C.n+1
D.nlogn

单选题

若无向图G(V，E)中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（）。

A. 6
B. 15
C. 16
D. 21

单选题

在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的( )倍。

A.1/2
B.2
C.1
D.4

1