1l.n个顶点e条边的图采用邻接矩阵存储,深度优先遗历算法的时间复杂度为Om2;若采用邻接 表存储时,该算法的时间复杂度为On+e 12.n个顶点e条边的图用邻接矩阵存储,广度优先遍历算法的时间复杂度为Om2);若采用邻接 表存储,该算法的时间复杂度为O(n+e) l3.图的BFS生成树的树高比DFS生成树的树高或相等 14.用普里姆(Prim算法求具有n个顶点e条边的图的最小生成树的时间复杂度为On2);用克鲁 斯卡尔( Kruskal)算法的时间复杂度是 O(elogze)。 15.若要求一个稀疏图G的最小生成树,最好用京鲁斯卡尔( Kruskal算法来求解。 16.若要求一个稠密图G的最小生成树,最好用普里姆Pim,算法来求解。 17.用 Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路 径的。 18.拓扑排序算法是通过重复选择具有0↑前驱顶点的过程来完成的。 三、简答题(每题6分,共24分) 1.【严题集71①】已知如图所示的有向图,请给出该图的 (1)每个顶点的入/出度; 顶点 (2)邻接矩阵; 入度 (3)邻接表; 出度 4)逆邻接表。 谷案: 7.1(1) (2)邻接矩阵 出出 1001 出度022313 1001 (3)邻接表 (4)逆邻接表 4A3 11. n 个顶点 e 条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 O(n2 ) ；若采用邻接 表存储时，该算法的时间复杂度为 O(n+e) 。 12. n 个顶点 e 条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 O(n2 ) ；若采用邻接 表存储，该算法的时间复杂度为 O(n+e) 。 13. 图的 BFS 生成树的树高比 DFS 生成树的树高 小或相等 。 14. 用普里姆(Prim)算法求具有 n 个顶点 e 条边的图的最小生成树的时间复杂度为 O(n2 ) ；用克鲁 斯卡尔(Kruskal)算法的时间复杂度是 O(elog2e) 。 15. 若要求一个稀疏图 G 的最小生成树，最好用 克鲁斯卡尔(Kruskal) 算法来求解。 16. 若要求一个稠密图 G 的最小生成树，最好用 普里姆(Prim) 算法来求解。 17. 用 Dijkstra 算法求某一顶点到其余各顶点间的最短路径是按路径长度 递增 的次序来得到最短路 径的。 18. 拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。 三、简答题（每题 6 分，共 24 分） 1. 【严题集 7.1①】已知如图所示的有向图，请给出该图的: （1） 每个顶点的入/出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表。 答案： 顶点 1 2 3 4 5 6 入度 出度