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

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 、nn+1c、nn-1d、nn-1/2e、n+1f、ng、n-13. 对下图从顶点 a 动身进行深度优先遍历，就（a ）是可能得到的遍历序列；a 、acfgdebb 、abcde

2、fgc、acdgbefd、abefgcd对下图从顶点 a 动身进行广度优先遍历，就（d ）是不行能得到的遍历序列；a 、abcdefgb 、acdbfgec、abdcegfd、adcbgef014. 设图 g 的邻接矩阵 a=100101，就 g 中共有（ c）个顶点；如 g 为有向图，就 g 中共有（ d ）0条弧；如 g 为无向图，就g 中共有（ b ）条边；a 、1b 、2c、3d、4e、 5f、9g、以上答案都不对5. 含 n 个顶点的图，最少有（ b ）个连通重量，最多有（d）个连通重量；a 、0b 、1c、n-1d、n6. 用邻接表储备图所用的空间大小（a ）；a 、与图的顶点数和

3、边数都有关b 、只与图的边数有关c、只与图的顶点数有关d 、与边数的平方有关7. n 个顶点的无向图的邻接表最多有（b ）个表结点；2a 、nb 、nn-1c、nn+1d 、nn-1/28. 无向图 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,b9. 图的 bfs 生成树的树高比 dfs 生成树的树高（ a ）；a 、小或相等b 、小c、大或相等d、大10. 以下不正

4、确选项（c）；(1) 求从指定源点到其余各顶点的迪杰斯特拉（dijkstra ）最短路径算法中弧上权不能为负的缘由是在实际应用中无意义；(2) 利用 dijkstra 求每一对不同顶点之间的最短路径的算法时间是on 3；（图用邻接矩阵表示）(3) floyd 求每对不同顶点对的算法中答应弧上的权为负，但不能有权和为负的回路；a 、1,2,3b 、1c、1,3d 、2,311. 当各边上的权值（a ）时， bfs 算法可用来解决单源最短路径问题；a 、均相等b、均互不相等c、不肯定相等12. 如一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（c）； a 、对称矩阵b 、稀疏矩阵c、三角矩阵d

5、、一般矩阵13. 在有向图 g 的拓扑序列中，如顶点vi 在顶点 vj 之前，就以下情形不行能显现的是（d）； a 、g 中有弧 <vi,vj>b、g 中有一条从 vi 到 vj 的路径c、g 中没有弧 <vi,vj>d、 g 中有一条从 vj 到 vi 的路径14. 关键路径是 aoe 网中（ b ）；a 、从始点到终点的最短路径b、从始点到终点的最长路径c、人始点到终点的边数最多的路径d、从始点到终点的边数最少的路径15. 下面关于求关键路径的说法不正确选项（c）； a 、求关键路径是以拓扑排序为基础的b 、一个大事的最早开头时间同以该大事为尾的弧的活动最早开头时间

6、相同c、一个大事的最迟开头时间为以该大事为尾的弧的活动最迟开头时间与该活动的连续时间的差d 、关键活动肯定位于关键路径上【填空题】1. 设无向连通图 g 含 n 个顶点 e 条边，就 g 的生成树含个顶点条边；2. 连通重量是无向图的子图，生成树是无向连通图的子图；3. 对稀疏图而言，在邻接矩阵和邻接表这两种储备结构中挑选更为相宜；4. 设无向图 g 含 n 个顶点 e 条边，就 g 的邻接表表示中含个边表结点；5. 设有向图 g 含 n 个顶点 e 条弧，就 g 的邻接表表示中含个边表结点；【运算题】1. 设无向图如下，写出对该图从顶点a 动身进行广度优先遍历可能得到的全部遍历序列；解： a

7、bcdefg、abdcegf、acbdfeg、acdbfge、 adbcgef、adcbgfe；2. 设有向图如下，写出对该图从顶点a 动身进行深度优先遍历可能得到的全部遍历序列；解： abedc、acbed、acdbe；3. 设无向网如下， 1写出其邻接矩阵； 2 基于该邻接矩阵求深度优先生成树和广度优先生成树；3 基于该邻接矩阵按普里姆算法求最小生成树；4写出其邻接表；5 基于该邻接表按克鲁斯卡尔算法求最小生成树；解：43143559555557654973632526546(2) 深度优先生成树：；广度优先生成树：(3) 最小生成树：；求解过程：(4) 邻接表：(5) 最小生成树：4.

8、设 aov 图如下，写出对该图进行拓扑排序可能得到的全部拓扑序列；解： abcdefg、abcdfeg、abcfdeg5. 设 aoe 网如下，试求关键路径；解：关键路径： v1v 2 v 5 v7关键路径： v1 v3 v6 v7；6. 设有向网如下，试用迪杰斯特拉算法求从顶点a 动身到其余各顶点的最短路径；解： ab： 3af ：5afe： 7abc： 11afed： 147. 设有向网如下，试用弗洛伊德算法求图中各对顶点间的最短路径；解：学习资料欢迎下载【算法题】以下算法题中可能用到的类如下：public class mgraph private object vexs; private

9、 int adj; private int vexnum; private int arcnum;public mgraphint maxvn int i, j;vexs=new objectmaxvn;adj=new intmaxvnmaxvn; fori=0;i<maxvn;i+forj=0;j<maxvn;j+adjij=0; vexnum=0; arcnum=0;/ 构造函数/ 图的邻接矩阵储备结构类public class alanode public int adj;public alanode next;/ 图的邻接表储备结构中的表结点类public class al

10、vnodepublic object data;/ 顶点信息public alanode firstarc;/ 图的邻接表储备结构中的头结点类public class algraph private alvnode vexs; private int vexnum; private int arcnum;public algraphint maxvn vexs=new alvnodemaxvn; vexnum=0;arcnum=0;/ 构造函数/ 图的邻接表储备结构类1. 在 algraph 类中添加符合如下要求的构造函数 public algraphobject v, arcarray a其

11、中 v 为顶点向量， a 为弧向量，类 arcarray的定义如下：public class arcarrayprivate int index1;/弧尾顶点下标private int index2;/弧头顶点下标2public algraphmgraph g2. 在 algraph 类中添加实现如下功能的方法：(1) 在无向图中插入一个顶点；(2) 在无向图中删除一个顶点；(3) 在无向图中添加一条边；(4) 在无向图中删除一条边；(5) 判定无向图中是否存在从顶点vi 到顶点 vj 的路径（ i j ）；(6) 输出无向图中从顶点vi 到顶点 vj 的全部简洁路径；解：5public bo

12、olean pathint i, int j/ 从顶点 vi 动身进行深度优先遍历，调用完成时全部与vi 有路径相通的顶点都被拜访到boolean visited =new booleanvexs.length; fork=0;k<vexnum;k+ visitedk=false; dfsi, visited;return visitedj;/pathvoid dfsint i, boolean visited/从顶点 vi 动身对图 g 进行深度优先遍历visitedi=true; forp=vexsi.firstarc;p;p=p.nextif .visitedp.adj dfsp.adj, visited;/dfs3. 在 mgraph 类中添加符合如下要求的构造函数：(1) public class mgraphobject v, edgearray e其中 v 为顶点向量， e 为边向量，类 edgearray 的定义如下：public class edgearraypublic int