第 8 章 图一、单项选择题1
在一个具有n 个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为(A)
A ．s B．s-1 C．s+1 D．n 2
在一个具有n 个顶点的无向图中，若具有 e 条边，则所有顶点的度数之和为（D ）
A ．n B．e C．n+e D．2e 3
在一个具有n 个顶点的无向完全图中，所含的边数为（C ）
A ．n B． n(n-1) C．n(n-1)/2 D．n(n+1)/2 4
在一个具有n 个顶点的有向完全图中，所含的边数为（B ）
A ．n B．n(n-1) C．n(n-1)/2 D．n(n+1)/2 5
在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为（B ）
A ．k B．k+1 C．k+2 D．2k 6
对于一个具有n 个顶点的无向连通图，它包含的连通分量的个数为（B ）
A ．0 B．1 C．n D．n+1 7
若一个图中包含有k 个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用（ A ）次深度优先搜索遍历的算法
A ．k B．1 C．k-1 D．k+1 8
若要把n 个顶点连接为一个连通图，则至少需要（ C ）条边
A ．n B．n+1 C．n-1 D．2n 9
在一个具有n 个顶点和e 条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（D ）
A ．n B．n e C．e D．2 e 10
在一个具有n 个顶点和e 条边的有向图的邻接矩阵中，表示边存在的元素个数为（C ）
A ．n B．n e C．e D．2 e 11
在一个具有n 个顶点和e 条边的无向图的邻接表中，边结点的个数为（D ）
A ．n B．n e C．e D．2 e 12
在一个具有n 个顶点和e 条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为（A ）
A ．n B．
