1．任何一个无向连通图的最小生成树________。

A．只有一棵           B．有一棵或多棵

C．一定有多棵         D．可能不存在

2．下列算法中，________算法用来求图中每对顶点之间的最短路径。

A．Dijkstra      B．Floyed      C．Prim     D．Kruskal

3．由N个顶点组成的有向图，最多可以有________条边。

A．N*N           B．N（N+1）    C．N（N-1） D．N(N-1)/2

4．关键路径是结点网络中________。

A. 从源点到汇点的最长路径

B. 从源点到汇点的最短路径

C. 最长的回路

D. 最短的回路

5．在一个图中，所有顶点的度数之和等于所有边数的________倍。

A．2             B．3           C．1        D．1.5

6. 下面关于图的存储的叙述中正确的是________ 。

A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关

B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关

C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关

D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关

7. AOV 网是一种________。

A．有向图        B．无向图      C．无向无环图   D．有向无环图

8. 在一个具有n个顶点的无向完全图中，包含有 n(n-1)/2 条边，在一个具有 n 个顶点的有向完全图中，包含有 ________ 条边。

A．n+2           B．n(n-1)      C．n²          D．2n

9. 设完全无向图中有n个顶点，则该完全无向图中有________条边。

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

10.设有向无环图 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

11.设某无向图有n个顶点，则该无向图的邻接表中有________个表头结点。

A．2n            B．n           C．n/2         D．n(n-1)

12.设无向图G 中有n个顶点，则该无向图的最小生成树上有________条边。

A．n             B．n-1         C．2n          D．2n-1

13.设无向图G 中的边的集合E={(a ，b) ，(a，e)，(a，c)，(b，e)，(e，d) ，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为________。

A．aedfcb        B．acfebd      C．aebcfd     D．aedfbc

14.有n个顶点 e条边的无向图 G,它的邻接表中的表结点总数是________。

A．2n            B．n           C．2e          D．e