2022年《数据结构》习题集：图 .pdf

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

1、数据结构课后练习题第 7 章 图1/8 北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1 第 7 章 图一、选择题1.一个有 n 个顶点的无向图最多有（）条边。A、 n B、n(n-1) C、n(n-1)/2 D、2n 2.具有 6 个顶点的无向图至少有（）条边才能保证是一个连通图。A、 5 B、6 C、7 D、8 3.具有 n 个顶点且每一对不同的顶点之间都有一条边的图被称为（）。A、线性图B、无向完全图C、无向图D、简单图4.具有 4个顶点的无向完全图有（）条边。A、 6 B、12 C、16 D、20 5.G是一个非连通无向图，共有28 条边，则该图至少有（）个顶点。A

2、、 6 B、7 C、8 D、9 6.存储稀疏图的数据结构常用的是（）。A、邻接矩阵B、三元组C、邻接表D、十字链表7.对一个具有 n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（）。A、 n B、(n-1)2C、(n+1)2D、n28.设连通图 G的顶点数为 n，则 G 的生成树的边数为（）。A、 n-1 B、n C、2n D、2n-1 9.对于一个具有N个顶点和 E条边的无向图，若采用邻接表表示，则表头向量的大小为（1） ）；所有邻接表中的结点总数是（ 2） ）。（1）A、N B、N+1 C、N-1 D、N+E （2）A、E/2 B、E C、2E D、N+E 10.对于一个具有n个顶点和 e

3、条边的无向图，若采用邻接表表示，则表向量的大小为（），所有顶点邻接表的结点总数为（）。A、 n B、n+1 C、n-1 D、2n E、e/2 F、e G、2e H、n+e 11.在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（）。A、顶点 v 的度B、顶点 v 的出度C、顶点 v 的入度D、依附于顶点v 的边数12.已知一个图， 若从顶点 a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（）和（）（1） A 、abecdf B、acfebd C、acebfd D、acfdeb （2） A 、abcedf B、abcefd C、abedfc D、acfdeb abecdf1

4、3.采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（）和（）。A、中序遍历B、先序遍历C、后序遍历D、层次遍历14.已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1 出发，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 数据结构课后练习题第 7 章 图2/8 北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1 得到的顶点序列分别为（）和（）。A、 v1,v

5、2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v3,v4,v5,v2 D、v1,v4,v3,v5,v2 V10V21V32V43213V544V13V3VVV15.已知有 8 个顶点为A，B，C， D，E，F，G， H 的无向图，其邻接矩阵存储结构如下，由此结构，从A 点开始深度遍历，得到的顶点序列为（）。ABCDEFGHA01010000B10101110C01010000D10100010E01000001F01000011G01010101H00001110A、 ABCDGHFE B、ABCDGFHE C、ABGHFECD D、ABFHEGDC E、 ABEHFGDC

6、 F、ABEHGFCD 16.已知一个图如下，在该图的最小生成树中各边上权值之和为（），在该图的最小生成树中，从v1 到 v6的路径为（）。A、31 B、38 C、36 D、43 E、 v1,v3,v6 F、v1,v4,v6 G、v1,v5,v4,v6 H、v1,v4,v3,v6 v1v2v4v6v3v5586481012209选择题 1617.关键路径是事件结点网络中的（）。A、从源点到汇点的最长路径B、从源点到汇点的最短路径C、最长的回路D、最短的回路18.正确的 AOE网必须是（）， AOE网中某边权值应当是（）。（1） A、完全图B、哈密尔顿图C、无环图D、强连通图（2） A、实数B、

7、正整数C、正数D、非负数19.已知一个图如下，则由该图得到的一种拓扑序列为（）。A、v1,v4,v6,v2,v5,v3 B、v1,v2,v3,v4,v5,v6 C、v1,v4,v2,v3,v6,v5 D、v1,v2,v4,v6,v3,v5 20.下面结论中正确的是（）。A、在无向图中，边的条数是顶点度数之和。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 数据结构课后练习题第 7 章 图3/8 北京理工大学珠海学院计算机学院“数

8、据结构”课程组编制2011-3-1 B、在图结构中，顶点可以没有任何前驱和后继。C、在 n 个顶点的无向图中，若边数大于n-1，则该图必定是连通图D、图的邻接矩阵必定是对称矩阵。21.下面结论中正确的是（）。A、若有向图的邻接矩阵中对角线以下元素均为0，则该图的拓扑排序序列必定存在。B、网络的最小代价生成树是唯一的。C、在拓扑排序序列中，任意两个相继顶点vi 和 vj 都存在从vi 到 vj 的路径。D、在有向图中，从一个顶点到另一个顶点的最短路径是唯一的。22.下面结论不正确的是（）。A、无向图的连通分量是该图的极大连通子图。B、有向图用邻接矩阵表示容易实现求顶点度数的操作。C、无向图用邻接

