数据结构第五章图习题

精品文档5 图【单选题】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-13. 对下图从顶点 a 出发进行深度优先遍历，则（ A）是可能得到的遍历序列。A、 acfgdebB、 abcdefgC、acdgbefD、 abefgcd对下图从顶点a 出发进行广度优先遍历，则（D）是不可能得到的遍历序列。A、 abcdefgB、 acdbfgeC、abdcegfD、 adcbgef0104.设图 G的邻接矩阵A= 101010，则 G中共有 （C）个顶点； 若 G为有向图， 则 G中共有 （D）条弧；若 G为无向图，则G中共有（ B）条边。A、 1B、 2C、 3D、 4E、5F、 9G、以上答案都不对5. 含 n 个顶点的图，最少有（ B）个连通分量，最多有（ D）个连通分量。A、 0B、 1C、 n-1D、 n6.用邻接表存储图所用的空间大小（A）。A、与图的顶点数和边数都有关B、只与图的边数有关C、只与图的顶点数有关D、与边数的平方有关7. n 个顶点的无向图的邻接表最多有（B）个表结点。A、 n2B、 n(n-1)C、 n(n+1)D、 n(n-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,b。1欢迎下载精品文档9. 图的 BFS生成树的树高比 DFS生成树的树高（ A）。A、小或相等B、小C、大或相等D、大10. 下列不正确的是（ C）。(1) 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra ）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2) 利用 Dijkstra求每一对不同顶点之间的最短路径的算法时间是3O(n ) ；（图用邻接矩阵表示）(3)Floyd 求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。A、 (1),(2),(3)B、 (1)C、(1),(3)D、 (2),(3)11. 当各边上的权值（ A）时， BFS算法可用来解决单源最短路径问题。A、均相等B、均互不相等C、不一定相等12.若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（C）。A、对称矩阵B、稀疏矩阵C、三角矩阵D、一般矩阵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、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D、关键活动一定位于关键路径上【填空题】1.设无向连通图 G含 n 个顶点 e 条边，则 G的生成树含个顶点条边。2.连通分量是无向图的子图，生成树是无向连通图的子图。3.对稀疏图而言，在邻接矩阵和邻接表这两种存储结构中选择更为适宜。4.设无向图 G含 n 个顶点 e 条边，则 G的邻接表表示中含个边表结点。5.设有向图 G含 n 个顶点 e 条弧，则 G的邻接表表示中含个边表结点。2欢迎下载精品文档【计算题】1. 设无向图如下，写出对该图从顶点a 出发进行广度优先遍历可能得到的所有遍历序列。解： abcdefg 、 abdcegf 、 acbdfeg 、 acdbfge 、 adbcgef 、 adcbgfe 。2. 设有向图如下，写出对该图从顶点a 出发进行深度优先遍历可能得到的所有遍历序列。解： abedc 、acbed 、acdbe 。3.设无向网如下， (1) 写出其邻接矩阵；(2) 基于该邻接矩阵求深度优先生成树和广度优先生成树；(3)基于该邻接矩阵按普里姆算法求最小生成树；(4) 写出其邻接表； (5) 基于该邻接表按克鲁斯卡尔算法求最小生成树。解：。3欢迎下载精品文档4345593555(1)557654973632526546(2) 深度优先生成树：；广度优先生成树：(3) 最小生成树：；求解过程：(4) 邻接表：(5) 最小生成树：4. 设 AOV图如下，写出对该图进行拓扑排序可能得到的所有拓扑序列。4欢迎下载精品文档解： abcdefg 、 abcdfeg 、 abcfdeg5. 设 AOE网如下，试求关键路径。解：关键路径：v1 v2 v5 v7关键路径： v1 v3 v6v7。6. 设有向网如下，试用迪杰斯特拉算法求从顶点A 出发到其余各顶点的最短路径。解： ab： 3af ： 5afe ： 7abc ： 11afed ： 14。5欢迎下载精品文档7. 设有向网如下，试用弗洛伊德算法求图中各对顶点间的最短路径。解：。6欢迎下载精品文档【算法题】下列算法题中可能用到的类如下：public class MGraphprivate 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;i<maxvn;i+)for(j=0;j<maxvn;j+)adjij=0;vexnum=0;arcnum=0;/构造函数/图的邻接矩阵存储结构类public class ALANodepublic int adj;public ALANode next;/图的邻接表存储结构中的表结点类public class ALVNodepublic Object data; /顶点信息public ALANode firstarc;/图的邻接表存储结构中的头结点类public class ALGraphprivate ALVNode vexs;private int vexnum;private int arcnum;public ALGraph(int maxvn)vexs=new ALVNodemaxvn;vexnum=0;arcnum=0;/构造函数/图的邻接表存储结构类。7欢迎下载精品文档1. 在 ALGraph 类中添加符合如下要求的构造函数 public ALGraph(Object v, ArcArray a)其中 v 为顶点向量， a 为弧向量，类ArcArray的定义如下：public class ArcArrayprivate int index1; /弧尾顶点下标private int index2; /弧头顶点下标(2)public ALGraph(MGraph g)