第 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．2n C．e D．2e 13. 在一个无权图的邻接表表示中，每个边结点至少包含（B ）域。A ．1 B．2 C．3 D．4 14. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为（ B ）。A．k1 B．k2 C．k1-k2 D．k1+k2 15. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结点数为（C ）。A．k1 B．k2 C． k1-k2 D．k1+k2 16. 对于一个无向图，下面（A ）说法是正确的。A．每个顶点的入度等于出度B．每个顶点的度等于其入度与出度之和C．每个顶点的入度为0 D．每个顶点的出度为0 17. 在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的（A ）。A．出边数B...
VIP
