图练习1.pptVIP

图 练习1 1 设有8个结点的无向图，该图至少应有（ ）条边能确保是一个连通图。 A．5 B．6 C．7 D．8 2 对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为（ ）。 A．k1 B．k2 C．k1-k2 D．k1+k2 3 对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为（ ）。 A．k1 B．k2 C．k1-k2 D．k1+k2 4 对于一个无向图，若一个顶点的度为k，则对应邻接表中该顶点单链表中的结点数为（ ）。 5 一个有n个顶点的无向连通图，它所包含的连通分量个数为（ ）。 A．0 B．1 C．n D．n+1 6 已知一个有向图的邻接矩阵表示，计算第i个结点的出度的方法是（ ）。 A．求矩阵第i列非零元素之和 B．求矩阵第i行非零元素之和 7 已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是（ ）。 A．求矩阵第i列非零元素之和 B．求矩阵第i行非零元素之和 8 在无向图G的邻接矩阵A中，若A[i][j]等于 1，则A[j][i ]等于（ ）。 A．0 B．1 C．n 9 n个顶点的连通图至少（ ）条边 A．1 B．n-1 C．n D．n+1 10 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ）。 A．n B． (n-1)*(n-1) C．n-1 D．n*n 11 一个有n个顶点的有向完全图有（ ）条边。 A．n B．n(n-1) C．n(n-1)/2 D．2n 12 具有4个顶点的无向完全图有（ ）条边。 A．6 B．12 C．16 D．20 13 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A．1/2 B．1 C．2 D．4 14 在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。 A．1/2 B．1 C．2 D．4 15 在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为( )。 A. k B. k+1 C. k+2 D. 2k 16 对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为( )。 A. 0 B. 1 C. n D. n+1 17 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为( )。 A. n B. n?e C. e D. 2?e 18 在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为( )。 A. n B. n?e C. e D. 2?e C B A k B B A B B D B A B C B B D C