9、矩阵表示，图中的边数等于邻接矩阵元素之和的一半。D、有向图的邻接矩阵必定不是对称矩阵。23.下面结论中正确的是（）。A、按深度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。B、一个图按深度优先搜索遍历的结果是唯一的。C、若有向图G 中包含一个环，则G 的顶点间不存在拓扑排序。D、图的拓扑排序序列是唯一的。24.下面结论中不正确的是（）。A、按广度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。B、一个图按广度优先搜索遍历的结果是唯一的。C、无向图的邻接表表示法中，表中结点的数目是图中边的条数的2 倍。D、图的多重邻接表表示法中，表中结点数目是图中边的条数。25.在

10、一个图中，所有顶点的度数之和等于所有边数的（）倍。A、1/2 B、1 C、2 D、4 26.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A、1/2 B、1 C、2 D、4 27.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）。A、求关键路径的方法B、求最短路径的DIJKSTRA 方法C、广度优先遍历算法D、深度优先遍历算法28.任何一个带权的无向连通图的最小生成树（）。A、只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在29.以下说法正确的是（）。A、连通图的生成树，是该连通图的一个极小连通子图。B、无向图的邻接矩阵是对称的，有向图的邻接矩阵一定

11、是不对称的。C、任何一个有向图，其全部顶点可以排成一个拓扑序列。D、有回路的图不能进行拓扑排序。30.以下说法错误的是（）。A、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。B、邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。C、存储无向图的邻接矩阵是对称的，因此也可以只要存储邻接矩阵的下（或上）三角部分。D、用邻接矩阵A 表示图，判定任意两个结点Vi和 Vj之间是否有长度为m 的路径相连，则只要检查Am的第 i 行第 j 列的元素是否为0 即可。31.以下说法正确的是（）。名师资料总结 - - -精品

12、资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - 数据结构课后练习题第 7 章 图4/8 北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1 A、连通分量是无向图中的极小连通子图。B、强连通分量是有向图中的极大强连通子图。C、在一个有向图的拓扑序列中，若顶点a 在顶点 b 之前，则图中必有一条弧。D、对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。二、判断题1.用邻接矩阵法存储一个图时，所占

13、用的存储空间大小仅与图中结点个数有关。2.对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。3.任何有向网拓扑排序的结果是唯一的。4.有回路的图不能进行拓扑排序。5.存储有向图的邻接矩阵是对称的。6.一个有向图G 中若有弧 、和, 则在图 G 的拓扑序列中，顶点vi,vj和 vk的相对位置为vi,vj,vk。7.在 AOE网中一定有一条关键路径。8.含有 10 个顶点的无向连通图其生成树含有9 条边。9.十字链表是图的一种顺序表示法。三、填空题1.对具有 n 个顶点的图，其生成树有且仅有（）条边，即生成树是图的边数（）的连通图。2.一个无向图有n 个顶点和

14、 e 条边，则所有顶点的度数之和为（），其邻接矩阵是一个关于（）对称的矩阵。3.在图形结构中，每个结点的前驱结点和后继结点可以有（）。4.设无向图G 的顶点数为n，图 G 最少有（）边，最多有（）条边。若G 为有向图，有n 个顶点，则图 G 最少有（）条边，最多有（）条边。具有n 个顶点的无向完全图，边的总数为（）条，而有 n 个顶点的有向完全图，边的总数为（）条。5.在无权图G 的邻接矩阵A 中，若 (vi,vj)或属于 G 的边 /弧的集合，则对应元素Aij 等于（），否则等于（）。6.在无向图G 的邻接矩阵A 中，若 Aij=1，则 Aji 等于（）。7.已知一个图的邻接矩阵表示，计算第

15、I 个顶点的入度方法为（）。8.在一个图G 的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的（），而对于无向图而言等于该顶点的（）。9.已知图 G 的邻接表如图7.4 所示，其从顶点V1 出发的深度优先搜索序列为（），其从顶点V1 出发的广度优先搜索序列为（）。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - 数据结构课后练习题第 7 章 图5/8 北京理工大学珠海学院计算机学院“数据结构”课程组编制20

16、11-3-1 10.n 个顶点的弱连通有向图G 最多有（）条弧，最少有（）条弧。11.在 n 个顶点 e 条边的连通图中，连通分量个数为（）。12.任何（）的有向图， 其所有结点都可以排在一个拓扑序列中，拓扑排序的方法是先从图中选一个（）为 0 的结点且输出，然后从图中删除该结点及其（），反复执行，直到所有结点都输出为止。13.一个连通图的（）是一个极小连通子图。14.在 AOE网中，从源点到汇点各活动时间总和最长的路径为（）。15.在有向图的邻接矩阵上，由第i 行可得到第（）个结点的出度，而由第j 列可得到第（）个结点的入度。16.对无向图，设有n 个结点， e 条边，则其邻接表表示中需要（

