数据结构第7章图习题

1、、单项选择题第 7章 图1在一个无向图 G 中，所有顶点的度数之和等于所有边数之和的 倍Al/2B1C2D42在一个有向图中， 所有顶点的入度之和等于所有顶点的出度之和的 倍Al/2B1C2D43一个具有 n 个顶点的无向图最多包含 条边。AnBn1Cn-1Dn(n-1)/24一个具有 n 个顶点的无向完全图包含 条边。An(n-l)Bn(n+l)Cn(n-l)/2Dn(n-l)/25一个具有 n 个顶点的有向完全图包含 条边。An(n-1)Bn(n+l)Cn(n-l)/2Dn(n+l)/26对于具有 n 个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为 AnB. n><hCn-1

2、7.无向图的邻接矩阵是一个 A .对称矩阵C.上三角矩阵D. (n-I)也-I)B.零矩阵D.对角矩阵8对于一个具有 n 个顶点和 e 条边的无 (有)向图，若采用邻接表表示，则表头 向量的大小为 。AnBeC 2nD 2e9对于一个具有 n 个顶点和 e 条边的无 (有)向图，若采用邻接表表示，则所有 顶点邻接表中的结点总数为 。AnBeAnBeC2nD2e10在有向图的邻接表中，每个顶点邻接表链接着该顶点所有邻接点。A 入边B出边C.入边和出边D .不是入边也不是出边11.在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有邻接点。A .入边B.出边C.入边和出边D .不是人边也不是出边1

3、2.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点， 则该图一定是A .完全图B.连通图C.有回路D .一棵树13.采用邻接表存储的图的深度优先遍历算法类似于二叉树的算法。A .先序遍历B.中序遍历C.后序遍历D .按层遍历14.采用邻接表存储的图的广度优先遍历算法类似于二叉树的算法。A .先序遍历B.中序遍历C.后序遍历D .按层遍历15.如果无向图 G 必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是AnBeA. G 肯定不是完全图G 一定不是连通图AnBeAnBeB. G 中一定有回路G 有二个连通分量AnBeAnBe16. 下列有关图遍历的说法不正确的

4、是A .连通图的深度优先搜索是一个递归过程B. 图的广度优先搜索中邻接点的寻找具有先进先出”的特征C.非连通图不能用深度优先搜索法D.图的遍历要求每一顶点仅被访问一次17. 下列说法中不正确的是A .无向图中的极大连通子图称为连通分量B连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D.有向图的遍历不可采用广度优先搜索方法18. 一个有向图G的邻接表存储如下图7-1所示，现按深度优先搜索遍历，从顶点vi出发，所得到的顶点序列是 。,V4图7-1 一个有向图的邻接表,V419. 对图7-2所示的无向图，从顶点1开始进行深度优先遍历，可得

