《图测试题答案》由会员分享，可在线阅读，更多相关《图测试题答案（6页珍藏版）》请在金锄头文库上搜索。
1、1第第 6 章章 图图 自测卷解答自测卷解答 姓名姓名 班级班级 一、单选题（每题一、单选题（每题 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. 11
2、2 （ C ）4. 有有 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
3、. 树树 D. 图图 （ 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，根据算法，则从顶点，根据算法，则从顶点
4、0 出发，按广度优先遍历的结点序列是出发，按广度优先遍历的结点序列是 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 （建议：（建议：0 1 2 3 4 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 6A0 2 4 3 1 5 6 B. 0 1
5、 3 6 5 4 2 C. 0 4 2 3 1 6 5 D.0 3 6 1 5 4 2建议：0 1 3 4 2 5 601000111011000010110101100110010001100100110111102（ D ）12. 已知图的邻接表如下所示，根据算法，则从顶点已知图的邻接表如下所示，根据算法，则从顶点 0 出发按深度优先遍历的结点序列是出发按深度优先遍历的结点序列是（ 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. 已知一个图的邻接矩阵表示，删除所有从第已知一个图的邻接矩阵表示，删除所有从第 i 个顶
9、点出发的方法是个顶点出发的方法是 将邻接矩阵的第将邻接矩阵的第 i 行全部置行全部置 0 。10. 图的深度优先遍历序列图的深度优先遍历序列 不是不是 惟一的。惟一的。A0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3A0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2311. n 个顶点个顶点 e 条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 O(n2) ；若采用邻接；若采用邻接 表存储时，该算法的时间复杂度为表存储时，该算法的时间复杂度为 O(n+e) 。12.
10、 n 个顶点个顶点 e 条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 O(n2) ；若采用邻；若采用邻 接表存储，该算法的时间复杂度为接表存储，该算法的时间复杂度为 O(n+e) 。13. 图的图的 BFS 生成树的树高比生成树的树高比 DFS 生成树的树高生成树的树高 小或相等小或相等 。14. 用普里姆用普里姆(Prim)算法求具有算法求具有 n 个顶点个顶点 e 条边的图的最小生成树的时间复杂度为条边的图的最小生成树的时间复杂度为 O(n2) ；用克鲁；用克鲁 斯卡尔斯卡尔(Kruskal)算法的时间复杂度是算法的时间复
11、杂度是 O(elog2e) 。15. 若要求一个稀疏图若要求一个稀疏图 G 的最小生成树，最好用的最小生成树，最好用 克鲁斯卡尔克鲁斯卡尔(Kruskal) 算法来求解。算法来求解。16. 若要求一个稠密图若要求一个稠密图 G 的最小生成树，最好用的最小生成树，最好用 普里姆普里姆(Prim) 算法来求解。算法来求解。17. 用用 Dijkstra 算法求某一顶点到其余各顶点间的最短路径是按路径长度算法求某一顶点到其余各顶点间的最短路径是按路径长度 递增递增 的次序来得到最短路的次序来得到最短路 径的。径的。18. 拓扑排序算法是通过重复选择具有拓扑排序算法是通过重复选择具有 0 个前驱顶点的
12、过程来完成的。个前驱顶点的过程来完成的。三、简答题（每题三、简答题（每题 6 6 分，共分，共 2424 分）分）1. 已知如图所示的有向图，请给出该图的已知如图所示的有向图，请给出该图的: （1）每个顶点的入每个顶点的入/出度；出度； （2）邻接矩阵；邻接矩阵； （3）邻接表；邻接表； （4）逆邻接表。逆邻接表。答案：答案：顶点123456入度出度42. 请对下图的无向带权图：请对下图的无向带权图： （1）写出它的邻接矩阵，并按普里姆算法求其最小生成树；写出它的邻接矩阵，并按普里姆算法求其最小生成树； （2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。写出它的邻接表，并按克鲁斯卡尔算法
13、求其最小生成树。解：设起点为解：设起点为 a。可以直接由原始图画出最小生成树，而且最小生。可以直接由原始图画出最小生成树，而且最小生 成树只有一种（类）成树只有一种（类）! 邻接矩阵为：邻接矩阵为： PRIM 算法（横向变化）：算法（横向变化）： VbcdefghUV-UVex lowcosta 4a 3aaaaaab,c,d,e,f,g,hVex 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 Vex lowcost000d 7g 200a,c,b,d ,h ,g f,e Vex lowcost000f 3000a,c,b,d ,h ,g, f e Vex lowcost0000000a,c,b,d ,h ,g, f, e 邻接表为：邻接表为：ab4c3ba4c5d5e9ca3b5d5h5db5c5e7f6g5h4eb9
