1、计算机学科专业基础综合数据结构-图(二)及答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：42，分数：42.00)1.具有 6个顶点的无向图至少应有_条边才能确保是一个连通图。 A.5 B.6 C.7 D.8（分数：1.00）A.B.C.D.2.设 G是一个非连通无向图，有 15条边，则该图至少有_个顶点。 A.5 B.6 C.7 D.8（分数：1.00）A.B.C.D.3.下列关于无向连通图特性的叙述中，正确的是_。所有顶点的度之和为偶数边数大于顶点个数减 1至少有一个顶点的度为 1 A.只有 B.只有 C.和 D.和（分数：1.00）A.B.C.D.4.对
2、于具有 n(n1)个顶点的强连通图，其有向边的条数至少是_。 A.n+1 B.n C.n-1 D.n-2（分数：1.00）A.B.C.D.5.下列有关图的说法中正确的是_。 A.在图结构中，顶点不可以没有任何前驱和后继 B.具有 n个顶点的无向图最多有 n(n-1)条边，最少有 n-1条边 C.在无向图中，边的条数是结点度数之和 D.在有向图中，各顶点的入度之和等于各顶点的出度之和（分数：1.00）A.B.C.D.6.对于一个具有 n个顶点和 e条边的无向图，若采用邻接矩阵表示，则该矩阵大小是_，矩阵中非零元素的个数是 2e。 A.n B.(n-1)2 C.n-1 D.n2（分数：1.00）A
3、.B.C.D.7.无向图的邻接矩阵是一个_。 A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵（分数：1.00）A.B.C.D.8.从邻接矩阵 （分数：1.00）A.B.C.D.E.F.G.H.9.下列说法中正确的是_。 A.一个图的邻接矩阵表示是唯一的，邻接表表示也唯一 B.一个图的邻接矩阵表示是唯一的，邻接表表示不唯一 C.一个图的邻接矩阵表示不唯一，邻接表表示唯一 D.一个图的邻接矩阵表示不唯一，邻接表表示也不唯一（分数：1.00）A.B.C.D.10.用邻接表存储图所用的空间大小_。 A.与图的顶点数和边数都有关 B.只与图的边数有关 C.只与图的顶点数有关 D.与边数的二次方有
4、关（分数：1.00）A.B.C.D.11.采用邻接表存储的图的深度优先搜索算法类似于二叉树的_，广度优先搜索算法类似于二叉树的层次序遍历。 A.中序遍历 B.前序遍历 C.后序遍历 D.层次序遍历（分数：1.00）A.B.C.D.12.如果从无向图的任意一个顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_。 A.强连通图 B.连通图 C.有回路 D.一棵树（分数：1.00）A.B.C.D.13.下面_算法可用于求无向图的所有连通分量。 A.广度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径（分数：1.00）A.B.C.D.14.一个连通图的生成树是含有该连通图的全部顶点的_
5、。 A.极小连通子图 B.极小子图 C.极大连通子图 D.极大子图（分数：1.00）A.B.C.D.15.在一个带权连通图 G中，权值最小的边一定包含在 G的_生成树中。 A.最小 B.任何 C.广度优先 D.深度优先（分数：1.00）A.B.C.D.16.任何一个连通图的最小生成树_。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在（分数：1.00）A.B.C.D.17.对于无向图的生成树，下列说法错误的是_。 A.生成树是遍历的产物 B.从同一顶点出发所得的生成树相同 C.生成树中不包括环 D.不同遍历方法所得的生成树不同（分数：1.00）A.B.C.D.18.当采用邻接表
6、方式存储带权连通图时，求最小生成树的 Prim算法的时间复杂度为_。 A.O(n) B.O(elog2e) C.O(n2) D.O(n3)（分数：1.00）A.B.C.D.19.求最短路径的 Dijkstra算法的时间复杂度为_。 A.O(n) B.O(n+e) C.O(n2) D.O(ne)（分数：1.00）A.B.C.D.20.若一个有向图中的部分顶点不能通过拓扑排序排到一个拓扑有序序列里，则可断定该图是_。 A.有根有向图(如果 G中顶点 a到 G中每个结点都有路径可以到达，则称结点 a为 G的根) B.强连通图 C.含有多个入度为 0的顶点的图 D.含有顶点数大于 1的强连通分量（分数
7、：1.00）A.B.C.D.21.设有向图具有 n个顶点和 e条边，如果用邻接矩阵作为它的存储结构，则拓扑排序的时间复杂度为_。 A.O(nlog2e) B.O(n+e) C.O(n) D.O(n2)（分数：1.00）A.B.C.D.22.在下列有关关键路径的说法中错误的是_。 A.在 AOE网络中可能存在多条关键路径 B.关键活动不按期完成就会影响整个工程的完成时间 C.任何一个关键活动提前完成，整个工程将会提前完成 D.所有的关键活动都提前完成，整个工程将会提前完成（分数：1.00）A.B.C.D.23.图的简单路径是指_不重复的路径。 A.权值 B.顶点 C.边 D.边与顶点均（分数：1
8、.00）A.B.C.D.24.下列说法中正确的是_。 A.如果有向图的邻接矩阵是对称矩阵，则该有向图一定是有向完全图 B.如果某个图的邻接矩阵不是对称矩阵，则该图一定是有向图 C.如果某个图的邻接矩阵是对称矩阵，则该图一定是无向图 D.邻接矩阵表示法只存储了边的信息，没有存储顶点的信息（分数：1.00）A.B.C.D.25.在下列有关图的存储结构的说法中错误的是_。 A.用邻接矩阵存储一个图时所占用的存储空间大小与图中的顶点个数有关，而与图的边数无关 B.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用 C.邻接矩阵只适用于稠密图(边数接近于顶点数的二次方)，邻接表只适用于稀
9、疏图(边数远小于顶点数的二次方) D.对同一个有向图来说，邻接表中的边结点数与逆邻接表中的边结点数相等（分数：1.00）A.B.C.D.26.假设一个有向图具有 n个顶点和 e条边，若该有向图采用邻接矩阵存储，则删除与顶点 i相关联的所有边的时间复杂度是_；若该有向图采用邻接表存储，则删除与顶点 i相关联的所有出边的时间复杂度是 O(e)。 A.O(n) B.O(e) C.O(n+e) D.O(n2)（分数：1.00）A.B.C.D.27.对于一个有向图，若一个顶点的度为 k1，出度为 k2，则对应逆邻接表中该顶点的入边表中的边结点数为_。 A.k1 B.k2 C.k1-k2 D.k1+k2（
10、分数：1.00）A.B.C.D.28.设图有 n个顶点和 e条边，在采用邻接矩阵时，遍历图的顶点所需时间为_；在采用邻接表时，遍历图的顶点所需时间为 O(n+e)。 A.O(n) B.O(n2) C.O(e) D.O(ne)（分数：1.00）A.B.C.D.29.一个有向图 G的邻接表存储如图所示，现按深度优先搜索方式从顶点 A出发执行一次遍历，所得到的顶点序列是_。（分数：1.00）A.B.C.D.30.图的广度优先遍历算法中使用队列作为其辅助数据结构，那么在算法执行过程中每个顶点最多进队_次。 A.1 B.2 C.3 D.4（分数：1.00）A.B.C.D.31.下列关于连通图的 BFS和
11、 DFS生成树的高度论述正确的是_。 A.BFS生成树的高度小于 DFS生成树的高度 B.BFS生成树的高度小于或等于 DFS生成树的高度 C.BFS生成树的高度大于 DFS生成树的高度 D.BFS生成树的高度大于或等于 DFS生成树的高度（分数：1.00）A.B.C.D.32.若一个具有 N个顶点和 K条边的无向图是一个森林(NK)，则该森林必有_棵树。 A.K B.N C.N-K D.1（分数：1.00）A.B.C.D.33.下面的说法中正确的是_。 A.图的一棵最小生成树的代价不一定比该图其他任何一棵生成树的代价小 B.带权连通图的最小生成树可能不唯一，但权值最小的边一定出现在解中 C.
12、若带权连通图上各边上的权值互不相同，则该图的最小生成树是唯一的 D.一个带权连通图的最小生成树的权值之和不是唯一的（分数：1.00）A.B.C.D.34.在用 Kruskal算法求解带权连通图的最小生成树时，通常采用一个_辅助结构，判断一条边的两个端点是否在同一个连通分量上。在该算法中选择权值最小的边的原则是该边不能在图中构成回路，它主要适用于稀疏图。 A.位向量 B.堆 C.并查集 D.生成树顶点集合（分数：1.00）A.B.C.D.35.下列说法中错误的是_。 A.强连通分量是有向图中的极大强连通子图 B.对有向图 G，如果从任意一个顶点出发进行一次深度优先搜索或广度优先搜索能访问到每一个
13、顶点，则该图一定是完全图 C.连通图的广度优先搜索算法中一般要采用队列来暂存刚访问过的顶点 D.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点（分数：1.00）A.B.C.D.36.以下说法中正确的是_。 A.连通分量是无向图中的极小连通子图 B.有向图的遍历不可采用广度优先搜索方法 C.连通图的生成树包含了图中所有顶点 D.对 n个顶点的连通图 G来说，如果其中的某个子图有 n个顶点和 n-1条边，则该子图一定是 G的生成树（分数：1.00）A.B.C.D.37.以下关于最小生成树的说法中正确的是_。 A.最小生成树是指边数最少的生成树 B.从 n个顶点的连通图中选取 n-1条权值最小的
14、边，即可构成最小生成树 C.只要带权无向图中没有权值相同的边，其最小生成树就是唯一的 D.只要带权无向图中有权值相同的边，其最小生成树就不可能是唯一的（分数：1.00）A.B.C.D.38.Dijkstra算法是按_方法求出图中从某顶点到其余顶点最短路径的。 A.按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B.按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C.通过深度优先遍历求出图中某顶点到其余顶点的所有路径 D.通过广度优先遍历求出图的某顶点到其余顶点的最短路径（分数：1.00）A.B.C.D.39.在求最短路径的算法中，要求所有边上的权值都不能为负值的算法是_；虽然允许边上的
15、权值为负值，但不允许在有向回路中出现负值的算法是 Floyd算法。 A.Kruskal算法 B.Dijkstra算法 C.Floyd算法 D.Prim算法（分数：1.00）A.B.C.D.40.以下有关图的最短路径的说法中正确的是_。 A.带权有向图的最短路径一定是简单路径 B.在有向图中，从一个顶点到另一个顶点的最短路径是唯一的 C.求单源最短路径的 Dijkstra算法不适用于有回路的带权有向图 D.在用 Floyd算法求解各顶点之间的最短路径时，每个表示两个顶点之间路径的 path(k-1)ij一定是 path(k)ij的子集（分数：1.00）A.B.C.D.41.设有向图具有 n个顶点
16、和 e条边，如果用邻接表作为它的存储结构，则拓扑排序的时间复杂度为_。 A.O(n) B.O(n+e) C.O(n2) D.O(ne)（分数：1.00）A.B.C.D.42.判断一个有向图是否存在回路除了可利用拓扑排序方法外，还可用利_。 A.求关键路径的方法 B.求最短路径的 Dijkstra方法 C.广度优先遍历算法 D.深度优先遍历算法（分数：1.00）A.B.C.D.二、B综合应用题/B(总题数：12，分数：58.00)43.编写一个算法，将一个无向图的邻接矩阵转换成邻接表。（分数：3.00）_44.设计一个算法，判断无向图 G是否连通。若连通，则返回 1；否则返回 0，假设图中顶点标
17、号从 0到g.vexnum-1。（分数：5.00）_45.设计一个算法，输出图 G中从顶点 vi到 vj的长度为 L的所有简单路径。（分数：5.00）_46.编写一个实现连通图 G的深度优先遍历(从顶点 v出发)的非递归函数，可以用伪代码描述。（分数：5.00）_47.自由树(即无环连通图)T=(V，E)的直径是树中所有点对点之间最短路径长度的最大值，即 T的直径定义为 d(u，v)的最大值(其中 u，vV)。这里 d(u，v)表示顶点 u到顶点 v的最短路径长度(路径长度为路径中包含的边数)。如图所示为一棵自由树，其直径为 18。试写算法求 T的直径，并分析算法的时间复杂度。（分数：5.00
18、）_48.对于一个使用邻接表存储的带权有向图 G，试利用深度优先搜索方法，对该图中所有顶点进行拓扑排序。若邻接表的数据类型为 graph，则算法对应函数的说明为 int dfs_toposort(graph *g) 若函数返回1，则表示拓扑排序成功，图中不存在环；若函数返回 0，则图中存在环，拓扑排序不成功。在这个算法中嵌套调用一个递归的深度优先搜索算法为 dfs1(graph *g, int v) 在遍历图的同时进行拓扑排序，给出整个算法的实现。（分数：5.00）_49.设计一个算法，求出无向图 G的连通分量个数，假设图中顶点标号从 0到 g.vexnum-1。（分数：5.00）_50.图的
19、 D-搜索类似于 BFS(广度优先搜索)，不同之处在于用栈代替 BFS中的队列，入、出队列的操作改为入、出栈的操作，即当一个顶点的所有邻接点被搜索之后，下一个搜索出发点应该是最近入栈(栈顶)的顶点。请用邻接表作为存储结构，写一个 D-搜索算法。（分数：5.00）_51.有一幅如图所示的藏宝图，设计一个算法要求从入口到出口，必须经过“食品”和“财宝”的地方，不得经过“强盗”的地方。（分数：5.00）_52.设计一个算法，输出图 G中经过某个顶点 vi的长度为 L的所有环。（分数：5.00）_53.假设图采用邻接表存储，编写一个函数，利用深度优先搜索算法，求出无向图中通过给定点 v的所有简单回路。
20、（分数：5.00）_54.设计一个算法创建一个带权(路径)的无向图，要求被创建的图由用户输入，输出从 V0到其他各个顶点的最短路程长度和路径。（分数：5.00）_计算机学科专业基础综合数据结构-图(二)答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：42，分数：42.00)1.具有 6个顶点的无向图至少应有_条边才能确保是一个连通图。 A.5 B.6 C.7 D.8（分数：1.00）A. B.C.D.解析：解析 有 n个顶点的连通图，至少需要 n-1条边才能保持图的连通。多一条边将形成回路，少一条边将变成非连通图。当 n=6时，n-1=5。2.设 G是一个非连
21、通无向图，有 15条边，则该图至少有_个顶点。 A.5 B.6 C.7 D.8（分数：1.00）A.B.C. D.解析：解析 本题根据连通图的性质以及顶点与边数的关系即可求解：设无向图有 n个顶点，它的边数en(n-1)/2。若 e=15，有 15n(n-1)/2，解得 n6。在连通图情形下至少需有 6个顶点，在非连通图情形下则至少需有 7个顶点。3.下列关于无向连通图特性的叙述中，正确的是_。所有顶点的度之和为偶数边数大于顶点个数减 1至少有一个顶点的度为 1 A.只有 B.只有 C.和 D.和（分数：1.00）A. B.C.D.解析：解析 无向连通图中每一条边都对应两个度，因此所有顶点的度
22、之和为边数的 2倍，因此一定是偶数。 在无向连通图中，边数最少可以等于顶点个数减 1，此时的无向连通图为一棵树，所以不完全对。 例如，n 个顶点和 n-1条边构成一个环，它可以是连通的，但所有顶点的度均为 2。因此不对。 因此本题选 A。4.对于具有 n(n1)个顶点的强连通图，其有向边的条数至少是_。 A.n+1 B.n C.n-1 D.n-2（分数：1.00）A.B. C.D.解析：解析 对于有向强连通图，当 n等于 1时，边为 0，否则至少需要 n条边才能形成强连通图。此时所有 n个顶点都在某一个有向环上，如下图所示。在此情况下，当有向边的条数少于 n时，不能构成环，不再是强连通图。*5
23、.下列有关图的说法中正确的是_。 A.在图结构中，顶点不可以没有任何前驱和后继 B.具有 n个顶点的无向图最多有 n(n-1)条边，最少有 n-1条边 C.在无向图中，边的条数是结点度数之和 D.在有向图中，各顶点的入度之和等于各顶点的出度之和（分数：1.00）A.B.C.D. 解析：解析 如果有向图中只有一个顶点，则此顶点没有前驱，也没有后继；对于无向图，图中顶点没有次序关系，所以也谈不上前驱和后继，因此选项 A错误。 具有 n个顶点的无向图最少可以有 0条边，只有在连通图的情形下最少是 n-1条边，因此选项 B错误。 在无向图中，所有顶点的度数之和是边的条数的 2倍，选项 C错误。6.对于
24、一个具有 n个顶点和 e条边的无向图，若采用邻接矩阵表示，则该矩阵大小是_，矩阵中非零元素的个数是 2e。 A.n B.(n-1)2 C.n-1 D.n2（分数：1.00）A.B.C.D. 解析：解析 有 n个顶点的图的邻接矩阵记录了每一对顶点之间的关系，有 n2个矩阵元素，其中有 2e个非零元素用以表示无向图的 e条边。7.无向图的邻接矩阵是一个_。 A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵（分数：1.00）A. B.C.D.解析：解析 无向图的邻接矩阵是一个对称矩阵。对于同一条边(v i，v j)，它是双向的，所以在矩阵的第 i行、第 j列以及第 j行、第 i列都为 1。8.
25、从邻接矩阵 （分数：1.00）A.B. C.D.E.F.G.H.解析：解析 此邻接矩阵有 3行 3列，是 3个顶点的邻接矩阵，有 32=9个矩阵元素，其中 4个非零元素。如果它是有向图的邻接矩阵，则应有 4条有向边；如果它是无向图的邻接矩阵，则应有 2条边(对称)。9.下列说法中正确的是_。 A.一个图的邻接矩阵表示是唯一的，邻接表表示也唯一 B.一个图的邻接矩阵表示是唯一的，邻接表表示不唯一 C.一个图的邻接矩阵表示不唯一，邻接表表示唯一 D.一个图的邻接矩阵表示不唯一，邻接表表示也不唯一（分数：1.00）A.B. C.D.解析：解析 图的邻接矩阵表示是唯一的，每条边的信息存放在矩阵中确定的
26、位置。邻接表表示则不唯一，取决于各条边读入的先后次序，以及在边链表中采用前插法还是后插法来插入这些边。10.用邻接表存储图所用的空间大小_。 A.与图的顶点数和边数都有关 B.只与图的边数有关 C.只与图的顶点数有关 D.与边数的二次方有关（分数：1.00）A. B.C.D.解析：解析 设图具有 n个顶点和 e条边，则用邻接表存储图需要建立至少有 n个顶点信息的顶点向量，此外为每一条边创建边链结点，有向图有 e个边链结点，无向图有 2e个边链结点(对称情形)，所以所需的存储空间为 O(n+e)，也就是说所用空间与图的顶点数和边数都有关。11.采用邻接表存储的图的深度优先搜索算法类似于二叉树的_
27、，广度优先搜索算法类似于二叉树的层次序遍历。 A.中序遍历 B.前序遍历 C.后序遍历 D.层次序遍历（分数：1.00）A.B. C.D.解析：解析 图的深度优先遍历类似于树的先根次序遍历，而树的先根次序遍历又与其二叉树表示的前序遍历结果相同，所以采用邻接表存储的图的深度优先搜索算法类似于二叉树的前序遍历。广度优先搜索算法则类似于二叉树的层次序遍历。12.如果从无向图的任意一个顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_。 A.强连通图 B.连通图 C.有回路 D.一棵树（分数：1.00）A.B. C.D.解析：解析 对无向图作一次深度优先搜索，可遍历连通图的所有顶点。当然，通
28、过深度优先搜索也可以遍历一棵树，不过遍历树通常被称为中序、前序、后序遍历；强连通图是有向图，与题意矛盾；有回路的无向图不一定是连通图，因为回路不一定包含图的所有结点。13.下面_算法可用于求无向图的所有连通分量。 A.广度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径（分数：1.00）A. B.C.D.解析：解析 从图中一个顶点出发进行广度优先遍历，能够遍历到所有与该顶点连通的顶点，就是说可找到一个包含了该顶点的连通分量。然后再选择剩余未被访问过的顶点继续广度优先遍历，就可以遍历到其他的连通分量。14.一个连通图的生成树是含有该连通图的全部顶点的_。 A.极小连通子图 B.极小子图 C
29、.极大连通子图 D.极大子图（分数：1.00）A. B.C.D.解析：解析 一个连通图的生成树是具有为保证连通性的边最少的树，是图的极小连通子图。15.在一个带权连通图 G中，权值最小的边一定包含在 G的_生成树中。 A.最小 B.任何 C.广度优先 D.深度优先（分数：1.00）A. B.C.D.解析：解析 求解最小生成树的原则是要选择权值最小的 n-1条边连通 n个顶点，并要求选出的边不能构成回路。权值最小的边是第一个选择的边，它应在最小生成树的边集合中。16.任何一个连通图的最小生成树_。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在（分数：1.00）A.B. C.D.
30、解析：解析 如果一个无向连通图具有多条权值相同的边，在构造最小生成树的过程中选择具有最小权值的边时，会出现多种可能的选择，得到的最小生成树不止一棵；但如果无向连通图各边上具有的权值互不相同时，构造的最小生成树是唯一的。因此，可能有一棵或多棵最小生成树。17.对于无向图的生成树，下列说法错误的是_。 A.生成树是遍历的产物 B.从同一顶点出发所得的生成树相同 C.生成树中不包括环 D.不同遍历方法所得的生成树不同（分数：1.00）A.B. C.D.解析：解析 生成树不允许有环是显而易见的。生成树是通过遍历图中的顶点得到的；遍历方法不同，所得生成树也不同。从同一顶点开始遍历，如果某一个顶点的邻接顶
31、点有多个可选时，选择不同的邻接顶点，可构成不同的生成树，所以选项 B不正确。18.当采用邻接表方式存储带权连通图时，求最小生成树的 Prim算法的时间复杂度为_。 A.O(n) B.O(elog2e) C.O(n2) D.O(n3)（分数：1.00）A.B. C.D.解析：解析 求最小生成树的 Prim算法中，如果采用小根堆来组织那些一个端点在 S中、另一个端点在V-S中的边，最坏情况下所有边都进一次堆，在堆内把权值最小的边调整到堆顶需要的时间是 O(log2e)，则总的时间应是 O(elog2e)。19.求最短路径的 Dijkstra算法的时间复杂度为_。 A.O(n) B.O(n+e) C
32、.O(n2) D.O(ne)（分数：1.00）A.B.C. D.解析：解析 用 Dijkstra算法求从带权有向图的某个源顶点到其他各个顶点的最短路径，执行 n-1次或n-2次选择，每次选择一个顶点后还要计算绕过这个新选出的顶点是否能够缩短从源顶点到其他未选择最短路径的顶点的路径长度，有两层嵌套 for循环，所以算法的时间复杂度为 O(n2)。20.若一个有向图中的部分顶点不能通过拓扑排序排到一个拓扑有序序列里，则可断定该图是_。 A.有根有向图(如果 G中顶点 a到 G中每个结点都有路径可以到达，则称结点 a为 G的根) B.强连通图 C.含有多个入度为 0的顶点的图 D.含有顶点数大于 1
33、的强连通分量（分数：1.00）A.B.C.D. 解析：解析 如果全部顶点都不能通过拓扑排序排到一个拓扑有序序列里，则说明该图是一个强连通图，所有顶点构成一个有向环；如果部分顶点不能通过拓扑排序排到一个拓扑有序序列里，则说明该图中存在回路，该回路构成一个强连通分量。21.设有向图具有 n个顶点和 e条边，如果用邻接矩阵作为它的存储结构，则拓扑排序的时间复杂度为_。 A.O(nlog2e) B.O(n+e) C.O(n) D.O(n2)（分数：1.00）A.B.C.D. 解析：解析 采用邻接矩阵作为有向图的存储结构进行拓扑排序，需要输出每一个顶点，其时间复杂度为 O(n)。在输出顶点后，要针对该顶
34、点检测矩阵中对应的行，根据行中信息寻找与该顶点相关联的边，以便对这些边的入度减 1，其时间复杂度为 O(n)。因此，算法总的时间复杂度为 O(n2)。22.在下列有关关键路径的说法中错误的是_。 A.在 AOE网络中可能存在多条关键路径 B.关键活动不按期完成就会影响整个工程的完成时间 C.任何一个关键活动提前完成，整个工程将会提前完成 D.所有的关键活动都提前完成，整个工程将会提前完成（分数：1.00）A.B.C. D.解析：解析 在 AOE网络中可以存在多条关键路径。任何一个关键活动提前完成，只能影响它所在的关键路径，如果其他关键路径不能提前完成，整个工程不可能提前完成。只有所有的关键活动
35、都提前完成，整个工程才可能提前完成。如果任意一个关键活动发生延误，则会导致整个工程延误。23.图的简单路径是指_不重复的路径。 A.权值 B.顶点 C.边 D.边与顶点均（分数：1.00）A.B. C.D.解析：解析 图的路径是指图的一个顶点序列，由这些顶点构成的边属于图的边集合。而图的简单路径是指没有重复顶点的路径，所以选项 B正确。在定义简单路径时，边可以重复也可以不重复。24.下列说法中正确的是_。 A.如果有向图的邻接矩阵是对称矩阵，则该有向图一定是有向完全图 B.如果某个图的邻接矩阵不是对称矩阵，则该图一定是有向图 C.如果某个图的邻接矩阵是对称矩阵，则该图一定是无向图 D.邻接矩阵
36、表示法只存储了边的信息，没有存储顶点的信息（分数：1.00）A.B. C.D.解析：解析 在有向完全图中，如果从一个顶点 a到另一个顶点 b有路径，则反之从顶点 b到顶点 a必有路径，有向完全图的邻接矩阵一定是对称矩阵，对于无向图的邻接矩阵也有相同的结论。但反过来不一定成立，如果某个图的邻接矩阵是对称矩阵，则该图不一定是无向图，也不一定是有向完全图，这可用下图来解释。*一个图的邻接矩阵是不对称的，则它一定是有向图。此外，邻接矩阵法也存储了顶点信息，它包括了一个顶点信息向量和一个存储图中边的信息的邻接矩阵。25.在下列有关图的存储结构的说法中错误的是_。 A.用邻接矩阵存储一个图时所占用的存储空
37、间大小与图中的顶点个数有关，而与图的边数无关 B.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用 C.邻接矩阵只适用于稠密图(边数接近于顶点数的二次方)，邻接表只适用于稀疏图(边数远小于顶点数的二次方) D.对同一个有向图来说，邻接表中的边结点数与逆邻接表中的边结点数相等（分数：1.00）A.B. C.D.解析：解析 图的邻接表存储方法适用于存储有向图也适用于存储无向图，对于无向图中，同一条边将会有两个边结点。对于图的邻接矩阵表示方法，矩阵尺寸只与图中顶点个数有关，与边数无关，而其中非零元素个数与边数有关。26.假设一个有向图具有 n个顶点和 e条边，若该有向图采用邻接矩阵
38、存储，则删除与顶点 i相关联的所有边的时间复杂度是_；若该有向图采用邻接表存储，则删除与顶点 i相关联的所有出边的时间复杂度是 O(e)。 A.O(n) B.O(e) C.O(n+e) D.O(n2)（分数：1.00）A. B.C.D.解析：解析 对于图的邻接矩阵存储方法，要删除与某一顶点相关联的所有边，只需将其对应的行和列所有值设置为 0即可，时间复杂度为 O(n)；对于图的邻接表存储方法，要删除与某一顶点相关联的所有出边，则需要删除该顶点的边表中的所有边结点，时间复杂度为 O(e)。27.对于一个有向图，若一个顶点的度为 k1，出度为 k2，则对应逆邻接表中该顶点的入边表中的边结点数为_。
39、 A.k1 B.k2 C.k1-k2 D.k1+k2（分数：1.00）A.B.C. D.解析：解析 对于有向图，一个顶点的度等于其出度与入度之和。如果顶点的度为 k1，出度为 k2，则入度为 k1-k2。在逆邻接表中该顶点的入边表是所有进入该顶点的边组成的边链表，其中的边结点数等于该顶点的入度，即 k1-k2。28.设图有 n个顶点和 e条边，在采用邻接矩阵时，遍历图的顶点所需时间为_；在采用邻接表时，遍历图的顶点所需时间为 O(n+e)。 A.O(n) B.O(n2) C.O(e) D.O(ne)（分数：1.00）A.B. C.D.解析：解析 存储结构为邻接矩阵的图的遍历算法要对所有顶点都访
40、问一次，每次访问时为确定下一次要访问哪个顶点，需遍历该顶点的行向量，寻找该顶点的所有邻接顶点，所以遍历的时间复杂度为 O(n2)。而对于存储结构为邻接表的图的遍历算法也要对所有顶点访问一次，每次访问时为确定下一次要访问哪个顶点，需遍历该顶点的边链表，所以时间复杂度为 O(n+e)。29.一个有向图 G的邻接表存储如图所示，现按深度优先搜索方式从顶点 A出发执行一次遍历，所得到的顶点序列是_。（分数：1.00）A.B. C.D.解析：解析 题中的邻接表是针对有向图的，每个顶点的边链表是出边表。从顶点 1出发，通过深度优先搜索，如果访问顶点 2，再往前走可以顺序访问 3，5，再回溯到 1，访问 4
41、，因此答案 B是正确的。30.图的广度优先遍历算法中使用队列作为其辅助数据结构，那么在算法执行过程中每个顶点最多进队_次。 A.1 B.2 C.3 D.4（分数：1.00）A. B.C.D.解析：解析 根据图的广度优先遍历算法可知，遍历过程中每个顶点最多进队 1次。31.下列关于连通图的 BFS和 DFS生成树的高度论述正确的是_。 A.BFS生成树的高度小于 DFS生成树的高度 B.BFS生成树的高度小于或等于 DFS生成树的高度 C.BFS生成树的高度大于 DFS生成树的高度 D.BFS生成树的高度大于或等于 DFS生成树的高度（分数：1.00）A.B. C.D.解析：解析 BFS 遍历所
42、得到的生成树的高度不超过以遍历起始顶点为中心的图的层次数，而 DFS遍历所得到的生成树的高度与能前伸的最远距离有关，BFS 生成树的高度一定不会超过 DFS生成树的高度。32.若一个具有 N个顶点和 K条边的无向图是一个森林(NK)，则该森林必有_棵树。 A.K B.N C.N-K D.1（分数：1.00）A.B.C. D.解析：解析 设森林中有 m棵树，每棵树的结点个数分别是 n1，n 2，n m，分支数为 n1-1，n 2-1，n m-1，森林的各棵树的结点集合和边集合互不相交，则总顶点数 N=n1+n2+nm，总边数 K=(n1-1)+(n2-1)+(nm-1)=n1+n2+n-m=N-m，化简得 m=N-K。33.下面的说法中正确的是_。 A.图的一棵最小生成树的代价不一定比该图其他任何一棵生成树的代价小 B.带权连通图的最小生成树可能不唯一，但权值最小的边一定出现在解中 C.若带权连通图上各边上的权值互不相同，则该图的最小生成树是唯一的 D.一个带权连通图的最小生成树的权值之和不是唯一的（分数：1.00）A.B.C. D.解析：解析 带权连通图中的所有生成树中权值之和最小的生成树为该图的最小生成树，因此选项 A错误。
