《数据结构》课程教学资源（试卷习题）第7章 自测空题（无答案）

第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出发按深度优先遮历的结点序列是 0111101 1001001 A.0243156 1000100 B.0136542 1100110 .0423165 1011010 D 0361542 0001101 1100010 )9.已知图的邻接矩阵同上思8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是 A.0243156 B.0135642 C.0423165D.0134256 r )10.已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遗历的结点序列是 A.0243651 B0136425 C0423156D.0134256 )1.己知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是 A.0243165 B.0135642 C.0123465D.0123456 ()12.已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是 132☐3☑ A.0132 B.0231 %032☑ C.0321 D.0123 01☐3☑ 0□2☑

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 （ ）12. 已知图的邻接表如下所示，根据算法，则从顶点 0 出发按深度优先遍历的结点序列是 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 A．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3

( )13.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是 32 A.0321 B.0123 2+ 0/ C.0132 D.0312 33 0/ 2 0/ ）14.深度优先遍历类似于二叉树的 A,先序遍历 B.中序遍历 C.后序遍历D.层次遍历 )15.广度优先遍历类似于二叉树的 A.先序遍历 B.中序遍历 C后序遍历D.层次遍历 )16.任何一个无向连通图的最小生成树 A.只有一棵B.一棵或多棵 C.一定有多棵D.可能不存在 二、填空题（每空1分，共20分） 1.图有 等存储结构，遍历图有」 等方法 有向图G用邻接表矩阵存储， 其第 行的所有元素之和等于顶点i的 3.如果n个项点的图是一个环，则它有 棵生成树 4.n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 5.n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 6.设有一稀疏图G,则G采用 存储较省空间。 ,设有一稠密图G,则G采用 存储较省空间 ,图的逆邻接表存储结构只适用于 9.已知一个图的邻接炬阵表示，删除所有从第1个顶点出发的方法是」 10.图的深度优先遍历序列 惟一的。 m个顶点·条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 ；若采用邻接表存储时 该算法的时间复杂度为 1上.n个顶点©条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 若采用邻接表存储，该 算法的时间复杂度为 13.图的BFS生成树的树高比DFS生成树的树高 14.用普里姆(Pim算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 ;用克鲁斯卡尔 (KruskaI算法的时间复杂度是 15. 若要求 琉图 G的最小生成树，最好用 算法来求解 16.若要求一个稠密图G的最小生成树，最好用 算法来求解。 17.用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 的次序来得到最短路径的。 18.拓扑排序算法是通过重复选择具有个前驱顶点的过程来完成的。 三、简答题（每题6分，共24分） 1.【严题巢7.1①】已知如图所示的有向图，请给出该图的： (1)每个顶点的入/出度： 顶点123456 （2)邻接矩阵： 入度 (3)邻接表： (0 出度 逆邻接表

2 （ ）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. 图的深度优先遍历序列 惟一的。 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） 逆邻接表。 A．0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2 顶点 1 2 3 4 5 6 入度 出度

2.【严题集7.7②】请对下图的无向带权图 (1D 写出它的邻接矩阵，并按普里姆算法求其最小生成树： (2)写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树 9 6 【严题集7.5②】已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先 生成树和「度优先生成树 6 78910 0 0 。 101000010。 4.【严题集7.11②】试利用Dijkstra算法求图中从顶点a到其他各顶点 间的最短路 径，写出执行算法过程中各步的状态。 ⊙ (a 四、给定下列网G:(10分) 20 8 F D 1试着找出网G的最小生成树，画出其逻辑结构图： 2用 同的 画出网G的有 3用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。 3

3 2. 【严题集 7.7②】请对下图的无向带权图： （1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树； （2） 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。 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)I/输入有向图的顶点数，边数，顶点信息和边的信息，以建立邻接表 return OK; }//Build_AdjList 2.【严题集7.15③】试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,V,w),即删除一条边的操作。 (如果要删除所有从第ⅰ个顶点出发的边呢？提示：将邻接矩阵的第1行全部置0) 解： /设本题中的图G为有向无权图 Status DeleteArc(MGraph &G,char v,char w) ∥在邻接矩阵表示的图G上删除边(、，w) } return OK; //Delete Arc 3.【严题集7.22③】试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点到 顶点v的路径(i≠j)。 附加题：【严题集7.27④】采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为 k的简单路径的算法。 (注1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。 注2：此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。) 4

4 五、算法设计题（每题 10 分，共 30 分） 1. 【严题集 7.14③】编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接 表。 解：Status Build_AdjList(ALGraph &G) //输入有向图的顶点数,边数,顶点信息和边的信息，以建立邻接表 { 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 中有关按“路径”遍历的算法基本框架。）