《图自测卷解答》由会员分享，可在线阅读，更多相关《图自测卷解答（8页珍藏版）》请在金锄头文库上搜索。
1、 第第 7 章章 图图 自测卷解答自测卷解答 一、单选题（每题一、单选题（每题 1 1 分，共分，共 1616 分）分） （ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的在一个图中，所有顶点的度数之和等于图的边数的 倍。倍。A1/2 B. 1 C. 2 D. 4 （ B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。倍。A1/2 B. 1 C. 2 D. 4 （ B ）3. 有有 8 个结点的无向图最多有个结点的无向图最多有 条边。条边。A14 B. 28 C. 56 D. 112 （ C ）4.
2、有有 8 个结点的无向连通图最少有个结点的无向连通图最少有 条边。条边。A5 B. 6 C. 7 D. 8 （ C ）5. 有有 8 个结点的有向完全图有个结点的有向完全图有 条边。条边。A14 B. 28 C. 56 D. 112 （ B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。来实现算法的。 A栈栈 B. 队列队列 C. 树树 D. 图图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。来实现算法的。 A栈栈 B. 队列队列 C. 树树 D. 图图
3、 （ C ）8. 已知图的邻接矩阵，根据算法思想，则从顶点已知图的邻接矩阵，根据算法思想，则从顶点 0 出发按深度优先遍历的结点序出发按深度优先遍历的结点序 列是列是（ D ）9. 已知图的邻接矩阵同上题已知图的邻接矩阵同上题 8，根据算法，则从顶点，根据算法，则从顶点 0 出发，按深度优先遍历出发，按深度优先遍历 的结点序列是的结点序列是 A 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 3 4 2 5 6（ B ）10. 已知图的邻接矩阵同上题已知图的邻接矩阵同上题 8，根据算法，则从顶点，根据算法，则从顶点 0 出发，按广度
4、优先遍历的出发，按广度优先遍历的 结点序列是结点序列是 A 0 2 4 3 6 5 1 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4 2 5 6（ C ）11. 已知图的邻接矩阵同上题已知图的邻接矩阵同上题 8，根据算法，则从顶点，根据算法，则从顶点 0 出发，按广度优先遍历出发，按广度优先遍历 的结点序列是的结点序列是 A 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6 （ D ）12. 已知图的邻接表如下所示，根据算法，则从顶点已知图的邻接表如下所示，根据算法，则从
5、顶点 0 出发按深度优先遍历的结出发按深度优先遍历的结 点序列是点序列是A0 2 4 3 1 5 6 B. 0 1 3 6 5 4 2 C. 0 4 2 3 1 6 5 D.0 3 6 1 5 4 20100011101100001011010110011001000110010011011110A0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3（ A ）13. 已知图的邻接表如下所示，根据算法，则从顶点已知图的邻接表如下所示，根据算法，则从顶点 0 出发按广度优先遍历的出发按广度优先遍历的 结点序列是结点序列是（ A ）14. 深度优先遍历类似于二叉树的深度优
6、先遍历类似于二叉树的 A先序遍历先序遍历 B. 中序遍历中序遍历 C. 后序遍历后序遍历 D. 层次遍历层次遍历（ D ）15. 广度优先遍历类似于二叉树的广度优先遍历类似于二叉树的 A先序遍历先序遍历 B. 中序遍历中序遍历 C. 后序遍历后序遍历 D. 层次遍历层次遍历（ A ）16. 任何一个无向连通图的最小生成树任何一个无向连通图的最小生成树 A只有一棵只有一棵 B. 一棵或多棵一棵或多棵 C. 一定有多棵一定有多棵 D. 可能不存可能不存 在在 （注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯 一）一
7、） 二、填空题（每空二、填空题（每空 1 1 分，共分，共 2020 分）分） 1. 图有图有 邻接矩阵邻接矩阵 、 邻接表邻接表 等存储结构，遍历图有等存储结构，遍历图有 深度优先遍历深度优先遍历 、 广度优先遍广度优先遍 历历 等方法。等方法。 2. 有向图有向图 G 用邻接表矩阵存储，其第用邻接表矩阵存储，其第 i 行的所有元素之和等于顶点行的所有元素之和等于顶点 i 的的 出度出度 。 3. 如果如果 n 个顶点的图是一个环，则它有个顶点的图是一个环，则它有 n 棵生成树。棵生成树。 （以任意一顶点为起点，以任意一顶点为起点， 得到得到 n-1 条边）条边） 4. n 个顶点个顶点 e
8、 条边的图，若采用邻接矩阵存储，则空间复杂度为条边的图，若采用邻接矩阵存储，则空间复杂度为 O(n2) 。 5. n 个顶点个顶点 e 条边的图，若采用邻接表存储，则空间复杂度为条边的图，若采用邻接表存储，则空间复杂度为 O(n+e) 。 6. 设有一稀疏图设有一稀疏图 G，则，则 G 采用采用 邻接表邻接表 存储较省空间。存储较省空间。 7. 设有一稠密图设有一稠密图 G，则，则 G 采用采用 邻接矩阵邻接矩阵 存储较省空间。存储较省空间。 8. 图的逆邻接表存储结构只适用于图的逆邻接表存储结构只适用于 有向有向 图。图。 9. 已知一个图的邻接矩阵表示，删除所有从第已知一个图的邻接矩阵表示
9、，删除所有从第 i 个顶点出发的方法是个顶点出发的方法是将邻接矩阵的第将邻接矩阵的第 i 行行 全部置全部置 0。 10. 图的深度优先遍历序列图的深度优先遍历序列 不是不是 惟一的。惟一的。 11. n 个顶点个顶点 e 条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 O(n2) ；若采用邻接表存储时，该算法的时间复杂度为；若采用邻接表存储时，该算法的时间复杂度为 O(n+e) 。 12. n 个顶点个顶点 e 条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 O
10、(n2) ；若采用邻接表存储，该算法的时间复杂度为；若采用邻接表存储，该算法的时间复杂度为 O(n+e) 。 13. 图的图的 BFS 生成树的树高比生成树的树高比 DFS 生成树的树高生成树的树高小或相等小或相等 。 14. 用普里姆用普里姆(Prim)算法求具有算法求具有 n 个顶点个顶点 e 条边的图的最小生成树的时间复杂度为条边的图的最小生成树的时间复杂度为 O(n2) ；用克鲁斯卡尔；用克鲁斯卡尔(Kruskal)算法的时间复杂度是算法的时间复杂度是 O(elog2e) 。 15. 若要求一个稀疏图若要求一个稀疏图 G 的最小生成树，最好用的最小生成树，最好用 克鲁斯卡尔克鲁斯卡尔(
11、Kruskal) 算法来求解。算法来求解。 16. 若要求一个稠密图若要求一个稠密图 G 的最小生成树，最好用的最小生成树，最好用 普里姆普里姆(Prim) 算法来求解。算法来求解。 17. 用用 Dijkstra 算法求某一顶点到其余各顶点间的最短路径是按路径长度算法求某一顶点到其余各顶点间的最短路径是按路径长度递增递增的次序来得的次序来得 到最短路径的。到最短路径的。 18. 拓扑排序算法是通过重复选择具有拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。个前驱顶点的过程来完成的。 三、简答题（每题三、简答题（每题 6 6 分，共分，共 2424 分）分） 1. 已知如图所示的
12、有向图，请给出该图的已知如图所示的有向图，请给出该图的:A0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2（1）每个顶点的入每个顶点的入/出度；出度； （2）邻接矩阵；邻接矩阵； （3）邻接表；邻接表； （4）逆邻接表。逆邻接表。答案：答案：2. 请对下图的无向带权图：请对下图的无向带权图：（1）写出它的邻接矩阵，并按普里姆算法求其最小生成树；写出它的邻接矩阵，并按普里姆算法求其最小生成树； （2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。解：设起点为解：设起点为 a。可以直接由原始图画出最小生成树，而且
13、最小生成。可以直接由原始图画出最小生成树，而且最小生成 树只有一种（类）树只有一种（类）! 邻接矩阵为：邻接矩阵为： PRIM 算法（横向变化）：算法（横向变化）： VbcdefghUV-UVex lowcosta 4a 3aaaaaab,c,d,e,f,g,h Vex lowcosta 40c 5aaac 5a,cb, d,e,f,g,hVex lowcost00c 5b 9aac 5a,c,bd,e,f,g,hVex lowcost000d 7d 6d 5d 4a,c,b,d e,f,g,hVex lowcost000d 7d 6d 50a,c,b,d ,h e,f,g Vex000dg00a,c,b,d ,h f,e 顶点123456入度出度064560252036307945670555505395504340最小生成树最小生成树 lowcost72,gVex lowcost000f 3000a,c,b,d ,h ,g, f e Vex lowcost0000000a,c,b,d ,h ,g, f, e 邻接表为：邻接表为：ab4c3ba4c5d5e9ca3b5d5
