数据结构 第五章练习题

第1题

含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（ ）。

• A. n/2
• B. n-1
• C. n
• D. n+1

答案：B. n-1

解析： 简单路径是指路径上不重复出现顶点的路径。在一个含有n个顶点的图中，一条简单路径最多能经过所有n个顶点一次。路径的长度等于其包含的边的数量。一条经过k个顶点的路径，其长度为k-1。因此，最长的简单路径会经过全部n个顶点，其长度为 n-1。

第2题

具有10个顶点的无向连通图最少有（）条边。

• A. 10
• B. 1
• C. 8
• D. 9

答案：D. 9

解析： 要使一个含有n个顶点的无向图保持连通，最少需要 n-1 条边。这种情况下，图的形态是一棵树，它能用最少的边连接所有顶点。对于10个顶点，最少需要 10 - 1 = 9 条边。

第3题

具有10个顶点的无向连通图最多有（）条边。

• A. 45
• B. 90
• C. 9
• D. 18

答案：A. 45

解析： 当一个无向图的边数达到最多时，它是一个完全图，即任意两个顶点之间都有一条边。对于n个顶点的无向完全图，其边数为 C(n, 2) = n * (n-1) / 2。对于10个顶点，最多有 10 * (10-1) / 2 = 10 * 9 / 2 = 45 条边。

第4题

一个具有n个顶点的无向图，最多有（）个连通分量。

• A. 1
• B. n-1
• C. n
• D. n＋1

答案：C. n

解析： 连通分量是图的极大连通子图。当图中没有任何边时，每个顶点自身都构成一个独立的连通分量，此时连通分量的数量达到最大值。因此，一个具有n个顶点的图，最多可以有n个连通分量。

第5题

对于下图所示无向图，顶点v₀到v₃的最短路径长度是（ ）。

• A. 1
• B. 2
• C. 3
• D. 4

答案：B. 2

解析： 这是一个无权图，最短路径指的是包含边数最少的路径。从v₀到v₃有两条长度为2的路径：

1. v₀ → v₁ → v₃
2. v₀ → v₂ → v₃ 因此，最短路径长度为2。

第6题

对于下图所示有向网图，顶点v₀到v₅的最短路径长度是（ ）。

• A. 12
• B. 11
• C. 7
• D. 8

答案：D. 8

解析： 这是一个带权有向图，需要使用Dijkstra算法求解单源最短路径。

1. 从v₀出发，v₀到v₀距离为0。
2. 更新v₀的邻居：dist(v₁) = 1, dist(v₂) = 5。
3. 选择当前最短路径顶点v₁，更新其邻居：dist(v₃) = 1 + 2 = 3。
4. 选择当前最短路径顶点v₃，更新其邻居：dist(v₄) = 3 + 7 = 10, dist(v₅) = 3 + 8 = 11。
5. 选择当前最短路径顶点v₂，更新其邻居：dist(v₄) = min(10, 5 + 1) = 6。
6. 选择当前最短路径顶点v₄，更新其邻居：dist(v₅) = min(11, 6 + 2) = 8。 最终v₀到v₅的最短路径长度为8，路径为 v₀→v₂→v₄→v₅。

第7题

若无向图G＝（V， E）有两个连通分量G₁＝（V₁， E₁）和G₂＝（V₂， E₂），则有（ ）。

• A.｜V₁｜＋｜V₂｜＝｜V｜， ｜E₁｜＋｜E₂｜＝｜E｜
• B.｜V₁｜＋｜V₂｜＜｜V｜， ｜E₁｜＋｜E₂｜＜｜E｜
• C.｜V₁｜＋｜V₂｜＝｜V｜， ｜E₁｜＋｜E₂｜＜｜E｜
• D.｜V₁｜＋｜V₂｜＜｜V｜， ｜E₁｜＋｜E₂｜＝｜E｜

答案：A.｜V₁｜＋｜V₂｜＝｜V｜， ｜E₁｜＋｜E₂｜＝｜E｜

解析： 图的连通分量是对图的顶点集和边集的一种划分。如果一个图G恰好由G₁和G₂这两个连通分量构成，那么G的顶点集是V₁和V₂的不交并集，G的边集是E₁和E₂的不交并集。因此，它们的顶点数和边数都是简单相加等于总数。

第8题

若有向图G＝（V， E）有两个连通分量G₁＝（V₁， E₁）和G₂＝（V₂， E₂），则有（）。

