2022年数据结构第五章图习题 .pdf

《2022年数据结构第五章图习题 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构第五章图习题 .pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习资料欢迎下载05图【单选题】1. 设无向图 G 中有五个顶点，各顶点的度分别为2、4、3、1、2，则 G 中边数为（ C） 。、 4 条、 5 条、 6 条、无法确定2. 含 n 个顶点的无向完全图有（D）条边；含n 个顶点的有向图最多有（C）条弧；含n 个顶点的有向强连通图最多有（C）条弧；含n 个顶点的有向强连通图最少有（）条弧；设无向图中有n 个顶点，则要接通全部顶点至少需（G）条边。A、n2B、n(n+1)C、n(n-1)D、n(n-1)/2E、n+1F、nG、n-1 3. 对下图从顶点a 出发进行深度优先遍历，则（A）是可能得到的遍历序列。A、acfgdebB、abcdefgC、

2、acdgbefD、abefgcd 对下图从顶点a 出发进行广度优先遍历，则（D）是不可能得到的遍历序列。A、abcdefgB、acdbfgeC、abdcegfD、adcbgef 4. 设图 G 的邻接矩阵A=010101010，则 G 中共有（ C）个顶点；若G 为有向图，则G 中共有（ D）条弧；若G 为无向图，则G 中共有（ B）条边。A、1B、2C、3D、4E、 5F、9G、以上答案都不对5. 含 n 个顶点的图，最少有（B）个连通分量，最多有（D）个连通分量。A、0B、1C、n-1D、n 6. 用邻接表存储图所用的空间大小（A） 。A、与图的顶点数和边数都有关B、只与图的边数有关C、只

3、与图的顶点数有关D、与边数的平方有关7. n 个顶点的无向图的邻接表最多有（B）个表结点。A、n2B、n(n-1) C、n(n+1) D、n(n-1)/2 8. 无向图G=(V,E)，其中： V=a,b,c,d,e,f ，E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的是（D） 。A、a,b,e,c,d,fB、a,c,f,e,b,dC、a,e,b,c,f,dD、a,e,d,f,c,b 9. 图的 BFS 生成树的树高比DFS 生成树的树高（A） 。精选学习资料 - - - - - - - - - 名师归纳总结

4、- - - - - - -第 1 页，共 9 页学习资料欢迎下载A、小或相等B、小C、大或相等D、大10. 下列不正确的是（C） 。(1)求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra ）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2)利用 Dijkstra 求每一对不同顶点之间的最短路径的算法时间是O(n3)； （图用邻接矩阵表示）(3)Floyd 求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。A、(1),(2),(3)B、(1)C、(1),(3)D、(2),(3) 11. 当各边上的权值（A）时， BFS 算法可用来解决单源最短路径问题。A、均相等

5、B、均互不相等C、不一定相等12. 若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（C） 。A、对称矩阵B、稀疏矩阵C、三角矩阵D、一般矩阵13. 在有向图G 的拓扑序列中，若顶点Vi 在顶点 Vj 之前，则下列情形不可能出现的是（D） 。A、G 中有弧 B、G 中有一条从Vi 到 Vj 的路径C、G 中没有弧 D、 G 中有一条从Vj 到 Vi 的路径14. 关键路径是AOE 网中（ B） 。A、从始点到终点的最短路径B、从始点到终点的最长路径C、人始点到终点的边数最多的路径D、从始点到终点的边数最少的路径15. 下面关于求关键路径的说法不正确的是（C） 。A、求关键路径是以拓扑排序为

6、基础的B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D、关键活动一定位于关键路径上【填空题】1. 设无向连通图G 含 n 个顶点 e 条边，则G 的生成树含个顶点条边。2. 连通分量是无向图的子图，生成树是无向连通图的子图。3. 对稀疏图而言，在邻接矩阵和邻接表这两种存储结构中选择更为适宜。4. 设无向图 G 含 n 个顶点 e条边，则G 的邻接表表示中含个边表结点。5. 设有向图 G 含 n 个顶点 e条弧，则G 的邻接表表示中含个边表结点。精选学习资料 - - - - - - - - -

