数据结构习题集第章图.doc

《数据结构习题集第章图.doc》由会员分享，可在线阅读，更多相关《数据结构习题集第章图.doc（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构课后练习题 第7章 图第7章 图一、 选择题1. 一个有n 个顶点的无向图最多有（ ）条边。A、n B、n(n-1) C、n(n-1)/2 D、2n2. 具有6 个顶点的无向图至少有（ ）条边才能保证是一个连通图。A、5 B、6 C、7 D、83. 具有n 个顶点且每一对不同的顶点之间都有一条边的图被称为（ ）。A、线性图 B、无向完全图 C、无向图 D、简单图4. 具有4个顶点的无向完全图有（ ）条边。A、6 B、12 C、16 D、205. G是一个非连通无向图，共有28 条边，则该图至少有（ ）个顶点。A、6 B、7 C、8 D、96. 存储稀疏图的数据结构常用的是（ ）。A、邻

2、接矩阵 B、三元组 C、邻接表 D、十字链表7. 对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（ ）。A、n B、(n-1)2 C、(n+1)2 D、n28. 设连通图G的顶点数为n，则G 的生成树的边数为（ ）。A、n-1 B、n C、2n D、2n-19. 对于一个具有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+E10. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为（ ），所有顶点邻接表

3、的结点总数为（ ）。A、n B、n+1 C、n-1 D、2n E、e/2 F、e G、2e H、n+e11. 在有向图的邻接表存储结构中，顶点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、acfdeb13. 采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（ ）和（ ）。A

4、、中序遍历 B、先序遍历 C、后序遍历 D、层次遍历14. 已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（ ）和（ ）。A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v3,v4,v5,v2 D、v1,v4,v3,v5,v215. 已知有8个顶点为A，B，C，D，E，F，G，H的无向图，其邻接矩阵存储结构如下，由此结构，从A点开始深度遍历，得到的顶点序列为（ ）。A、ABCDGHFE B、ABCDGFHE C、ABGHFECD D、ABFHEGDCE、ABEHFGDC F、ABEHGFCD16

5、. 已知一个图如下，在该图的最小生成树中各边上权值之和为（ ），在该图的最小生成树中，从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,v617. 关键路径是事件结点网络中的（ ）。A、从源点到汇点的最长路径 B、从源点到汇点的最短路径 C、最长的回路 D、最短的回路18. 正确的AOE网必须是（ ），AOE网中某边权值应当是（ ）。（1）A、完全图 B、哈密尔顿图 C、无环图 D、强连通图（2）A、实数 B、正整数 C、正数 D、非负数19. 已知一个图如下，则由该图得到的一种拓扑

6、序列为（ ）。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,v520. 下面结论中正确的是（ ）。A、在无向图中，边的条数是顶点度数之和。 B、在图结构中，顶点可以没有任何前驱和后继。 C、在n 个顶点的无向图中，若边数大于n-1，则该图必定是连通图 D、图的邻接矩阵必定是对称矩阵。21. 下面结论中正确的是（ ）。A、若有向图的邻接矩阵中对角线以下元素均为0，则该图的拓扑排序序列必定存在。 B、网络的最小代价生成树是唯一的。 C、在拓扑排序序列中，任意两个相继顶点vi 和vj 都存在从

7、vi 到vj 的路径。 D、在有向图中，从一个顶点到另一个顶点的最短路径是唯一的。22. 下面结论不正确的是（ ）。A、无向图的连通分量是该图的极大连通子图。 B、有向图用邻接矩阵表示容易实现求顶点度数的操作。 C、无向图用邻接矩阵表示，图中的边数等于邻接矩阵元素之和的一半。 D、有向图的邻接矩阵必定不是对称矩阵。23. 下面结论中正确的是（ ）。A、按深度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。 B、一个图按深度优先搜索遍历的结果是唯一的。 C、若有向图G中包含一个环，则G的顶点间不存在拓扑排序。 D、图的拓扑排序序列是唯一的。24. 下面结论中不正确的是（ ）。A、按

8、广度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。 B、一个图按广度优先搜索遍历的结果是唯一的。 C、无向图的邻接表表示法中，表中结点的数目是图中边的条数的2倍。D、图的多重邻接表表示法中，表中结点数目是图中边的条数。25. 在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。A、1/2 B、1 C、2 D、426. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。A、1/2 B、1 C、2 D、427. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（ ）。A、求关键路径的方法 B、求最短路径的DIJKSTRA 方法C、广度优先遍历算法

9、 D、深度优先遍历算法28. 任何一个带权的无向连通图的最小生成树（ ）。A、只有一棵 B、有一棵或多棵 C、一定有多棵 D、可能不存在29. 以下说法正确的是（ ）。A、连通图的生成树，是该连通图的一个极小连通子图。B、无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。C、任何一个有向图，其全部顶点可以排成一个拓扑序列。D、有回路的图不能进行拓扑排序。30. 以下说法错误的是（ ）。A、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。B、邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。C、存储无

10、向图的邻接矩阵是对称的，因此也可以只要存储邻接矩阵的下（或上）三角部分。D、用邻接矩阵A 表示图，判定任意两个结点Vi 和Vj 之间是否有长度为m 的路径相连，则只要检查Am的第i行第j列的元素是否为0 即可。31. 以下说法正确的是（ ）。A、连通分量是无向图中的极小连通子图。B、强连通分量是有向图中的极大强连通子图。C、在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。D、对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。二、 判断题1. 用邻接矩阵法存储一个图时，所占用的存储空间大小仅与图中结点个数有关。2. 对任意一个图，

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

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