5、到顶点访问序列<A. 1， 2， 4， 3， 5， 7， 6B. 1，2，4，3，5，6，7序列<A. 1， 3， 2， 4， 5， 6， 7B. 1， 2， 4， 3， 5， 6， 7C. 1， 2， 3， 4， 5， 7， 6D. 2， 5， 1， 4， 7， 3， 6一个无向连通图的生成树是含有该连通图的全部顶点的B 极小子图D 极大子图A 极小连通子图C. 极大连通子图 22设无向图G=(V, E)和G = (V ',如果G'为G的生成树，则下列说法中不正确的是 。A. G'为G的连通分量B. G'为G的无环子图C. G'为G的子图D

6、 . G'为G的极小连通子图且 V'= V23. 任意一个无向连通图 最小生成树。A .只有一棵B.有一棵或多棵C. 一定有多棵D .可能不存在24. 对于含有 n 个顶点的带权连通图，它的最小生成树是指图中任意一个A .由n-1条权值最小的边构成的子图。B. 由n-1条权值之和最小的边构成的子图。C. 由n-1条权值之和最小的边构成的连通子图。D. 由n个顶点构成的边的权值之和最小的生成树。25. 若一个有向图中的顶点不能排成一个拓扑序列， 则可断定该有向图 A .是个有根有向图B.是个强连通图C.含有多个入度为0的顶点D .含有顶点数目大于1的强连通分量26判定一个有向图是

7、否存在回路除了可以利用拓扑排序方法外，还可以用 A.求关键路径的方法B.求最短路径的Dijkstra算法C.广度优先遍历算法D .深度优先遍历算法27求最短路径的 Dijkstra 算法的时间复杂度为 。AO(n)BO(n+e)CO(n2)DO(ne)28求最短路径的 Floyd 算法的时间复杂度为 。AO(n)BO(ne)CO(n2)D O(n3)29关键路径是事件结点网络中 。A .从源点到汇点的最长路径B .从源点到汇点的最短路径C最长的回路D 最短的回路30下面说法不正确的是 。A在AOE网中，减少任一关键活动的权值后，整个工期也就相应减少BAOE 网工程工期为关键活动的权值和C.在关

8、键路径上的活动都是关键活动，而关键活动也必须在关键路径上DA 和 B31下面说法不正确的是 。A 关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，将使整个工程提前完成C 所有关键活动都提前完成，则整个工程提前完成D 某些关键活动若提前完成，将使整个工程提前完成二、填空题1 对于具有n个顶点的无向图G最多有 边。2对于具有 n 个顶点的强连通有向图 G 至少有条边。3对于具有 n 个顶点的有向图，每个顶点的度最大可达 。4若无向图G的顶点度数最小值大于 寸，G至少有一条回路。5对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量 的大小为 ，所有邻接表中的

9、结点总数是 。6已知一个有向图的邻接矩阵表示，删除所有从第 i 个结点出发的弧的方法是7对于 n 个顶点的无向图，采用邻接矩阵表示， 求图中边数的方法是 ，判断任意两个顶点 i 和 j 是否有边相连的方法是 ，求任意一个顶点的度的方法是 。8对于 n 个顶点的有向图， 采用邻接矩阵表示， 求图中边数的方法是 ，判断任意两个顶点 i 和 j 是否有边相连的方法是 ，求任意一个顶点的度的方法是 。9无向图的连通分量是指 。10已知图G的邻接表如图7-3所示，从顶点vi出发的深度优先搜索序列为，从顶点 1 出发的广度优先搜索序列为 。V1V2V3V4AV5V6A236A5A4A图7-3图G的邻接表1

10、1. n个顶点连通图的生成树一定有 边。12. 个连通图的 一个极小连通子图。13. Prim算法适用于求的网的最小生成树，Kruskal算法适用于求的网的最小生成树。14. 在AOV图中，顶点表示 有向边表示。15. 可以进行拓扑排序的有向图一定是 。16. 从源点到汇点长度最长的路径称为关键路径，该路径上的活动称为 17. Dijkstra算法从源点到其它各顶点的路径长度按 序依次产生，该算法在边上的权出现 情况时，不能正确产生最短路径。18. 求从某源点到其余各项点的Dijkstra算法在图的顶点数为10,用邻接矩阵表 示图时计算时间约为10ms,贝U在图的顶点数为40时，计算时间约为m

11、s三、判断题1 .具有n个顶点的无向图至多有n (n-1)条边。2. 有向图中各顶点的入度之和等于各顶点的出度之和。3. 邻接矩阵只储存了边的信息，没有存储顶点的信息。4. 对同一个有向图，只保存出边的邻接表中结点的数目总是和只保存入边的邻 接表中结点的数目一样多。5. 如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。6. 如果表示有向图的邻接矩阵是对称矩阵，则该有向图一定是有向完全图7如果表示某个图的邻接矩阵不是对称矩阵，则该图一定是有向图。8连通分量是无向图的极小连通子图。9强连通分量是有向图的极大连通子图。10. 对有向图G,如果以任一顶点出发进行一次深度优先或广度优先搜索能访问 到

12、每一个顶点，则该图一定是完全图。11. 连通图的广度优先搜索中一般要采用队列来暂时刚访问过的顶点。12. 图的深度优先搜索中一般要采用栈来暂时刚访问过的顶点。13. 有向图的遍历不可采用广度优先搜索方法。14. 连通图的生成树包含了图中所有顶点。15. 设 G 为具有 n 个顶点的连通图， 如果其中的某个子图有 n 个顶点， n-1 条边， 则该子图一定是G的生成树。16. 最小生成树是指边数最小的生成树。17. 从 n 个顶点的连通图中选取 n-1 条权值最小的边，即可构成最小生成树。18. 只要无向网中没有权值相同的边，其最小生成树就是惟一的。19. 只要无向网中有权值相同的边，其最小生成

13、树就可能不是惟一的。20. 有环图也能进行拓扑排序。21 .拓扑排序算法仅适用于有向无环图。21. 任何有向无环图的结点都可以排成拓扑排序，而且拓扑序列不惟一。22. 关键路径是由权值最大的边构成的。23. 在 AOE 网中，减小任一关键活动上的权值后，整个工期也就相应减小。24. 在 AOE 网中工程工期为关键活动上权值之和。25. 在关键路径的活动都是关键活动，而关键活动未必在关键路径上。26. 关键活动不按期完成就会影响整个工程的完成时间。27. 所有关键活动都提前完成，则整个工程将提前完成。28. 某些关键活动若提前完成，将可能使整个工程提前完成。29. 求单源最短路径的狄克斯特拉算法

14、不适用于有回路的有向网。四、简答题1图G是一个非连通无向图，共有28条边，则该图至少有多少个顶点？2.用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？3 对于稠密图和稀疏图，就存储而言，采用邻接矩阵和邻接表哪个更好些？4请回答下列关于图的一些问题：(1) 有n个顶点的有向强连通图最多有多少条边？最少有多少条边？(2) 表示一个有1000个顶点，1000条边的有向图的邻接矩阵有多少个矩阵 元素？是否为稀疏矩阵？(3) 对于一个有向图，不用拓扑排序，如何判断图是否存在环？5. 对n个顶点的无向图和有向图，采用邻接表表示时，如何判别下列有关问题?(1) 图中有多少条边？(2

15、) 任意两个顶点i和j是否有边相连？(3) 任意一个顶点的度是多少？6. 给出如图7-4所示的无向图G的邻接矩阵和邻接表两种存储结构。并在给定 的邻接表基础上，指出从顶点1出发的深度优先遍历和广度优先遍历序列。7 .对于图7-5所示的有向图，试给出：(1) 邻接矩阵。(2)邻接表(3)强连通分量(4) 对照邻接表，给出从顶点1出发的深度优先遍历序列。(5) 对照邻接表，给出从顶点3出发的深度优先遍历序列。图7-5 一个有向图8.什么样的图其最小生成树是惟一的?9已知带权连通图G（V,E）邻接表如图7-6所示，请画出该图，并分别以深度优 先和广度优先遍历该图，写出遍历中结点的序列，并画出该图的一

16、棵最小生 成树，其中表结点的3个域各为：V1V2V3V4V51.2.34.5*212316418A41232522A1*116J22J44AA41834J510A14222410A顶点号边上所带的权指针图7-6连通图的邻接表10已知世界6大城市为：北京（B）纽约（N）巴黎（P）伦敦（L）东京（T） 墨西哥城（M ）试用由表1给出的交通网确定最小生成树，并说明所使用的 方法及其时间复杂度。BNPLTMB1098281 I21 I124N109585510832P82583 I97 I92 IL815539589T211089795 1113M12432928911311 对于图7-7所示的带权有

17、向图，采用狄克斯特拉算法求从顶点1到其它顶点图7-7 一个有向图图7-8 一个有向图12设图7-8中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试 问建在哪个村庄能使个村庄总体交通代价最小。13表2所示给出了某工程各工序之间的优先关系和各工序所需的时间。表2某工程各工序关系表工序代号AB CD EFGHI JKLMN所需时间1510 5081540300151206015302040先驱工作-a,bBC,DBEGlEIF,IH,J,KLG完成如下各小题：(1) 画出相应的AOE网(2) 列出事件的最早发生时间，最迟发生时间。(3) 找出关键路径并指明完成该工程所需的最短时间。14.如

18、图7-9所示的AOE网，求：(1) 每项活动ai最早开始时间e(ai)和最迟开始时间l(ai)。(2) 完成此工程最少需要多少天(设边上权值为天数)。(3) 哪些是关键活动(4) 是否存在某项活动，当其提高速度后能使整个工程缩短工期?五、算法设计题1.假设图G采用邻接表存储，分别设计实现以下要求的算法:(1) 求出图G中每个顶点的入度。(2) 求出图G中每个顶点的出度(3) 求出图G中出度最大的一个顶点，输出该顶点的编号计算图G中出度为0的顶点数。(4) 判断图G中是否存在边i,j。2 假设图G采用邻接矩阵存储，分别设计实现以下要求的算法：(1) 求出图G中每个顶点的入度。(2) 求出图G中每

19、个顶点的出度(3) 求出图G中出度最大的一个顶点，输出该顶点的编号。(4) 计算图G中出度为0的顶点数。(5) 判断图G中是否存在边i,j。3 设计一个将邻接表转换为邻接矩阵的算法。4一个连通图采用邻接表作为存储机构，设计一个算法实现从顶点v出发的深度优先遍历的非递归过程。5设计一个算法，求不带权无向连通图 G中距离顶点v的最远顶点。6设计一个算法，判断无向图 G是否是一棵树，若是树，返回1;否则返回0。7假设图采用邻接表存储，分别写出基于 DFS和BPS遍历的算法来判别顶点i 和顶点j (i!=j)之间是否有路径。8假设图G采用邻接表存储，设计一个算法，判断无向图 G是否连通，若连通 则返回

20、1;否则返回0。9假设图G采用邻接表存储，设计一个算法，输出图 G中从顶点u到v的长度 为1的所有简单路径。10假设图G采用邻接表存储，设计一个算法，输出图 G中从顶点u到v的所 有简单路径。11假设图G采用邻接表存储，设计一个算法，从如图 7-10所示的无向图G中 找出满足如下条件的一条路径：(1) 给定起点vi和终点vj。(2) 给定一组必经点7,9，即输出的路径必须包含这些顶点(3) 给定一组必避点1,6，即输出的路径不能包含这些顶点6125101311图 7-1012假设图G采用邻接矩阵存储，采用遍历方法实际一个有向图的根的算法若有向图中存在一个顶点v,从v可以通过路径达达图中其它所有顶点，则 称v为该有向图的根。13假设图G采用邻接矩阵存储，设计一个算法判断在给定的有向图中是否存 在一个简单有向回路，若存在，则以顶点序列的方法输出该回路