7、 名师归纳总结 - - - - - - -第 2 页，共 9 页学习资料欢迎下载【计算题】1. 设无向图如下，写出对该图从顶点a 出发进行广度优先遍历可能得到的所有遍历序列。解： abcdefg、abdcegf、acbdfeg、acdbfge、 adbcgef、adcbgfe。2. 设有向图如下，写出对该图从顶点a 出发进行深度优先遍历可能得到的所有遍历序列。解： abedc、acbed、acdbe。3. 设无向网如下，(1)写出其邻接矩阵；(2)基于该邻接矩阵求深度优先生成树和广度优先生成树；(3)基于该邻接矩阵按普里姆算法求最小生成树；(4)写出其邻接表；(5)基于该邻接表按克鲁斯卡尔算法

8、求最小生成树。解：(1) 6456252363794567555553955434精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 9 页学习资料欢迎下载(2)深度优先生成树：；广度优先生成树：(3)最小生成树：；求解过程：(4)邻接表：(5)最小生成树：4. 设 AOV 图如下，写出对该图进行拓扑排序可能得到的所有拓扑序列。解： abcdefg、abcdfeg、abcfdeg 5. 设 AOE 网如下，试求关键路径。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 9 页学习资料欢

9、迎下载解：关键路径：v1v2v5 v7关键路径：v1v3v6v7。6. 设有向网如下，试用迪杰斯特拉算法求从顶点A 出发到其余各顶点的最短路径。解： ab：3af：5afe：7abc：11afed： 14 7. 设有向网如下，试用弗洛伊德算法求图中各对顶点间的最短路径。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 9 页学习资料欢迎下载解：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 9 页学习资料欢迎下载【算法题】下列算法题中可能用到的类如下：public class MG

10、raph private Object vexs; private int adj; private int vexnum; private int arcnum; public MGraph(int maxvn) int i, j; vexs=new Objectmaxvn; adj=new intmaxvnmaxvn; for(i=0;imaxvn;i+) for(j=0;jmaxvn;j+) adjij=0; vexnum=0; arcnum=0; / 构造函数/ 图的邻接矩阵存储结构类public class ALANode public int adj; public ALANode

11、 next; / 图的邻接表存储结构中的表结点类public class ALVNode public Object data; /顶点信息public ALANode firstarc; / 图的邻接表存储结构中的头结点类public class ALGraph private ALVNode vexs; private int vexnum; private int arcnum; public ALGraph(int maxvn) vexs=new ALVNodemaxvn; vexnum=0; arcnum=0; / 构造函数/ 图的邻接表存储结构类1. 在 ALGraph 类中添加符

12、合如下要求的构造函数public ALGraph(Object v, ArcArray a) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 9 页学习资料欢迎下载其中 v 为顶点向量， a 为弧向量，类ArcArray 的定义如下：public class ArcArray private int index1; /弧尾顶点下标private int index2; /弧头顶点下标 (2)public ALGraph(MGraph g) 2. 在 ALGraph 类中添加实现如下功能的方法：(1)在无向图中插入一个顶点；(2)在无向图

13、中删除一个顶点；(3)在无向图中添加一条边；(4)在无向图中删除一条边。(5)判定无向图中是否存在从顶点vi到顶点 vj的路径（ ij） 。(6)输出无向图中从顶点vi到顶点 vj的所有简单路径。解：(5) public boolean path(int i, int j) /从顶点 vi出发进行深度优先遍历，调用完成时所有与vi有路径相通的顶点都被访问到boolean visited =new booleanvexs.length; for(k=0;kvexnum;k+) visitedk=false; dfs(i, visited); return visitedj; /path void

14、 dfs(int i, boolean visited)/从顶点 vi出发对图G 进行深度优先遍历visitedi=true; for(p=vexsi.firstarc;p;p=p.next) if (!visitedp.adj) dfs(p.adj, visited); /dfs 3. 在 MGraph 类中添加符合如下要求的构造函数：(1)public class MGraph(Object v, EdgeArray e) 其中 v 为顶点向量， e 为边向量，类EdgeArray 的定义如下：public class EdgeArray public int index1; /顶点 1 下标public int index2; /顶点 2 下标 (2)public MGraph(ALGraph g) 4. 在 MGraph 类中添加实现如下功能的方法：(1)在有向图中插入一个顶点；(2)在有向图中删除一个顶点；(3)在有向图中添加一条边；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 9 页学习资料欢迎下载(4)在有向图中删除一条边。(5)判定有向图中从顶点vi到顶点 vj是否存在一条长为k 的简单路径。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 9 页