13、顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的（ ），而对于无向图而言等于该顶点的（ ）。9. 已知图G的邻接表如图7.4所示，其从顶点V1出发的深度优先搜索序列为（ ），其从顶点V1出发的广度优先搜索序列为（ ）。10. n个顶点的弱连通有向图G最多有（ ）条弧，最少有（ ）条弧。11. 在n个顶点e条边的连通图中，连通分量个数为（ ）。12. 任何（ ）的有向图，其所有结点都可以排在一个拓扑序列中，拓扑排序的方法是先从图中选一个（ ）为0的结点且输出，然后从图中删除该结点及其（ ），反复执行，直到所有结点都输出为止。13. 一个连通图的（ ）是一个极小连通子图。14. 在AOE网中

14、，从源点到汇点各活动时间总和最长的路径为（ ）。15. 在有向图的邻接矩阵上，由第i行可得到第（ ）个结点的出度，而由第j列可得到第（ ）个结点的入度。16. 对无向图，设有n个结点，e条边，则其邻接表表示中需要（ ）个表结点，对有向图，设有n个顶点，e条弧，则其邻接表表示需要（ ）个表结点。17. 在无权图G的邻接矩阵A中，若 (Vi,Vj)或属于图G的边集,则对应元素Ai,j等于（ ），否则等于（ ）。18. 已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是（ ）。删除所有从第 i个结点出发的边的方法是（ ）。19. 设无向图G中顶点数为n，则图G最少有（ ）条边，最多有（ ）条

15、边。若G为有向图，有n个顶点，则图至少有（ ）条边，最多有（ ）条边。20. 某作业工程表示成网络图，如图7.5所示。事件5的最早完成时间是（ ）。事件4的最迟开始时间是（ ）。事件5 的迟缓时间是（ ）。关键路径是（ ）。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个顶点

16、e条边，则其邻接表中需要（ ）个结点。其中，（ ）个结点构成头结点，（ ）个结点构成边结点表。25. 对有向图，若它有n顶点e条边，则其邻接表中需要（ ）个结点。其中，（ ）个结点构成头结点，（ ）个结点构成边结点表。26. 在邻接表上，无向图中顶点vi的度恰为（ ）。对有向图，顶点vi的出度是（ ）。为了求入度，必须遍历整个邻接表，在所有单链表中，其邻接点域的值为（ ）的结点的个数是顶点vi的入度。27. 遍历图的基本方法有（ ）优先搜索和（ ）优先搜索两种。四、 简答题1. 对于一个具有n个顶点的连通无向图，如果它有且只有一个简单回路，此图有几条边？一个具有n个顶点的弱连通图至少有几条边？

17、2. 已知某图的邻接表，如何建立该图的邻接矩阵？3. 简述无向图和有向图有哪几种存储结构，并说明各种结构在图的不同操作中有什么优越性？什么是AOE网的关键路径？五、 补充应用题1. 给出无向图如图7.6所示的G1的邻接矩阵和邻接表。图 7.62. 分别给出图7.6所示的G2的邻接矩阵、邻接表和逆邻接表。3. 分别给出图7.6所示的G3从v5出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。4. 求出图7.7的连通分量。5. 设有一无向图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,

18、5),(1,5),(3,5)。1) 按上述顺序输入后，画出其相应的邻接表；2) 在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。6. 已知连通网的邻接矩阵如图7.8所示，顶点集合为v1,v2,v3,v4,v5，试画出它所表示的从顶点v1开始利用Prim 算法得到的最小生成树。7. 拓扑排序的结果不是唯一的，对图7.9进行拓扑排序，写出全部不同的拓扑排序序列。8. 已知图G的邻接表如图7.10所示，顶点V1为出发点，完成要求：（1） 深度优先搜索的顶点序列；（2） 广度优先搜索的顶点序列；（3） 由深度优先搜索得到的一棵生成树；（4） 由广度优先搜索得到的一棵生成树。9. 图7.11所示

19、为一无向连通网络，要求根据Prim 算法和Kruskal 构造出它的最小生成树。10. 在下图所示的有向图7.12 中：（1）该图是强连通图吗？ （2）请给出每个顶点的度、入度和出度。（3）给出其邻接矩阵、邻接表及逆邻接表。11. DFS和BFS遍历采用什么样的数据结构来暂存顶点？当要求连通图的生成树的高度最小，应采用何种遍历？画出以顶点v1为初始源点遍历图7.13 所示的有向图所得到的DFS和BFS生成森林。12. 对图 7.14 所示的有向网，试利用Dijkstra 算法求从源点1到其他各顶点的最短路径。13. 已知如图7.16所示的AOE网。求：（1）每项活动的最早开始时间和最晚开始时间

20、；（2）完成此工程最少需要多少单位时间；（3）关键活动与关键路径。14. 已知带权连通图，G（V,E）的邻接表如图7.17所示。试画出该图，并分别从顶点1 开始的深度优先和广度优先遍历之，给出遍历中结点的序列，最后画出该图的一棵最小生成树。其中表结点的三个域为：15. 已知某图 G 的邻接矩阵为，顶点集合为v1,v2,v3,v41) 由邻接矩阵画出相应的图G；2) 如果要使此图成为完全图还要增加哪几条边。16. 对于图7.19所示的AOE网络，计算各事件（顶点）的ve(vi)和vl(vj)和活动（边）的e(ai)和l(ai)函数值；列出各条关键路径和关键活动。8 / 88/8北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1