收藏 分销(赏)

数据结构第六章图练习题及答案详细解析(精华版).doc

上传人:精**** 文档编号:2718427 上传时间:2024-06-04 格式:DOC 页数:18 大小:297.54KB
下载 相关 举报
数据结构第六章图练习题及答案详细解析(精华版).doc_第1页
第1页 / 共18页
数据结构第六章图练习题及答案详细解析(精华版).doc_第2页
第2页 / 共18页
数据结构第六章图练习题及答案详细解析(精华版).doc_第3页
第3页 / 共18页
数据结构第六章图练习题及答案详细解析(精华版).doc_第4页
第4页 / 共18页
数据结构第六章图练习题及答案详细解析(精华版).doc_第5页
第5页 / 共18页
点击查看更多>>
资源描述

1、(完整word版)数据结构第六章图练习题及答案详细解析(精华版)图 1. 填空题 设无向图G中顶点数为n,则图G至少有( )条边,至多有( )条边;若G为有向图,则至少有( )条边,至多有( )条边。【解答】0,n(n-1)/2,0,n(n-1)【分析】图的顶点集合是有穷非空的,而边集可以是空集;边数达到最多的图称为完全图,在完全图中,任意两个顶点之间都存在边。 任何连通图的连通分量只有一个,即是( )。【解答】其自身 图的存储结构主要有两种,分别是( )和( )。【解答】邻接矩阵,邻接表【分析】这是最常用的两种存储结构,此外,还有十字链表、邻接多重表、边集数组等。 已知无向图G的顶点数为n,

2、边数为e,其邻接表表示的空间复杂度为( )。【解答】(n+e)【分析】在无向图的邻接表中,顶点表有n个结点,边表有2e个结点,共有n+2e个结点,其空间复杂度为(n+2e)=(n+e)。 已知一个有向图的邻接矩阵表示,计算第j个顶点的入度的方法是( )。【解答】求第j列的所有元素之和 有向图G用邻接矩阵Ann存储,其第i行的所有元素之和等于顶点i的( )。【解答】出度 图的深度优先遍历类似于树的( )遍历,它所用到的数据结构是( );图的广度优先遍历类似于树的( )遍历,它所用到的数据结构是( )。【解答】前序,栈,层序,队列 对于含有n个顶点e条边的连通图,利用Prim算法求最小生成树的时间

3、复杂度为( ),利用Kruskal算法求最小生成树的时间复杂度为( )。【解答】(n2),(elog2e)【分析】Prim算法采用邻接矩阵做存储结构,适合于求稠密图的最小生成树;Kruskal算法采用边集数组做存储结构,适合于求稀疏图的最小生成树。 如果一个有向图不存在( ),则该图的全部顶点可以排列成一个拓扑序列。【解答】回路 在一个有向图中,若存在弧、,则在其拓扑序列中,顶点vi, vj, vk的相对次序为( )。【解答】vi, vj, vk【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。2. 选择题 在一个无向图中,所有顶点的度数之和等于所有边数的( )倍。A 1/2 B 1

4、C 2 D 4【解答】C【分析】设无向图中含有n个顶点e条边,则 。 n个顶点的强连通图至少有()条边,其形状是( )。A n B n+1 C n-1 D n(n-1)E 无回路F 有回路 G 环状 H 树状【解答】A,G 含n 个顶点的连通图中的任意一条简单路径,其长度不可能超过( )。A 1 B n/2 C n-1 D n 【解答】C【分析】若超过n-1,则路径中必存在重复的顶点。 对于一个具有n个顶点的无向图,若采用邻接矩阵存储,则该矩阵的大小是( )。A n B (n-1)2 C n-1 D n2【解答】D 图的生成树(),n个顶点的生成树有( )条边。A 唯一 B 不唯一 C 唯一性

5、不能确定D n E n +1 F n-1【解答】C,F 设无向图G=(V, E)和G =(V, E ),如果G 是G的生成树,则下面的说法中错误的是( )。A G 为 G的子图 B G 为 G的连通分量C G 为G的极小连通子图且V = V D G 是G的一个无环子图【解答】B【分析】连通分量是无向图的极大连通子图,其中极大的含义是将依附于连通分量中顶点的所有边都加上,所以,连通分量中可能存在回路。 G是一个非连通无向图,共有28条边,则该图至少有( )个顶点。A 6 B 7 C 8 D 9 【解答】D【分析】n个顶点的无向图中,边数en(n-1)/2,将e=28代入,有n8,现已知无向图非连

6、通,则n=9。 最小生成树指的是( ) 。A 由连通网所得到的边数最少的生成树B 由连通网所得到的顶点数相对较少的生成树C 连通网中所有生成树中权值之和为最小的生成树D 连通网的极小连通子图【解答】C 判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以用( )。A 求关键路径的方法 B 求最短路径的方法C 广度优先遍历算法 D 深度优先遍历算法【解答】D【分析】当有向图中无回路时,从某顶点出发进行深度优先遍历时,出栈的顺序(退出DFSTraverse算法)即为逆向的拓扑序列。 下面关于工程计划的AOE网的叙述中,不正确的是( )?br / A 关键活动不按期完成就会影响整个工程的完成

