数据结构与算法分析第六章图作业讲解-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构与算法分析第六章图作业讲解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

参考教材：《数据结构（C语言版第2版）》严蔚敏，李冬梅，吴伟民编著，人民邮电出版社，2022年版。

截图未标明出处均为原创或取自《数据结构（C语言版第2版）》~

本文对应的作业题讲解视频：

数据结构与算法分析作业讲解视频合集https://www.bilibili.com/video/BV1NN411A7hd/?share_source=copy_web&vd_source=7fbf4cbf97db097fe9c00746d1be6e44

作业讲解文档链接目录：

第二章线性表

第三章栈和队列

第四章串、数组和广义表

第五章树和二叉树

第六章图

第七章查找

第八章排序

(۶//•̀ᴗ•́)۶// (۶//*'▽'*)۶// (۶//๑˃̵ᴗ˂̵)۶/ (۶//•̀ᴗ•́)۶// (۶//*'▽'*)۶// (۶//๑˃̵ᴗ˂̵)۶/

╭═════╮╭═══════════╮
╭╯让路！ ║ 题来了！题来了！
╰⊙═══⊙╯╰═⊙═══⊙═══⊙╯

单选题1	用邻接矩阵A表示图,判定任意两个顶点Vi和Vj之间是否有长度为m的路径相连,则只要检查( )的第i行第j列的元素是否为零即可。
	A: m^A B: A C: A^m D: A^(m-1)
	正确答案：C
	思路：
单选题2	用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印相应的顶点,则输出的顶点序列是( )。
	A: 逆拓扑有序 B: 拓扑有序 C: 无序的
	正确答案：A
	思路：
单选题3	下列说法不正确的是( )。
	A: 图遍历是从某源点出发，每一个顶点仅被访问一次 B: 遍历的基本算法有两种：深度遍历和广度遍历 C: 图的深度遍历不适合有向图 D: 图的深度遍历是一个递归过程
	正确答案：C
	思路：反例：第二题。
单选题4	无向图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)},对该图进行深度优先遍历,得到的顶点序列正确的是( )。
	A: a,b,e,c,d,f B: a,c,f,e,b,d C: a,e,b,c,f,d D: a,e,d,f,c,b
	正确答案：D
	思路：先根据已知条件画图，然后从a点开始遍历。
单选题5	用邻接矩阵存储一个图所需的存储单元数目与图的边数有关。( )
	A: 正确 B: 错误
	正确答案：B
	思路：邻接矩阵表示法创建无向图G的时间复杂度是O(n^2)
单选题6	用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小与图中结点个数有关,而与图的边数无关。
	A: 正确 B: 错误
	正确答案：A

单选题7	有n个顶点的无向图,采用邻接矩阵表示,图中的边数等于邻接矩阵中非零元素之和的一半。( )
	A: 正确 B: 错误
	正确答案：A
	思路：
单选题8	有向图的邻接矩阵是对称的。( )
	A: 正确 B: 错误
	正确答案：B
	思路：
单选题9	无向图的邻接矩阵一定是对称矩阵,有向图的邻接矩阵一定是非对称矩阵。
	A: 正确 B: 错误
	正确答案：B
	思路：前半句是对的；后半句是错的。
单选题10	连通分量指的是有向图中的极大连通子图。
	A: 正确 B: 错误
	正确答案：B
	思路：连通分量：无向图中的极大连通子图
单选题11	邻接多重表是无向图和有向图的链式存储结构。
	A: 正确 B: 错误
	正确答案：B
	思路：邻接多重表是无向图的一种链式存储结构。
单选题12	十字链表是无向图的一种存储结构。
	A: 正确 B: 错误
	正确答案：B
	思路：十字链表是有向图的一种链式存储结构。
单选题13	无向图的邻接矩阵可用一维数组存储。
	A: 正确 B: 错误
	正确答案：A
	思路：
单选题14	邻接矩阵适用于有向图和无向图的存储,但不能存储带权的有向图和无向图,而只能使用邻接表存储形式来存储它。
	A: 正确 B: 错误
	正确答案：B

单选题15	有e条边的无向图,在邻接表中有e个结点。
	A: 正确 B: 错误
	正确答案：B
	思路：无向图中的一条边要存储两次。
