第7章图自测卷 姓名 班级 题号 四 五 总分 题分 10 得分 、单选题(每题1分,共16分) )1.在一个图中,所有顶点的度数之和等于图的边数的_倍。 B.1 ()2.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的倍 A.12 B.1 ()3.有8个结点的无向图最多有条边。 1.14 C.56 D.112 )4.有8个结点的无向连通图最少有条边。 B.6 ()5.有8个结点的有向完全图有 条边。 D.112 ()6.用邻接表表示图进行广度优先遍历时,通常是采用 来实现算法的。 A.栈 B.队列 C.树 图 ()7.用邻接表表示图进行深度优先遍历时,通常是采用 来实现算法的。 栈 B.队列 C.树 D.图 ()8.已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是 0111101 A.0243156 1000100 B.0136542 l100110 C.0423165 0 D.0361542 0001101 )9.已知图的邻接矩阵同上题8,根据算法,则从顶点0出发,按深度优先遍历的结点序列是 A.0243156 B.0135642C.0423165D.0134256 )10.已知图的邻接矩阵同上题8,根据算法,则从顶点0出发,按广度优先遍历的结点序列是 A.0243651 B.0136425 C.0423156D.0134256 )1.已知图的邻接矩阵同上题8,根据算法,则从顶点0出发,按广度优先遍历的结点序列是 A.0243165B.0135642C.0123465D.0123456
1 第 7 章 图 自测卷 姓名 班级 题号 一 二 三 四 五 总分 题分 16 20 24 10 30 100 得分 一、单选题（每题 1 分，共 16 分） （ ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。 A．1/2 B. 1 C. 2 D. 4 （ ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A．1/2 B. 1 C. 2 D. 4 （ ）3. 有 8 个结点的无向图最多有 条边。 A．14 B. 28 C. 56 D. 112 （ ）4. 有 8 个结点的无向连通图最少有 条边。 A．5 B. 6 C. 7 D. 8 （ ）5. 有 8 个结点的有向完全图有 条边。 A．14 B. 28 C. 56 D. 112 （ ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。 A．栈 B. 队列 C. 树 D. 图 （ ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。 A．栈 B. 队列 C. 树 D. 图 （ ）8. 已知图的邻接矩阵，根据算法思想，则从顶点 0 出发按深度优先遍历的结点序列是 （ ）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 （ ）10. 已知图的邻接矩阵同上题 8，根据算法，则从顶点 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 （ ）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 A．0 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 2 1 1 0 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 0 1
)12.已知图的邻接表如下所示,根据算法,则从顶点0出发按深度优先遍历的结点序列是 2[31门 A.0132 B.0231 2/ C.0321 D.0123 0□00 ()13.已知图的邻接表如下所示,根据算法,则从顶点0出发按广度优先遍历的结点序列是 T[2 A.0321 B.0123 0/ C.0132 D.0312 ()14.深度优先遍历类似于二叉树的 先序遍历 B.中序遍历C.后序遍历D.层次遍历 ()15.广度优先遍历类似于二叉树的 先序遍历B.中序遍历C.后序遍历 层次遍历 ()16.任何一个无向连通图的最小生成树 A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在 填空题(每空1分,共20分) 图有 等存储结构,遍历图有 等方 法 2.有向图G用邻接表矩阵存储,其第i行的所有元素之和等于顶点i的 3.如果n个顶点的图是一个环,则它有 棵生成树。 4.n个顶点e条边的图,若采用邻接矩阵存储,则空间复杂度为 5.n个顶点e条边的图,若采用邻接表存储,则空间复杂度为 6.设有一稀疏图G,则G采用 存储较省空间。 7.设有一稠密图G,则G采用 存储较省空间。 8.图的逆邻接表存储结构只适用于 图 9.已知一个图的邻接矩阵表示,删除所有从第i个顶点出发的方法是 10.图的深度优先遍历序列 惟一的
2 （ ）12. 已知图的邻接表如下所示，根据算法，则从顶点 0 出发按深度优先遍历的结点序列是 （ ）13. 已知图的邻接表如下所示，根据算法，则从顶点 0 出发按广度优先遍历的结点序列是 （ ）14. 深度优先遍历类似于二叉树的 A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 （ ）15. 广度优先遍历类似于二叉树的 A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 （ ）16. 任何一个无向连通图的最小生成树 A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在 二、填空题（每空 1 分，共 20 分） 1. 图有 、 等存储结构，遍历图有 、 等方 法。 2. 有向图 G 用邻接表矩阵存储，其第 i 行的所有元素之和等于顶点 i 的 。 3. 如果 n 个顶点的图是一个环，则它有 棵生成树。 4. n 个顶点 e 条边的图，若采用邻接矩阵存储，则空间复杂度为 。 5. n 个顶点 e 条边的图，若采用邻接表存储，则空间复杂度为 。 6. 设有一稀疏图 G，则 G 采用 存储较省空间。 7. 设有一稠密图 G，则 G 采用 存储较省空间。 8. 图的逆邻接表存储结构只适用于 图。 9. 已知一个图的邻接矩阵表示，删除所有从第 i 个顶点出发的方法是 。 10. 图的深度优先遍历序列 惟一的。 A．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3 A．0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2
1l.n个顶点e条边的图采用邻接矩阵存储,深度优先通历算法的时间复杂度为;若用邻接 表存储时,该算法的时间复杂度为 12.n个顶点e条边的图采用邻接矩阵存储,广度优先遍历算法的时间复杂度为 若采用邻 接表存储,该算法的时间复杂度为 13.图的BFS生成树的树高比DFS生成树的树高 14.用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 ;用克鲁 斯卡尔( Kruskal)算法的时间复杂度是 15.若要求一个稀疏图G的最小生成树,最好用 算法来求解 16.若要求一个稠密图G的最小生成树,最好用 算法来求解 17.用 Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 的次序来得到最短路 径的。 18.拓扑排序算法是通过重复选择具有个前驱顶点的过程来完成的。 三、简答题(每题6分,共24分) 1.【严题集71①】已知如图所示的有向图,请给出该图的 (1)每个顶点的入出度;「顶点12 (2)邻接矩阵; 入度 (3)邻接表; 出度 4)逆邻接表。 2.【严题集77②】请对下图的无向带权图: (1)写出它的邻接矩阵,并按普里姆算法求其最小生成树; (2)写出它的邻接表,并按克鲁斯卡尔算法求其最小生成树
3 11. n 个顶点 e 条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 ；若采用邻接 表存储时，该算法的时间复杂度为 。 12. n 个顶点 e 条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 ；若采用邻 接表存储，该算法的时间复杂度为 。 13. 图的 BFS 生成树的树高比 DFS 生成树的树高 。 14. 用普里姆(Prim)算法求具有 n 个顶点 e 条边的图的最小生成树的时间复杂度为 ；用克鲁 斯卡尔(Kruskal)算法的时间复杂度是 。 15. 若要求一个稀疏图 G 的最小生成树，最好用 算法来求解。 16. 若要求一个稠密图 G 的最小生成树，最好用 算法来求解。 17. 用 Dijkstra 算法求某一顶点到其余各顶点间的最短路径是按路径长度 的次序来得到最短路 径的。 18. 拓扑排序算法是通过重复选择具有 个前驱顶点的过程来完成的。 三、简答题（每题 6 分，共 24 分） 1. 【严题集 7.1①】已知如图所示的有向图，请给出该图的: （1） 每个顶点的入/出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表。 2. 【严题集 7.7②】请对下图的无向带权图： （1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树； （2） 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。 顶点 1 2 3 4 5 6 入度 出度
3.【严题集7②】已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所 得的深度优先生成树和广度优先生成树。 12345678910 10000001010 0001000 40000100010 50000010001 61100000000 70010000 81001000010 90000101001 0100001000 4.【严题集71②】试利用 Di jkstra算法求图中从顶点a到其他各顶点 间的最短路径,写出执行算法过程中各步的状态。 四、给定下列网G:(10分) A)12 B C (E)6 G 1试着找出网G的最小生成树,画出其逻辑结构图; 2用两种不同的表示法画出网G的存储结构图; 3用C语言(或其他算法语言)定义其中一种表示法(存储结构)的数据类型 五、算法设计题(每题10分,共30分) 1.【严题集7.4③】编写算法,由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立 有向图的邻接表。 解: Status Build Adjlist( ALGraph&G)/输入有向图的顶点数边数顶点信息和边的信息,以建立邻接 表
4 3. 【严题集 7.5②】已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点 1 出发进行遍历所 得的深度优先生成树和广度优先生成树。 4. 【严题集 7.11②】试利用 Dijkstra 算法求图中从顶点 a 到其他各顶点 间的最短路径，写出执行算法过程中各步的状态。 四、给定下列网 G: （10 分） 1 试着找出网 G 的最小生成树，画出其逻辑结构图； 2 用两种不同的表示法画出网 G 的存储结构图； 3 用 C 语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。 五、算法设计题（每题 10 分，共 30 分） 1. 【严题集 7.14③】编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立 有向图的邻接表。 解：Status Build_AdjList(ALGraph &G) //输入有向图的顶点数,边数,顶点信息和边的信息，以建立邻接 表
return OK 3//Build AdjList 2.【严题集71】试在邻接矩阵存储结构上实现图的基本操作: Deleteare(G,v,w),即删除一条边的操 作 (如果要删除所有从第i个顶点出发的边呢?提示:将邻接矩阵的第i行全部置0) 解 设本题中的图G为有向无权图 Status deleteare( MGraph&G, char y, char w)∥在邻接矩阵表示的图G上删除边vw } return OK: 1//Delete Are 3.【严题集722】试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存 在由顶点v到项点v的路径(i≠j) 附加题:【严题集7④】采用邻接表存储结构,编写一个判别无向图中任意给定的两个顶点之间是否存 在一条长度为k的简单路径的算法。 (注1:一条路径为简单路径指的是其顶点序列中不含有重现的顶点
5 { return OK; }//Build_AdjList 2. 【严题集 7.15③】试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w)，即删除一条边的操 作。 （如果要删除所有从第 i 个顶点出发的边呢？ 提示： 将邻接矩阵的第 i 行全部置 0 ） 解： //设本题中的图 G 为有向无权图 Status DeleteArc(MGraph &G, char v, char w) //在邻接矩阵表示的图 G 上删除边(v,w) { } return OK; }//Delete_Arc 3. 【严题集 7.22③】试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存 在由顶点 vi 到顶点 vj的路径（i≠j）。 附加题：【严题集 7.27④】采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存 在一条长度为 k 的简单路径的算法。 （注 1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点
注2:此题可參见严题集P207-208中有关按“路径”遍历的算法基本框架。)
6 注 2：此题可参见严题集 P207-208 中有关按“路径”遍历的算法基本框架。）