7、时间B 任何一个关键活动提前完成,那么整个工程将会提前完成C 所有的关键活动都提前完成,那么整个工程将会提前完成D 某些关键活动若提前完成,那么整个工程将会提前完【解答】B【分析】AOE网中的关键路径可能不止一条,如果某一个关键活动提前完成,还不能提前整个工程,而必须同时提高在几条关键路径上的关键活动。3. 判断题 一个有向图的邻接表和逆邻接表中的结点个数一定相等。【解答】对。邻接表和逆邻接表的区别仅在于出边和入边,边表中的结点个数都等于有向图中边的个数。 用邻接矩阵存储图,所占用的存储空间大小只与图中顶点个数有关,而与图的边数无关。【解答】对。邻接矩阵的空间复杂度为(n2),与边的个数无关。

8、 图G的生成树是该图的一个极小连通子图【解答】错。必须包含全部顶点。 无向图的邻接矩阵一定是对称的,有向图的邻接矩阵一定是不对称的【解答】错。有向图的邻接矩阵不一定对称,例如有向完全图的邻接矩阵就是对称的。 对任意一个图,从某顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点。【解答】错。只有连通图从某顶点出发进行一次遍历,可访问图的所有顶点。 在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧。【解答】错。只能说明从顶点a到顶点b有一条路径。 若一个有向图的邻接矩阵中对角线以下元素均为零,则该图的拓扑序列必定存在。【解答】对。参见第11题的证明。 在AOE网中一定只有一

9、条关键路径?br /【解答】错。AOE网中可能有不止一条关键路径,他们的路径长度相同4n个顶点的无向图,采用邻接表存储,回答下列问题?br / 图中有多少条边? 任意两个顶点i和j是否有边相连? 任意一个顶点的度是多少?br /【解答】 边表中的结点个数之和除以2。 第i个边表中是否含有结点j。 该顶点所对应的边表中所含结点个数。5n个顶点的无向图,采用邻接矩阵存储,回答下列问题: 图中有多少条边? 任意两个顶点i和j是否有边相连? 任意一个顶点的度是多少?【解答】 邻接矩阵中非零元素个数的总和除以2。 当邻接矩阵A中Aij=1(或Aji=1)时,表示两顶点之间有边相连。 计算邻接矩阵上该顶点

10、对应的行上非零元素的个数。6证明:生成树中最长路径的起点和终点的度均为。【解答】用反证法证明。设v1, v2, , vk是生成树的一条最长路径,其中,v1为起点,vk为终点。若vk的度为2,取vk的另一个邻接点v,由于生成树中无回路,所以,v在最长路径上,显然 v1, v2, , vk , v的路径最长,与假设矛盾。所以生成树中最长路径的终点的度为1。同理可证起点v1的度不能大于1,只能为1。7已知一个连通图如图6-6所示,试给出图的邻接矩阵和邻接表存储示意图,若从顶点v1出发对该图进行遍历,分别给出一个按深度优先遍历和广度优先遍历的顶点序列。【解答】邻接矩阵表示如下:深度优先遍历序列为:v1

11、 v2 v3 v5 v4 v6广度优先遍历序列为:v1 v2 v4 v6 v3 v5邻接表表示如下:8图6-7所示是一个无向带权图,请分别按Prim算法和Kruskal算法求最小生成树。【解答】按Prim算法求最小生成树的过程如下:按Kruskal算法求最小生成树的过程如下:9对于图6-8所示的带权有向图,求从源点v1到其他各顶点的最短路径。【解答】从源点v1到其他各顶点的最短路径如下表所示。源点 终点 最短路径 最短路径长度v1 v7 v1 v7 7v1 v5 v1 v5 11v1 v4 v1 v7 v4 13v1 v6 v1 v7 v4 v6 16v1 v2 v1 v7 v2 22v1 v

12、3 v1 v7 v4 v6 v3 2510如图6-9所示的有向网图,利用Dijkstra算法求从顶点v1到其他各顶点的最短路径。【解答】从源点v1到其他各顶点的最短路径如下表所示。源点 终点 最短路径 最短路径长度v1 v3 v1 v3 15v1 v5 v1 v5 15v1 v2 v1 v3 v2 25v1 v6 v1 v3 v2 v6 40v1 v4 v1 v3 v2 v4 4511证明:只要适当地排列顶点的次序,就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。【解答】任意n个结点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v0v1v2vn-1,我们来证明此时的邻接矩阵A为上三角

13、矩阵。证明采用反证法。假设此时的邻接矩阵不是上三角矩阵,那么,存在下标i和j(ij),使得Aij不等于零,即图中存在从vi到vj的一条有向边。由拓扑序 列的定义可知,在任意拓扑序列中,vi的位置一定在vj之前,而在上述拓扑序列v0v1v2vn-1中,由于ij,即vi的位置在vj之后,导 致矛盾。因此命题正确。12. 算法设计 设计算法,将一个无向图的邻接矩阵转换为邻接表。【解答】先设置一个空的邻接表,然后在邻接矩阵上查找值不为零的元素,找到后在邻接表的对应单链表中插入相应的边表结点。邻接矩阵存储结构定义如下:const int MaxSize=10;template struct AdjMat

