数据结构题型

选择题

(3) 对于顺序查找（Sequential search），哪项描述正确？

(A) 最佳、平均和最坏情况的渐进时间复杂度是相同的。
(B) 最佳情况的渐进时间复杂度优于平均和最坏情况。
(C) 最佳和平均情况的渐进时间复杂度优于最坏情况。
(D) 最佳情况的渐进时间复杂度优于平均情况，平均情况优于最坏情况。

正确答案: (B) 最佳情况的渐进时间复杂度优于平均和最坏情况。

解释：

最佳情况：在第一次比较时找到目标元素，时间复杂度为 $ O(1) $。
平均情况：检查大约一半的元素，时间复杂度为 $ O(n) $。
最坏情况：检查所有元素，时间复杂度为 $ O(n) $。因此，最佳情况的渐进时间复杂度优于平均和最坏情况。

(4) 我们使用父指针表示法（Parent pointer representation）来解决以下哪种问题？

(A) 最短路径问题
(B) 一般树的遍历
(C) 等价类问题
(D) 精确匹配查询

正确答案: (C) 等价类问题

解释：

父指针表示法常用于解决并查集（Union-Find）中的等价类问题，特别是在快速查找某个元素的代表元时。

(5) 减少基于磁盘的程序运行时间的最有效方法是：

(A) 改进基本操作。
(B) 最小化磁盘访问次数。
(C) 消除递归调用。
(D) 减少主存的使用。

正确答案: (B) 最小化磁盘访问次数

解释：

磁盘访问是程序运行中的主要耗时操作，减少磁盘访问次数可以显著提高性能。

(9) 2-3 树相比于二叉搜索树（BST）的最重要优势是：

(A) 2-3 树的节点更少。
(B) 2-3 树的分支因子更高。
(C) 2-3 树是高度平衡的。
(D) 以上都不是。

正确答案: (C) 2-3 树是高度平衡的

解释：

2-3 树保持高度平衡，所有叶子节点在同一层，这使得它的搜索、插入、删除操作更有效率，而普通的二叉搜索树可能会变得不平衡。

(10) 哪项最能表征伸展树（Splay tree）的性能？

(A) 所有操作都需要 $ O(n) $ 时间。
(B) 对于 $ m > n $，$ m $ 次操作总共需要 $ O(m n) $ 时间。
(C) 所有操作都需要 $ O(n) $ 时间。
(D) 以上都不是。

正确答案: (B) 对于 $ m > n $，$ m $ 次操作总共需要 $ O(m n) $ 时间。

解释：

伸展树是一种自调整的二叉搜索树，能够保证一系列 $ m $ 次操作在 $ O(m n) $ 时间内完成，摊还时间复杂度优于单次操作的最坏情

计算复杂度题型

求以下代码片段在平均情况下的渐进时间复杂度 $ $。假设所有变量都是 int 类型。（9分）

(1)

sum = 0;
for (i = 0; i < 3; i++) // 外层循环执行3次
    for (j = 0; j < n; j++) // 内层循环执行 n 次
        sum++;

解答：

外层循环执行 3 次，内层循环执行 n 次。因此，总共的 sum++ 操作次数为 $ 3 n $，即 3n。
因此，渐进时间复杂度为：
$ (n) $

(2) 假设数组 A 包含从 0 到 $ n-1 $ 的随机排列。

sum = 0;
for (i = 0; i < n; i++) // 外层循环执行 n 次
    for (j = 0; A[j] != i; j++) // 内层循环执行，直到找到 A[j] == i
        sum++;

解答：

内层循环的执行次数取决于 A[j] 和 i 的相对位置。A 是一个随机排列，平均情况下，内层循环在每次遍历中大约需要检查一半的元素，即 $ $ 次。
因此，外层循环执行 $ n $ 次，每次内层循环执行大约 $ $ 次。
总的 sum++ 操作次数为 $ n $，即 $ $。
因此，渐进时间复杂度为：
$ (n^2) $

(3)

sum = 0;
if (EVEN(n)) // 如果 n 是偶数
    for (i = 0; i < n; i++) // 执行 n 次循环
        sum++;
else
    sum = sum + n; // 单次操作

解答：

如果 $ n $ 是偶数，for 循环将执行 $ n $ 次，复杂度为 $ O(n) $。
如果 $ n $ 是奇数，则仅执行一次赋值操作 sum = sum + n;，复杂度为 $ O(1) $。
由于 $ n $ 的奇偶性各占一半，平均情况下，该代码的复杂度为 $ O(n) $。
因此，渐进时间复杂度为：
$ (n) $

构建堆（注意和插入堆是不一样的）

一种是有一个数组直接构建，是接近于O(n)的，另外一种则是适合于动态输入的情况，复杂度并不足够优秀。

5. 展示通过在下列存储在数组中的值上运行 buildheap（构建堆）后得到的最大堆。数组中的值如下：
$ 44, 66, 33, 88, 77, 55, 22 $
（10分）

步骤：构建最大堆的过程使用自底向上的方法，从最后一个非叶节点开始调整。对于给定的数组，首先要找出所有非叶节点，并进行堆调整（heapify）。最大堆要求每个父节点的值都大于或等于其子节点的值。

初始数组：

$ 44, 66, 33, 88, 77, 55, 22 $
索引从 0 开始，树结构如下所示：

     44
    /  \
  66    33
 /  \   / \
88  77 55 22

步骤 1：从第一个非叶节点开始调整

从最后一个非叶节点开始调整：
节点 33（索引 2），其子节点为 55 和 22。由于 55 > 33，交换这两个值。
1
2
3
4
5
44
/ \
66 55
/ \ / \
88 77 33 22
调整节点 66（索引 1）：
节点 66 的子节点是 88 和 77。由于 88 > 66，交换这两个值。
1
2
3
4
5
44
/ \
88 55
/ \ / \
66 77 33 22
调整根节点 44（索引 0）：
节点 44 的子节点是 88 和 55。由于 88 > 44，交换这两个值。
1
2
3
4
5
88
/ \
44 55
/ \ / \
66 77 33 22
继续调整节点 44，它的子节点是 66 和 77。由于 77 > 44，交换这两个值。
1
2
3
4
5
88
/ \
77 55
/ \ / \
66 44 33 22

最终的最大堆：

     88
    /  \
  77    55
 /  \   / \
66  44 33 22

数组表示的最大堆：

$ 88, 77, 55, 66, 44, 33, 22 $

答案：

通过运行 buildheap 后，最终的最大堆数组为： $ 88, 77, 55, 66, 44, 33, 22 $

最短路题型

Dijkstra 算法通常是求解单源最短路中最快的算法，但它无法处理存在负权边的情况。Dijkstra 本质上是一种贪心算法，通过不断调整每个点的 “当前距离” 最终得到最优结果，

dijkstra的算法思想是从以上最短距离数组中每次选择一个最近的点，将其作为下一个点，然后重新计算从起始点经过该点到其他所有点的距离，更新最短距离数据。已经选取过的点就是确定了最短路径的点，不再参与下一次计算。