17、）个表结点，对有向图，设有n 个顶点， e条弧，则其邻接表表示需要（）个表结点。17.在无权图G 的邻接矩阵A 中，若(Vi,Vj)或属于图G 的边集 ,则对应元素Ai,j等于（），否则等于（）。18.已知一个有向图的邻接矩阵表示，计算第i 个结点的入度的方法是（）。删除所有从第i 个结点出发的边的方法是（）。19.设无向图G 中顶点数为n，则图 G 最少有（）条边，最多有 （）条边。若 G 为有向图， 有 n 个顶点，则图至少有（）条边，最多有（）条边。20.某作业工程表示成网络图，如图 7.5 所示。事件 5 的最早完成时间是 （） 。 事件 4 的最迟开始时间是 （） 。事件 5 的迟缓

18、时间是（）。关键路径是（）。21.设 x,yV，若E,则表示有向图G 中从 x 到 y 的一条（），x 称为（）点，y 称为（）点。若（ x,y） E，则在无向图G中 x 和 y 间有一条（）。22.在无向图中， 如果从顶点v 到顶点 v有路径， 则称 v 和 v是（）的。如果对于图中的任意两个顶点vi,vjV，且 vi 和 vj 都是连通的，则称G 为（）。23.连通分量是无向图中的（）连通子图。24.对无向图，若它有n 个顶点 e 条边，则其邻接表中需要（）个结点。其中， （）个结点构成头结点，（）个结点构成边结点表。25.对有向图，若它有n 顶点 e 条边，则其邻接表中需要（）个结点。其

19、中，（）个结点构成头结点，（）个结点构成边结点表。26.在邻接表上，无向图中顶点vi 的度恰为（）。对有向图，顶点vi 的出度是（）。为了求入度，必须遍历整个邻接表，在所有单链表中，其邻接点域的值为（）的结点的个数是顶点vi 的入度。27.遍历图的基本方法有（）优先搜索和（）优先搜索两种。四、简答题1.对于一个具有n 个顶点的连通无向图，如果它有且只有一个简单回路，此图有几条边？一个具有n 个顶点的弱名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - -

20、- - - - - 数据结构课后练习题第 7 章 图6/8 北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1 连通图至少有几条边？2.已知某图的邻接表，如何建立该图的邻接矩阵？3.简述无向图和有向图有哪几种存储结构，并说明各种结构在图的不同操作中有什么优越性？什么是AOE网的关键路径？五、补充应用题1.给出无向图如图7.6 所示的 G1 的邻接矩阵和邻接表。图 7.6 2.分别给出图7.6 所示的 G2 的邻接矩阵、邻接表和逆邻接表。3.分别给出图7.6 所示的 G3从 v5出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。4.求出图 7.7 的连通分量。5.设有一无

21、向图G=(V,E),其中V=1,2,3,4,5,6,E=(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5) 。1)按上述顺序输入后，画出其相应的邻接表；2)在该邻接表上，从顶点4 开始，写出DFS序列和 BFS序列。6.已知连通网的邻接矩阵如图7.8所示，顶点集合为 v1,v2,v3,v4,v5， 试画出它所表示的从顶点v1开始利用Prim 算法得到的最小生成树。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

22、 第 6 页，共 8 页 - - - - - - - - - 数据结构课后练习题第 7 章 图7/8 北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1 7.拓扑排序的结果不是唯一的，对图7.9 进行拓扑排序，写出全部不同的拓扑排序序列。8.已知图 G 的邻接表如图7.10 所示，顶点V1为出发点，完成要求：（1） 深度优先搜索的顶点序列；（2） 广度优先搜索的顶点序列；（3） 由深度优先搜索得到的一棵生成树；（4） 由广度优先搜索得到的一棵生成树。9.图 7.11 所示为一无向连通网络，要求根据Prim 算法和 Kruskal 构造出它的最小生成树。10.在下图所示的有向图

23、7.12 中：（1）该图是强连通图吗？（2）请给出每个顶点的度、入度和出度。（3）给出其邻接矩阵、邻接表及逆邻接表。11.DFS和 BFS遍历采用什么样的数据结构来暂存顶点？当要求连通图的生成树的高度最小，应采用何种遍历？画出以顶点v1 为初始源点遍历图7.13 所示的有向图所得到的DFS和 BFS生成森林。12.对图7.14 所示的有向网，试利用Dijkstra 算法求从源点1 到其他各顶点的最短路径。13.已知如图7.16 所示的 AOE网。求：（1）每项活动的最早开始时间和最晚开始时间；（2）完成此工程最少需要多少单位时间；（3）关键活动与关键路径。14.已知带权连通图，G（V,E）的邻

24、接表如图7.17 所示。试画出该图，并分别从顶点1 开始的深度优先和广度优名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 数据结构课后练习题第 7 章 图8/8 北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1 先遍历之，给出遍历中结点的序列，最后画出该图的一棵最小生成树。其中表结点的三个域为：15.已知某图G 的邻接矩阵为101101001011010，顶点集合为 v1,v2,v3,v4 1)由邻接矩阵画出相应的图G；2)如果要使此图成为完全图还要增加哪几条边。16.对于图 7.19 所示的 AOE网络，计算各事件（顶点）的ve(vi)和 vl(vj)和活动（边）的e(ai)和 l(ai)函数值；列出各条关键路径和关键活动。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -