计算机科学测验 - III: 第 2 部分

答案： (a) T(n) = O(n)

说明

给定递归关系

T(n) = 2T(n/2) + n ... (i)

使用主定理

T(n) = aT(n/b) + f(n) ... (ii)

比较 (i) 和 (ii)，我们得到

a = 2,

b = 2, 和

f(n) = n

情况 I

f(n) = O(n^log_b^a)

n = O(n^log₂²)

n = O(n^1)

n = O(n)，等式成立

因此，T(n) = O(n)。所以，(a) 是正确答案。

答案： (c) 7

解释： 举行 5 场比赛，将马匹分成 5 组。取前五场比赛的获胜者，举行第六场比赛；这场比赛的获胜者将是 25 匹马中最快的。

现在举行第七场比赛，参赛马匹如下。

1) 第六场比赛的第二名和第三名马匹

2) 选择第六场比赛中并列第一的组的第二快和第三快的马。

3) 选择在第六场比赛中获得第二快的组的动物。

第七场比赛中最快的马和第二快的马分别是所有 25 匹马中的第二快和第三快的马。.

因此，(c) 是正确答案。

答案： (d) O(1)

说明

我们只需要比较任意 3 个元素。这三个元素中的中间元素将是既非最大值也非最小值的一个。由于比较次数是常数，因此时间复杂度为 (1)。

因此，(d) 是正确答案。

答案： (d) 循环双链表

说明

无法使用单链表、双链表和循环单链表来实现给定的想法，因为我们没有指向最后一个节点的指针。要连接两种类型的列表，我们需要遍历其中一个列表才能访问最后一个节点，这需要 O(n) 的时间。

循环双链表可以在常数时间 O(1) 内连接。我们只需要执行正确的代码序列。

设 list1 和 list2 的 front 和 last 指针分别为 front1 和 last1，以及 front2 和 last2。

last1 -> next = front2

front2 -> prev = last1

front1 -> prev = last2

last2 -> next = front

我们可以将新节点的指针重命名为 front = front1 和 last = last2。

答案： (d) O(2ⁿ)、O(logn)、O(n²)、O(n logn)

说明

汉诺塔是一个数学谜题，其中我们有 n 个不同大小的磁盘和三个杆：起始杆、结束杆和辅助杆。谜题的目标是将所有磁盘从起始杆移动到结束杆，规则是

1. 一次只能移动一个盘子，并且
2. 较大的圆盘不能放在较小的圆盘之上。

此问题的时间复杂度为 O(2ⁿ)。

在最坏情况下，二分搜索的时间复杂度为 O(logn)。

在最坏情况下，堆排序的时间复杂度仍为 O(n logn)，但快速排序的时间复杂度变为 O(n²)。

答案： (b) I、II 和 III

说明

第一条陈述是正确的。最大堆中的叶节点总是包含最小的元素。因此，我们必须搜索每个叶节点中的最小值。最坏情况复杂度为 O(n)。

第二条陈述也是正确的。最大元素始终位于顶部，第二大元素始终是根节点的子节点。

第三条陈述是正确的，因为构建最大堆需要 O(n) 时间。

第四条陈述是错误的，因为将最大堆转换为二叉搜索树需要 O(n logn) 时间。

因此，(b) 是正确答案。

答案： (d) 插入排序

说明

在最佳情况下，插入排序的时间复杂度变为 O(n)，因为它会比较元素并将它们插入到正确的位置。因此，在对几乎已排序的数组进行排序时，它不会花费更多时间。另一方面，堆排序和归并排序将花费 O(n logn) 时间，而快速排序将花费 O(n²)，这是最坏情况。

答案： (b) 选择排序

解释： 选择排序选择最小值或最大值，并将其与正确位置的元素交换。它执行的交换次数不超过 O(n)。在所需交换次数方面，选择排序表现最佳。

答案： (b) 使用从右到左的数组遍历在线性时间内解决

说明

该方法是从右到左扫描数组元素，同时计算迄今为止已达到的最大元素个数。每当最大值发生变化时，就打印该值。

为了将该概念付诸实践，请执行以下操作

1. 我们从最后一个索引位置开始。它的右侧永远没有元素。因此，最后一个位置永远是领导者。
2. 之后，我们继续迭代数组，直到索引位置 = 0。我们始终监控最大值。
3. 每次遇到比之前遇到的最高最大值更大的最大值时，我们就打印或保存该值，因为它是领导者。

这可以在线性时间内完成。因此，(b) 是正确答案。

答案： (b) G 中割集中的所有边都是最大权重

说明

以以下图为例

有三条边是最大权重。边 ef 将成为最小生成树的一部分。

割集定义为一组边，移除它们会断开图。

选项 A：此陈述是错误的，因为我们不能得出每条边的权重都是唯一的。尽管边可以具有相同的权重。

选项 B：割集 {ab, ac} 包含两条最大权重的边。因此，选项 (b) 是正确的。

选项 C：此陈述是错误的。这里，我们可以在边 ab 和 ac 之间进行选择。因此，我们不能保证唯一性。

选项 D：此陈述也是错误的。边 e 可能成为环的一部分。

答案： (b) 堆

说明

堆和优先队列都是特别有吸引力的数据结构，它们允许

• 将具有优先级的组件添加到堆中。
• 从堆或优先队列中移除最高优先级的组件并返回。
• 在不删除的情况下访问具有最高优先级的峰值元素。

维护一个组件列表并搜索其中具有最高优先级的组件是创建堆或优先队列数据类型的简单方法。这使得 Dijkstra 在无权图上的最短路径算法的实现时间为 O(n)。

答案： (b) 只有 II

说明

Bellman-Ford 最短路径算法用于确定单源最短路径。因此，它只能检测可从特定源到达的环，而不能找到不可从给定源到达的负权重环。

考虑一个不连通的情况，即从源点无法到达负权重环。如果存在可从源点到达的负权重环，则在 (顶点数- 1) 次迭代之后，算法将检测到它。

因此，说它总能找到负权重环是错误的。因此，陈述 I 是错误的，陈述 II 是正确的。

答案： (b) 从 W 到每个图顶点的最短路径

说明

从节点 W 进行 BFS 遍历形成的树给出从 W 到所有节点的最短路径。在无权图中，BFS 始终找到从源点到其他所有顶点的最短路径。

因此，(b) 是正确答案。

答案： (a) 只有 I

说明

最短路径可能会改变。原因是任何一对边，例如 a 和 b，在不同的路径中可能包含不同数量的边。例如，假设 a 和 b 之间的最短路径有 4 条边，权重为 12。允许另一条路径有两条边，权重为 17。增加每条边权重 5 后最短路径的权重现在是 12 + 4*5 = 32。另一条路径的权重增加了 2*5，使其变为 17+10 = 27。因此，最短路径变成了具有 27 权重的另一条路径。

最小生成树没有变化。请记住，在 Kruskal 算法中，边首先被排序。如果所有权重都增加，边的顺序不会改变。

答案： (c) 34

说明

使用 Kruskal 算法，我们首先按降序对所有边进行排序。然后尝试选择权重最小的边，并且必须确保避免生成树中的任何类型的环路。

答案： (b) 动态规划

说明

Floyd Warshall 算法可以解决所有对的最短路径问题。该问题旨在找出有向图的每对顶点之间的最短距离。动态规划是其基础。因此，(b) 是正确答案。

答案： (a) 18775

说明

计算乘法成本的公式：m[i, j] 表示将矩阵 i 到 j 相乘的成本。

m[i, j] = { 0 如果 (i == j)}

m[i, j] = { min[m[i, k] + m[k+1, j] + P_i-1 P_k P_j] 如果 (i < j)}

k 的范围为 i <= k < j。我们将计算每个 k 值的成本并选择最小成本。

我们使用矩阵维度创建了这个表

乘以一个矩阵的成本为零，这就是为什么我们在相应的单元格中填充零。

现在，计算 m[1, 2]。k 的可能值为 1。

对于 k = 1

m[1, 2] = m[1, 1] + m[2, 2] + P₀* P₁* P₂

= 0 + 0 + 5 * 10 * 35

= 1750

类似地，我们可以找到 m[2, 3]、m[3, 4] 和 m[4, 5] 的成本。

现在，计算 m[1, 3]。k 的可能值为 1、2

对于 k = 1

m[1, 3] = m[1, 1] + m[2, 3] + P₀ * P₁ * P₃

= 0 + 5250 + 5 * 10 * 15

= 0 + 5250 + 750

= 6000

对于 k = 2

m[1, 3] = m[1, 2] + m[3, 3] + P₀ * P₂ * P₃

= 1750 + 0 + 5 * 35 * 15

= 4375

我们得到了 k = 2 的最小成本。

类似地，我们可以计算 m[2, 4] 和 m[3, 4] 的成本。

完整的表格如下所示

乘矩阵的成本为 18750。

答案： (b) L(M, N) 的行主序和列主序都可以用来计算 l(i, j) 的值。

说明

选项 A 是错误的，因为不必将 L[M, N] 的所有元素初始化为 0。我们只在第一行和第一列填充零。

选项 B 是正确的。通过以行主序或列主序进行计算，我们可以执行所需的计算。

选项 C 是错误的。它否定了选项 B，这是不正确的。

选项 D 是错误的，因为要计算 l[i, j] 的值，我们只需要 l[i-1, j]、l[i, j-1] 和 l[i-1, j-1] 的值。条件 p<r 或 q<s 并不能完全满足条件。

答案： (c) A - (iii), B - (iv), C - (i), D - (ii)

说明

• Huffman 编码是一种无损数据压缩算法。输入字符被赋予可变长度的代码，其长度由相应字符的频率决定。它是基于贪心方法的。
• Floyd Warshall 算法可以解决所有对的最短路径问题。该问题旨在找出有向图的每对顶点之间的最短距离。动态规划是其基础。
• 选择排序方法通过重复选择未排序部分中值最小的元素来对数组进行排序，同时仍考虑升序。在选择排序的每次迭代中，选择最小的条目（按升序）并将其重新定位到未排序子数组的开头。减而治之是该概念背后的理论。
• 分而治之概念是称为归并排序的排序算法的基础。该算法将数组分成两个相等的部分，然后以排序的方式合并它们。

因此，选项 (c) 是正确答案。

答案： (a) 24

说明

问题中提到的属性与 Huffman 编码相同。

我们这里将遵循两个基本规则

i. 为了创建树，我们将选择频率最低的字母，并以自底向上的方式创建 Huffman 树。

ii. 我们将二元 1 分配给节点的右边缘，将二元 0 分配给节点的左边缘。

为了分配代码，我们将从根到包含字母的所有叶节点遍历树。

分配给每个字母的二进制代码

a - 0100, 长度 = 4

b - 00, 长度 = 2

c - 0101, 长度 = 4

d - 1, 长度 = 1

e - 011, 长度 = 3

字符串的最短二进制长度 = 4 * 1 + 2 * 3 + 4 * 1 + 1 * 4 + 3 * 2

= 4 + 6 + 4 + 4 + 6 = 24

因此，(a) 是正确答案。