• A.｜V₁｜＋｜V₂｜＝｜V｜， ｜E₁｜＋｜E₂｜＝｜E｜
• B.｜V₁｜＋｜V₂｜＜＝｜V｜， ｜E₁｜＋｜E₂｜＜＝｜E｜
• C.｜V₁｜＋｜V₂｜＝｜V｜， ｜E₁｜＋｜E₂｜＜＝｜E｜
• D.｜V₁｜＋｜V₂｜＜＝｜V｜， ｜E₁｜＋｜E₂｜＝｜E｜

答案：B.｜V₁｜＋｜V₂｜＜＝｜V｜， ｜E₁｜＋｜E₂｜＜＝｜E｜

解析： 对于有向图，“连通分量”这个术语可能指弱连通分量或强连通分量。一个有向图可以分解为多个强连通分量以及连接这些分量的边和顶点。题目中表述“有两个连通分量”通常意味着“至少有两个”，而不是“恰好有两个且仅有两个”。因此，G₁和G₂可能只是图G中的两个分量，图中可能还存在不属于这两个分量的其他顶点和边。因此，它们的顶点/边之和小于等于G的总顶点/边数是最稳妥和普适的答案。

第9题

对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。

• A. 正确
• B. 错误

答案：B. 错误

解析： 只有当图是连通图时，从任意一个顶点出发进行一次DFS或BFS才能访问到所有顶点。如果图是非连通图（包含多个连通分量），一次遍历只能访问到起始顶点所在的那个连通分量中的所有顶点，无法访问其他分量的顶点。

第10题

对于下图所示无向图，从顶点v₀出发的深度优先遍历序列是（ ）。

• A. v₀v₂v₃v₁
• B. v₀v₃v₂v₁
• C. v₀v₂v₁v₃
• D. v₀v₁v₃v₂

答案：D. v₀v₁v₃v₂

解析： 深度优先遍历（DFS）的特点是“一路走到底，不撞南墙不回头”。从v₀出发，假设我们按顶点编号小的优先访问：

1. 访问 v₀。
2. 从v₀的邻居{v₁, v₂}中选v₁，访问 v₁。
3. 从v₁的邻居{v₀, v₃}中选v₃ (v₀已访问)，访问 v₃。
4. 从v₃的邻居{v₁, v₂}中选v₂ (v₁已访问)，访问 v₂。
5. 所有顶点访问完毕。 得到的序列是 v₀ → v₁ → v₃ → v₂。

第11题

对于下图所示无向图，从顶点v₀出发的广度优先遍历序列是（ ）。

• A. v₀v₂v₃v₁
• B. v₀v₃v₂v₁
• C. v₀v₂v₁v₃
• D. v₀v₁v₃v₂

答案：C. v₀v₂v₁v₃

解析： 广度优先遍历（BFS）的特点是“逐层扩散”。从v₀出发：

1. 访问 v₀，并将其邻居入队。假设按顶点编号大的优先入队（一种常见的约定），则队列为 [v₂, v₁]。
2. 队首 v₂ 出队，访问 v₂。将其未访问的邻居v₃入队，队列为 [v₁, v₃]。
3. 队首 v₁ 出队，访问 v₁。其邻居v₀和v₃都已被访问或在队列中。队列为 [v₃]。
4. 队首 v₃ 出队，访问 v₃。 得到的访问序列是 v₀ → v₂ → v₁ → v₃。

第12题

对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（ ）。

• A. n
• B. n²
• C. n-1
• D. (n-1)²

答案：B. n²

解析： 邻接矩阵是一个方阵，用于表示顶点之间的邻接关系。对于一个有n个顶点的图，需要一个 n×n 的矩阵来表示任意两个顶点之间是否有边。因此矩阵大小为 n * n = n²。

第13题

具有n个顶点e条边的无向图采用邻接矩阵存储，则零元素的个数为（）。

• A. e
• B. 2e
• C. n²-e
• D. n²-2e

答案：D. n²-2e

解析： 邻接矩阵的总元素个数是 n²。在无向图中，矩阵是对称的，每一条边 (u, v) 对应矩阵中两个非零元素：A[u,v] 和 A[v,u]。因此，e 条边共对应 2e 个非零元素（假设图中无自环，对角线为0）。所以，矩阵中零元素的个数为总数减去非零元素数，即 n² - 2e。

第14题

用邻接表存储图所用的空间大小（ ）。

• A. 与图的顶点数和边数都有关
• B. 只与图的边数有关系
• C. 只与图的顶点数有关
• D. 与边数的平方有关

答案：A. 与图的顶点数和边数都有关

解析： 邻接表存储结构包含两部分：

1. 一个大小为n（顶点数V）的顶点数组或列表。
2. 每个顶点后跟一个链表，表示从该顶点出发的边。所有链表结点的总数等于图中边的数量的两倍（对于无向图，2E）或一倍（对于有向图，E）。 因此，总空间复杂度为 O(V+E)，与顶点数和边数都有关。

