《数据结构及其应用》笔记含答案 第六章_图.pdf
版权申诉
5星 · 超过95%的资源 171 浏览量
2022-05-28
02:23:03
上传
评论
收藏 859KB PDF 举报 
第 6 章 图
一、填空题
1、用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网（AOV-网）。
2、有 n(n-1)/2 条边的无向图称为_无向完全图__；有 n(n-1)条边的有向图称为_有向完全图。
3、一个含 n 个结点的完全无向图中，其最大边数为__ n(n-1)/2_。
4、顶点表示事件，弧表示活动，权表示活动持续时间的有向图称为AOE-网。
二、判断题
1、任何无向图都存在生成树。（ ）
2、连通分量是无向图中的极小连通子图。（ ）
3、强连通分量是有向图中的极大强连通子图。（ ）
4、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与
图中结点个数有关，而与图的边数无关。（ ）
5、邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（ ）
6、求最小生成树的 Prim 算法在边较少、结点较多时效率较高。（ ）
7、图的最小生成树的形状可能不唯一。（ ）
8、一个 AOV 网的拓扑序列一定是唯一的。 （ ）
9、若 AOV 网中存在环，则不能求它的拓扑排序序列。（ ）
10、若 AOV 网中所有顶点都在它的拓扑有序序列中，则该 AOV 网必定不存在环。（ ）
11、缩短关键路径上活动的工期一定能够缩短整个工程的工期。（ ）
12、AOE 网中一定只有一条关键路径。（ ）
三、单项选择题
1、在一个图中，所有顶点的度数之和等于图的边数的（ C ）倍。
A．1/2 B．1 C．2 D．4
2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B ）倍。
A．1/2 B．1 C．2 D．4
解释：有向图所有顶点入度之和等于所有顶点出度之和。
3、具有 n 个顶点的有向图最多有（ B ）条边。
A．n B．n(n-1) C．n(n+1) D．n
2
解释：有向图的边有方向之分，即为从n 个顶点中选取 2 个顶点有序排列，结果为n(n-1)。
4、n 个顶点的连通图用邻接距阵表示时，该距阵至少有（ B ）个非零元素。
A．n B．2(n-1) C．n/2 D．n
2
5、G 是一个非连通无向图，共有 28 条边，则该图至少有（ C ）个顶点。
A．7 B．8 C．9 D．10
解释：8 个顶点的无向图最多有 8*7/2=28 条边，再添加一个点即构成非连通无向图，故至少有9
个顶点。
6、若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该
图一定是（ B ）图。
A．非连通 B．连通 C．强连通 D．有向
解释：即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。
7、下面（A ）算法适合构造一个稠密图G 的最小生成树。
1
剩余14页未读，继续阅读
资源评论
hongzh02023-04-24资源很实用，对我启发很大，有很好的参考价值，内容详细。
