《T7-图(练习1)课件.ppt》由会员分享，可在线阅读，更多相关《T7-图(练习1)课件.ppt（19页珍藏版）》请在三一文库上搜索。
1、图,练习1,1,设有8个结点的无向图，该图至少应有（ ）条边能确保是一个连通图。 A5 B6 C7 D8,C,2,对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为（ ）。 Ak1 Bk2 Ck1-k2 Dk1+k2,B,3,对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为（ ）。 Ak1 Bk2 Ck1-k2 Dk1+k2,A,4,对于一个无向图，若一个顶点的度为k，则对应邻接表中该顶点单链表中的结点数为（ ）。,k,5,一个有n个顶点的无向连通图，它所包含的连通分量个数为（ ）。 A0 B1 Cn Dn
2、+1,B,6,已知一个有向图的邻接矩阵表示，计算第i个结点的出度的方法是（ ）。 A求矩阵第i列非零元素之和 B求矩阵第i行非零元素之和,B,7,已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是（ ）。 A求矩阵第i列非零元素之和 B求矩阵第i行非零元素之和,A,8,在无向图G的邻接矩阵A中，若Aij等于 1，则Aji 等于（ ）。 A0 B1 Cn,B,9,n个顶点的连通图至少（ ）条边 A1 Bn-1 Cn Dn+1,B,10,对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ）。 An B (n-1)*(n-1) Cn-1 Dn*n,D,11,一个有n个顶点
3、的有向完全图有（ ）条边。 An Bn(n-1) Cn(n-1)/2 D2n,B,12,具有4个顶点的无向完全图有（ ）条边。 A6 B12 C16 D20,A,13,在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A1/2 B1 C2 D4,B,14,在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。 A1/2 B1 C2 D4,C,15,在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为( )。 A. k B. k+1 C. k+2 D. 2k,B,16,对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为( )。 A. 0 B. 1 C. n D. n+1,B,17,在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为( )。 A. n B. ne C. e D. 2e,D,18,在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为( )。 A. n B. ne C. e D. 2e,C,