数据结构习题11级用(11)

第七章 图

一、选择题

1．具有4个顶点的无向完全图有（ ）条边。 A． 6 B．12 C. 16 D． 20

2．对于具有n个顶点的连通无向图，其边的个数至少为（ ）。 A． n-1 B．n C． n+1 D． nlogn

3．G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。 A． 6 B．7 C． 8 D． 9

4．对于具有n个顶点的强连通图，其弧条数的最小值为（ ）。 A． n+1 B．n C． n-1 D． n-2

5. 在一个图中，所有顶点的度数之和等于所有边数的（ ）倍；在一个有向图中，

所有顶点的入度之和等于所有顶点出度之和的（ ）倍。 A． 1/2 B． 2 C． 1 D． 4

6．图的深度、广度优先遍历算法分别类似于二叉树的（ ）。

A． 先序遍历和中序遍历 C． 后序遍历和中序遍历

B． 先序遍历和层序遍历

D． 层序遍历和先序遍历

7. 有n个顶点e条边的无向图G,它的邻接表中的表结点总数是( ) A． 2n B．n C． 2e D． e

8. 连通图G中有n个顶点,G的生成树是( )连通子图.

A． 包含G的所有顶点 B． 不必包含G的所有顶点 C． 包含G的所有边 D． 包含G的所有顶点和所有边 9. 下面关于图的存储的叙述中正确的是（ ）

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

数无关

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

数无关

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

无关

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

无关

10．对一个具有n个顶点和e条边的无向图，若采用邻接表存储，则表结点数是( ⒀ )。 A． n+e B． 2e C． e D． n

11．设图G用邻接表存储，则拓扑排序的时间复杂度为（ ）。

33

A． O(n) B． O(n+e) C． O(n2) D． O(n×e) 12．可以进行拓扑排序的图一定是（ ）。 A． 连通图 B． 带权连通图 C． 无回路的图 D． 无回路的有向图

13．下面（ ）可以判断出一个有向图中是否有环（回路）？ A． 求关键路径 B． 拓扑排序 C． 求最短路径 D． 前面都不正确 14．关键路径是事件结点网络中的（ ）。

A． 从源点到汇点的最长路径 B． 从源点到汇点的最短路径 C． 最长的回路 D． 最短的回路 15．下列说法错误的是（ ）。

A． 一个图的邻接矩阵表示是唯一的 B． 一个图的邻接表表示是唯一的

C． 一个图的生成树必为该图的极小连通子图 D． 一个无环有向图的拓扑排序序列必唯一 16．导致图的遍历序列不唯一的因素有（ ）。