14、rix T vertexMaxSize; /存放图中顶点的数组int arcMaxSizeMaxSize; /存放图中边的数组int vertexNum, arcNum; /图的顶点数和边数;邻接表存储结构定义如下:const int MaxSize=10;struct ArcNode /定义边表结点int adjvex; /邻接点域ArcNode *next;template struct VertexNode /定义顶点表结点T vertex;ArcNode *firstedge;struct AdjListVertexNode adjlistMaxSize;int vertexNum,

15、arcNum; /图的顶点数和边数;具体算法如下: 设计算法,将一个无向图的邻接表转换成邻接矩阵。【解答】在邻接表上顺序地取每个边表中的结点,将邻接矩阵中对应单元的值置为1。邻接矩阵和邻接表的存储结构定义与上题相同。具体算法如下: 设计算法,计算图中出度为零的顶点个数。【解答】在有向图的邻接矩阵中,一行对应一个顶点,每行的非零元素的个数等于对应顶点的出度。因此,当某行非零元素的个数为零时,则对应顶点的出度为零。据此,从第一行开始,查找每行的非零元素个数是否为零,若是则计数器加1。具体算法如下: 以邻接表作存储结构,设计按深度优先遍历图的非递归算法。【解答】参见6.2.1。 已知一个有向图的邻接

16、表,编写算法建立其逆邻接表。【解答】在有向图中,若邻接表中顶点vi有邻接点vj,在逆邻接表中vj一定有邻接点vi,由此得到本题算法思路:首先将逆邻接表的表头结点firstedge域置空,然后逐行将表头结点的邻接点进行转化。 分别基于深度优先搜索和广度优先搜索编写算法,判断以邻接表存储的有向图中是否存在由顶点vi到顶点vj的路径(ij)。【解答】 基于深度优先遍历: 基于广度优先遍历:学习自测及答案 1某无向图的邻接矩阵A=,可以看出,该图共有( )个顶点。A 3 B 6 C 9 D 以上答案均不正确【解答】A2无向图的邻接矩阵是一个( ),有向图的邻接矩阵是一个( )A 上三角矩阵 B 下三角

17、矩阵 C 对称矩阵 D 无规律【解答】C,D3下列命题正确的是( )。A 一个图的邻接矩阵表示是唯一的,邻接表表示也唯一B 一个图的邻接矩阵表示是唯一的,邻接表表示不唯一C 一个图的邻接矩阵表示不唯一的,邻接表表示是唯一D 一个图的邻接矩阵表示不唯一的,邻接表表示也不唯一【解答】B4十字链表适合存储( ),邻接多重表适合存储( )。【解答】有向图,无向图5. 在一个具有n 个顶点的有向完全图中包含有( )条边:A n(n-1)/2 B n(n-1) C n(n+1)/2 D n2【解答】B6n个顶点的连通图用邻接矩阵表示时,该矩阵至少有( )个非零元素。【解答】2(n-1)7表示一个有100个

18、顶点,1000条边的有向图的邻接矩阵有( )个非零矩阵元素。【解答】10008一个具有n个顶点k条边的无向图是一个森林(nk),则该森林中必有( )棵树。A k B n C n - k D 1【解答】C9用深度优先遍历方法遍历一个有向无环图,并在深度优先遍历算法中按退栈次序打印出相应的顶点,则输出的顶点序列是( )。A 逆拓扑有序 B 拓扑有序 C 无序 D 深度优先遍历序列【解答】A10. 关键路径是AOE网中( )。A 从源点到终点的最长路径 B从源点到终点的最长路径C 最长的回路 D 最短的回路【解答】A11. 已知无向图G的邻接表如图6-10所示,分别写出从顶点1出发的深度遍历和广度遍历序列,并画出相应的生成树。【解答】深度优先遍历序列为:1,2,3,4,5,6对应的生成树为:广度优先遍历序列为:1,2,4,3,5,6对应的生成树为:12. 已知已个AOV网如图6-11所示,写出所有拓扑序列。【解答】拓扑序列为:v0 v1 v5 v2 v3 v6 v4、 v0 v1 v5 v2 v6 v3 v4、 v0 v1 v5 v6 v2 v3 v4。

展开阅读全文
部分上传会员的收益排行 01、路***(¥15400+),02、曲****(¥15300+),
03、wei****016(¥13200+),04、大***流(¥12600+),
05、Fis****915(¥4200+),06、h****i(¥4100+),
07、Q**(¥3400+),08、自******点(¥2400+),
09、h*****x(¥1400+),10、c****e(¥1100+),
11、be*****ha(¥800+),12、13********8(¥800+)。
相似文档                                   自信AI助手自信AI助手
搜索标签

当前位置:首页 > 教育专区 > 其他

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        获赠5币

©2010-2024 宁波自信网络信息技术有限公司  版权所有

客服电话:4008-655-100  投诉/维权电话:4009-655-100

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :gzh.png    weibo.png    LOFTER.png 

客服