Problem G: [CSP-S1][选择] 图论基础2

1. 关键路径算法用于求解（ ）。

A. 最短路径

B. 最长路径

C. 工程工期

D. 最小生成树

2. 一个无向图有8个顶点，所有顶点的度数都是4，则边数为（ ）。

A. 16

B. 32

C. 8

D. 4

3. 若图G的边数m > n(n-1)/2（n为顶点数），则G一定是（ ）。

A. 连通图

B. 非连通图

C. 完全图

D. 树

4. 二分图（二部图）的顶点可划分为两个集合V1和V2，且图中每条边连接（ ）。

A. V1内部顶点

B. V2内部顶点

C. V1和V2之间

D. 任意顶点

5. 有向图G的拓扑序列不存在，则G中（ ）。

A. 存在环

B. 不存在环

C. 所有顶点入度为0

D. 所有顶点出度为0

6. 用Prim算法求最小生成树的时间复杂度为（ ）。

A. O(n^2)

B. O(elog e)

C. O(n log n)

D. O(n)

7. 一个无向图有6个顶点，9条边，则该图至少需要删除（ ）条边才能得到一棵生成树。

A. 3

B. 4

C. 5

D. 6

8. 若图G的邻接表中有奇数个表结点，则G是（ ）。

A. 无向图

B. 有向图

C. 带权图

D. 完全图

9. 在带权图中，从顶点A到顶点B的最短路径是（ ）。

A. 边数最少的路径

B. 权值之和最小的路径

C. 经过顶点最少的路径

D. 权值最大的边最小的路径

10. 若图G的顶点表示活动，边表示活动间的先后关系，则G是（ ）。

A. AOV网

B. AOE网

C. 有向无环图

D. 完全图