单选题16	有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。
	A: 正确 B: 错误
	正确答案：B
	思路：顶点的度=顶点的出度+顶点的入度
单选题17	强连通图的各顶点间均可达。
	A: 正确 B: 错误
	正确答案：A
	思路：
单选题18	强连通分量是无向图的极大强连通子图。
	A: 正确 B: 错误
	正确答案：B
	思路：
单选题19	一个有向图的邻接表和逆邻接表中结点的个数可能不等。
	A: 正确 B: 错误
	正确答案：B
	思路：
单选题20	需要借助于一个队列来实现DFS算法。
	A: 正确 B: 错误
	正确答案：B
	思路： DFS一般借助栈或递归实现。
单选题21	一个连通图的生成树是一个极小连通子图。
	A: 正确 B: 错误
	正确答案：A
	思路：
单选题22	N个顶点的连通图用邻接矩阵表示时,该矩阵至少有( )个非零元素。
	A: N B: 2(N-1) C: N-1 D: N+1
	正确答案：B
	思路： N个顶点的连通图至少有N-1条边。无向图的一条边在邻接矩阵中对应两个非零元素，所以整个矩阵一共有2(N-1)个非零元素。
单选题23	在图G的邻接表表示中,每个顶点邻接表中所含的结点数,对于无向图来说等于该顶点的度;对于有向图来说等于该顶点的出度。
	A: 正确 B: 错误
	正确答案：A
	思路：
单选题24	具有10个顶点的无向图,边的总数最多为( )
	A: 45 B: 90 C: 10 D: 20
	正确答案：A
	思路：每个顶点和其他所有顶点都有边，则每个顶点有9条边×10个顶点=90，又因为无向图中一个边连接两个点，所以，90/2= 45条边。
单选题25	在有n个顶点的有向图中,若要使任意两点间可以互相到达,则至少需要( )条弧。
	A: n+1 B: 2n C: n D: 2(n-1)
	正确答案：C
	思路：整体形成一个环即可。
单选题26	要连通具有n个顶点的有向图,至少需要( )条边。
	A: n-1 B: n C: n+1 D: 2n
	正确答案：B
	思路：整体形成一个环即可。
单选题27	在有n个顶点的有向图中,每个顶点的度最大可达( )。
	A: n+1 B: 2n C: n D: 2(n-1)
	正确答案：D
	思路：出度=入度=n-1。即每个点都有出发到其他所有点的弧和从其他所有出发到达自己的弧。
单选题28	若用n表示图中顶点数目,则有( )条边的无向图成为完全图。
	A: n(n-1)/2 B: n(n-1) C: 2n(n-1) D: n^2
	正确答案：A
	思路：
单选题29	n个结点的完全有向图含有边的数目( )。
	A: n^2 B: n(n+1) C: n/2 D: n(n-1)
	正确答案：D

单选题30	设无向图的顶点个数为n,则该图最多有( )条边。
	A: n-1 B: n(n-1)/2 C: n(n+1)/2 D: n^2
	正确答案：B

单选题31	G是一个非连通无向图,共有28条边,则该图至少有( )个顶点。
	A: 9 B: 10 C: 11 D: 12
	正确答案：A
	思路：假设图G’满足最少有n个点构成一个有28条边的连通无向图，则G’再增加一个孤立的点，就能满足题意，使该图成为非连通无向图G。且最少有n个点构成一个有28条边的连通无向图，则G’一定是一个完全图，即n(n-1)/2=28, n=8, 即G中的顶点数=8+1=9。
单选题32	对于一个具有n个顶点e条边的无向图的邻接表的表示,则表头向量大小为n,邻接表的边结点个数为( )。
	A: n*e B: n C: e D: 2e
	正确答案：D
	思路：注意这是一个无向图。
单选题33	已知一无向图G=(V,E),其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图,得到的序列为abecd,则采用的是广度优先遍历方法。
	A: 正确 B: 错误
	正确答案：B

单选题34	图中有关路径的定义是( )。
	A: 由顶点和相邻顶点序偶构成的边所形成的序列 B: 由不同顶点所形成的序列 C: 由不同边所形成的序列 D: 上述定义都不是
	正确答案：A

