文档介绍：第七章图一、选择题 ( )。 n,则该图最多有( )条边。 -1 (n-1)/2 (n+1)/2 . n n个顶点的有向图,至少需要( )条边。 -l +l ( )。 *n B. n(n+1) *(n-l) 6 .一个有 n 个结点的图,最少有( )个连通分量,最多有( )个连通分量。 -1 7 .在一个无向图中,所有顶点的度数之和等于所有边数( )倍,在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的( )倍。 DFS 遍历一个无环有向图,并在 DFS 算法退栈返回时打印相应的顶点,则输出的顶点序列是()。 ?( ) 网 ???????????010 101 010A 可以看出,该图共有(①)个顶点;如果是有向图该图共有( ②)条弧;如果是无向图,则共有( ③)条边。①.②.③. abed cf N个顶点的图用邻接矩阵 A表示时,顶点 Vi的度是( )。 A.?? nijiA 1],[ B.???? n1jj,iA C.?? niijA 1],[ D.?? nijiA 1],[ +???? n1ji,jA 14 .用相邻矩阵 A 表示图,判定任意两个顶点 Vi和Vj 之间是否有长度为 m的路径相连,则只要检查( )的第 i行第 j列的元素是否为零即可。 -1 15. 下列说法不正确的是( )。 :深度遍历和广度遍历 G=(V,E), 其中: V={a,b,c,d,e,f}, E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)} ,对该图进行深度优先遍历, 得到的顶点序列正确的是( )。 ,b,e,c,d,f ,c,f,e,b,d ,e,b,c,f,d ,e,d,f,c, b 17. 设图如右所示,在下面的 5 个序列中,符合深度优先遍历的序列有多少? () aebdfcacfdebaedfcbaefdcba 18. 下图中给出由 7 个顶点组成的无向图。从顶点 1 出发,对它进行深度优先遍历得到的序列是(①),而进行广度优先遍历得到的顶点序列是( ②)。①. E. 以上答案均不正确②. E. 以上答案均不正确 (回路): 20. 在图采用邻接表存储时,求最小生成树的 Prim 算法的时间复杂度为()。 (n) (n+e) (n 2)(n 3) 22. (1). 求从指定源点到其余各顶点的迪杰斯特拉( Dijkstra )最短路径算法中弧上权不能为负的原因是在实际应用中无意义; (2). 利用 Dijkstra 求每一对不同顶点之间的最短路径的算法时间是 O(n 3);(图用邻接矩阵表示) (3). Floyd 求每对不同顶点对的算法中允许弧上的权为负,但不能有权和为负的回路。上面不正确的是( )。 A.(1),(2),(3) B.(1) C.(1),(3) D.(2),(3) ()时, BFS 算法可用来解决单源最短路径问题。 24. 求解最短路径的 Floyd 算法的时间复杂度为()。 (n)(n+c )(n*n )(n*n*n ) G=(V,E) ,其中 V={V 1,V 2,V 3,V 4,V 5,V 6,V 7}, E={<V 1,V 2>,<V 1,V 3>,<V