1483: 算法基础(图论)

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

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

2.要连通具有 n个顶点的有向图，至少需要(     )条边。

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

3. 在下面的图中，若从顶点 (      ) 出发存在一条路径可以遍历这个图上的每一条边，而且仅仅遍历一次。

A. A点         B. B点           C. C点           D. D点

    4. 如图所示的有向图，共有(      ) 个强连通分量。

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

5.  己知一有向图的邻接表存储结构如下图，从顶点 1出发进行深度优先遍历得到的序列是(        ) 。

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

6. 某无向图的邻接矩阵如下所示，可以得出，该图共有(      ) 个顶点。

A. 9         B. 5         C. 3         D. 4

7、如图所示的DAG图，其拓扑排序序列为(       )。

tle="" align="" alt="" />

A. ADBGC         B. ADGBC        C. AGBDC        D. ACDGB

8. 任何一个连通图的最小生成树 (     )。

 A．只有一棵       B. 有一棵或多棵     C. 一定有多棵      D. 可能不存在

9. 下图所示带权无向图的最小生成树的权为 (       ）
       A. 14         B. 15         C. 17         D. 18

10. 某一国家共有6个城市，每个城市与任何一个城市之间都有一条道路连接，如下列表为6个城市之间两两之间的距离，现在问你从城市1到城市6的最短距离为(       )。
 A. 9         B. 8         C. 7         D. 6