单选题35	一个包含n个顶点的连通无向图,其边的个数至少为( )。
	A: n-1 B: n C: n+1 D: nlogn
	正确答案：A

单选题36	在一个无向图中,所有顶点的度数之和等于所有边数( )倍。
	A: 1/2 B: 1 C: 3/2 D: 2
	正确答案：D
	思路：一个边连接两个点。举例。
单选题37	在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的( )倍。
	A: 0 B: 1/2 C: 2 D: 1
	正确答案：D
	思路：一个弧提供一个入度+一个出度。所以入度之和=出度之和=弧的数量。
单选题38	一个有n个结点的图,最少有( )个连通分量。
	A: 0 B: 1 C: n D: n-1
	正确答案：B
	思路：连通分量是指无向图中的极大连通子图。
单选题39	一个有n个结点的图,最多有( )个连通分量。
	A: 1 B: n-1 C: n D: n+1
	正确答案：C
	思路：连通分量是指无向图中的极大连通子图。
单选题40	下列哪一种图的邻接矩阵是对称矩阵?( )
	A: 有向图 B: 无向图 C: AOV网(属于有向图） D: AOE网(属于有向图）
	正确答案：B
	思路：
单选题41	关键路径是事件结点网络中( )。
	A: 从源点到汇点的最长路径 B: 从源点到汇点的最短路径 C: 最长回路 D: 最短回路
	正确答案：A
	思路：
单选题42	关键路径是AOE网中从源点到终点的最长路径。
	A: 正确 B: 错误
	正确答案：A

单选题43	下列关于AOE网的叙述中,不正确的是( )。
	A: 关键活动不按期完成就会影响整个工程的完成时间 B: 任何一个关键活动提前完成,那么整个工程将会提前完成 C: 所有的关键活动提前完成,那么整个工程将会提前完成 D: 某些关键活动提前完成,那么整个工程将会提前完成
	正确答案：B
	思路：关键路径可能不止一条，一个关键路径上的关键活动提前完成，另一条关键路径上的活动保持不变，整个工程还是不会提前完全。
单选题44	在表示某工程的AOE网中,加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。
	A: 正确 B: 错误
	正确答案：B

单选题45	下面关于求关键路径的说法不正确的是( )。
	A: 求关键路径是以拓扑排序为基础的 B: 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C: 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D: 关键活动一定位于关键路径上
	正确答案：C
	思路：
单选题46	在AOE图中关键路径上活动的时间延长多少,整个工程时间也就随之延长多少。
	A: 正确 B: 错误
	正确答案：A

单选题47	Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按递增次序依次产生,该算法弧上的权出现负值情况时,不能正确产生最短路径。
	A: 正确 B: 错误
	正确答案：A
	思路：
单选题48	已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7}, E={<V1,V2>, <V1,V3>, <V1,V4>, <V2,V5>, <V3,V5>, <V3,V6>, <V4,V6>, <V5,V7>, <V6,V7>},G的拓扑序列是( )。
	A: V1,V3,V4,V6,V2,V5,V7 B: V1,V3,V2,V6,V4,V5,V7 C: V1,V3,V4,V5,V2,V6,V7 D: V1,V2,V5,V3,V4,V6,V7
	正确答案：A
	思路：
单选题49	下面哪一方法可以判断出一个有向图是否有环( )
	A: 深度优先遍历 B: 拓扑排序 C: 求最短路径 D: 求关键路径
	正确答案：B
	思路：在 AOV-网中，不应该出现有向环，因为存在环意味着某项活动应以自己为先决条件。显然，这是荒谬的。若设计出这样的流程图，工程便无法进行。而对程序的数据流图来说，则表明存在一个死循环。因此，对给定的 AOV-网应首先判定网中是否存在环。检测的办法是对有向图的顶点进行拓扑排序，若网中所有顶点都在它的拓扑有序序列中，则该A0V-网中必定不存在环。
单选题50	有向图G可拓扑排序的判别条件是不存在环。
	A: 正确 B: 错误
	正确答案：A

单选题51	拓扑排序的有向图中,最多存在一条环路。
	A: 正确 B: 错误
	正确答案：B

单选题52	在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是( )。
	A: G中有弧<vi,vj> B: G中有一条从Vi到Vj的路径 C: G中没有弧<vi,vj> D: G中有一条从Vj到Vi的路径
	正确答案：D
	思路：顶点Vi在顶点Vj之前，说明Vi是执行Vj的先决条件。如果还有D答案Vj到Vi的路径，则Vj是Vi的先决条件，彼此互为先决条件，则存在环，无法产生产生拓扑排序，与题目矛盾，所以选D。
单选题53	设有向图有n个顶点和e条边,进行拓扑排序时,总的计算时间为( )。
	A: O(n) B: O(n^2) C: O(n+e) D: O(n*e)
	正确答案：C
	思路：因为拓扑排序算法是在AOV-网上进行的，是一种有向图，并且排序算法的整个过程对每个活动（顶点）和每个弧都只经历一次。且用邻接表表示图时的时间复杂度为O(n+e)。
单选题54	在用邻接表表示图时,拓扑排序算法时间复杂度为( )。
	A: O(n) B: O(n+e) C: O(nn) D: O(nn*n)
	正确答案：B
	思路：因为拓扑排序算法是在AOV-网上进行的，是一种有向图，并且排序算法的整个过程对每个活动（顶点）和每个弧都只经历一次。且用邻接表表示图时的时间复杂度为O(n+e)。
单选题55	拓扑排序算法把一个无向图中的顶点排成一个有序序列。
	A: 正确 B: 错误
	正确答案：B

单选题56	拓扑排序算法仅能适用于有向无环图。
	A: 正确 B: 错误
	正确答案：B

单选题57	带权的连通无向图的最小代价生成树是唯一的。( )
	A: 正确 B: 错误
	正确答案：B
	思路：可能会生成多个代价之和相同且都为最小的生成树。
单选题58	最小生成树问题是构造连通网的最小代价生成树。( )
	A: 正确 B: 错误
	正确答案：A

单选题59	任何有向图的结点都可以排成拓扑排序,而且拓扑序列不唯一。
	A: 正确 B: 错误
	正确答案：B
	思路：不能在有环的有向图上完成拓扑排序。
单选题60	不同的求最小生成树的方法最后得到的生成树是相同的。
	A: 正确 B: 错误
	正确答案：B
	思路：最小生成树的形状可以是不同，但能保证代价之和相同且同为最小。
单选题61	最小生成树的KRUSKAL算法是一种贪心法。
	A: 正确 B: 错误
	正确答案：A
	思路： KRUSKAL算法：克鲁斯卡尔算法。
单选题62	求最小生成树的普里姆()算法中边上的权可正可负。
	A: 正确 B: 错误
	正确答案：B

单选题63	判断一个无向图是一棵树的条件是有n个顶点,n-1条边的无向连通图。
	A: 正确 B: 错误
	正确答案：A

单选题64	Prim(普里姆)算法适用于求边稠密的网的最小生成树;kruskal(克鲁斯卡尔)算法适用于求边稀疏的网的最小生成树。
	A: 正确 B: 错误
	正确答案：A
	思路：因为普里姆算法（加点法）的过程是不断选点加入。克鲁斯卡尔算法（加边法）的过程是不断选边加入。
单选题65	如果含n个顶点的图形形成一个环,则它有( )棵生成树。
	A: n-1 B: n C: n+1 D: 2n
	正确答案：B
	思路： n个顶点形成一个环，则有n条边。每断一条边，这个环都构不成，整个图可以被看出一棵树，有n条不同的边可以断，则对应有n种生成树。

୧ʕ•̬͡•ʕ•̫͡•♡ʕ͙•̫͑͡•ʔͦʕͮ•̫ͤ͡•ʔ͙ʕ•̫͡•ʕ•̫͡•ʔ୧ʕ•̬͡•ʕ•̫͡•♡〰︎ \ HAVE A GOOD DAY / 〰︎ ʕ•̫͡•ʕ•̫͡•ʔ୧ʕ•̬͡•ʕ•̫͡•♡ʕ͙•̫͑͡•ʔͦʕͮ•̫ͤ͡•ʔ͙୧ʕ•̬͡•ʕ•̫͡•♡ 文章来源地址https://www.toymoban.com/news/detail-777423.html

到了这里，关于数据结构与算法分析第六章图作业讲解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！