第15题

具有n个顶点的无向图，其邻接表最多有（）个边表结点。

• A. n²
• B. n(n-1)
• C. n(n+1)
• D. n(n-1)/2

答案：B. n(n-1)

解析： 邻接表中的边表结点总数等于图中所有顶点的度数之和。根据握手定理，无向图中所有顶点的度数之和等于边数的2倍（2e）。 当图为完全图时，边表结点数最多。n个顶点的无向完全图有 e = n(n-1)/2 条边。 因此，最多的边表结点数为 2e = 2 * [n(n-1)/2] = n(n-1)。

第16题

带权有向图G采用邻接矩阵存储，则顶点i的入度等于邻接矩阵中（ ）。

• A. 第i行非0的元素之和
• B. 第i列非0的元素之和
• C. 第i行非0且非∞的元素个数
• D. 第i列非0且非∞的元素个数

答案：D. 第i列非0且非∞的元素个数

解析： 在有向图的邻接矩阵A中，A[j][i]的值表示从顶点j到顶点i的边的权重。

• 入度：指向顶点i的边的数量。这对应于邻接矩阵的第i列中，值不为0（对无权图）或不为∞（对带权图，∞通常表示无边）的元素个数。
• 出度：从顶点i出发的边的数量，对应第i行。

第17题

假设一个有向图具有n个顶点e条边，采用邻接矩阵存储，则删除与顶点i相关联的所有边的时间复杂度是（ ）。

• A. O(n)
• B. O(e)
• C. O(n＋e)
• D. O(n＊e)

答案：A. O(n)

解析： 删除与顶点i相关联的所有边，意味着删除所有从i出发的边（出边）和所有指向i的边（入边）。

• 删除出边：需要将邻接矩阵的第i行所有元素置为0（或∞），这需要遍历n个元素，时间复杂度为O(n)。
• 删除入边：需要将邻接矩阵的第i列所有元素置为0（或∞），这需要遍历n个元素，时间复杂度为O(n)。 总的时间复杂度为 O(n) + O(n) = O(n)。

第18题

假设一个有向图具有n个顶点e条边，采用邻接表存储，则删除与顶点i相关联的所有边的时间复杂度是（ ）。

• A. O(n)
• B. O(e)
• C. O(n＋e)
• D. O(n＊e)

答案：C. O(n＋e)

解析：

• 删除出边：只需找到顶点i的边表，并将其清空。这需要 O(degree_out(i)) 的时间，其中degree_out(i)是i的出度。
• 删除入边：这比较复杂。因为标准的邻接表只记录了出边，为了删除所有指向i的边，我们必须遍历所有顶点的邻接表，检查其中是否有指向i的结点，并将其删除。这个过程需要遍历整个邻接表（所有n个顶点数组和所有e条边对应的结点），时间复杂度为O(n+e)。 总的时间复杂度由较慢的操作决定，即O(n+e)。

第19题

图的广度优先遍历算法用到辅助队列，每个顶点最多进队（）次。

• A. 1
• B. 2
• C. 3
• D. 不确定

答案：A. 1

解析： 在广度优先遍历（BFS）中，通常会使用一个visited数组或集合来记录已经访问过或已经加入队列的顶点。一个顶点在被加入队列之前，会先检查它是否已被访问。只有未被访问的顶点才会被加入队列，并在加入后立刻标记为已访问。因此，每个顶点最多只会进队一次，也最多出队一次。

第20题

无向图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. abecdf
• B. acfebd
• C. aebcfd
• D. Daedfcb

答案：D. aedfcb

解析： 深度优先遍历（DFS）遵循“深入”的原则。一个可能的遍历过程如下（假设邻居按字母顺序的倒序来选择）：

1. 从 a 出发，访问 a。
2. 从a的邻居{e, c, b}中选择 e，访问 e。
3. 从e的邻居{d, b, a}中选择 d (a已访问)，访问 d。
4. 从d的邻居{f, e}中选择 f (e已访问)，访问 f。
5. 从f的邻居{d, c}中选择 c (d已访问)，访问 c。
6. c的邻居{f, a}均已在访问路径上或已访问，回溯到f。
7. f的邻居均已访问，回溯到d。
8. d的邻居均已访问，回溯到e。
9. 从e的邻居{d, b, a}中选择 b (a,d已访问)，访问 b。
10. b的邻居{e, a}均已访问，回溯。所有顶点访问完毕。 得到的序列是 a, e, d, f, c, b，与选项D aedfcb 匹配。