华南理工大学数据结构11B

这也是一张很好的试卷，看来就是从这一年开始试卷开始有了质的飞跃。

选择题

问题：

对于一个顺序存储的线性表 $(a_1, a_2, \ldots, a_n)$，当删除任意一个节点时，平均需要移动的节点数是以下选项中的哪一个？
(A) $ n $
(B) $ n/2 $
(C) $ (n-1)/2 $
(D) $ (n+1)/2 $

解答：

当从顺序存储的线性表中删除一个节点时，后续的节点需要依次向前移动以填补被删除节点的位置。例如：

如果删除第一个节点，需要移动 $ n-1 $ 个节点。
如果删除最后一个节点，则无需移动节点（移动 0 个节点）。
如果删除中间某个节点，例如第 $ k $ 个节点，需要移动 $ n-k $ 个节点。

计算平均移动节点数：

假设每个节点被删除的概率是相等的（均匀分布），则对于任意一个节点 $ a_k $：

被删除后需要移动的节点数为 $ n-k $。

所有节点被删除时需要移动的节点总数为：
$ = (n-1) + (n-2) + + 1 + 0 $
这是一个等差数列，其和为：
$ S = $

平均移动的节点数为：
$ = = = $

答案：
(C) $ (n-1)/2 $

解释：

移动原因： 删除节点后，后续节点需要向前移动以保持线性表的顺序。
等概率假设： 假设每个节点被删除的概率是相同的，计算时需要对所有可能的移动情况取平均值。
平均计算： 根据等差数列的性质，计算出平均需要移动的节点数为 $ (n-1)/2 $。

问题：
以下哪个选项是正确的？

一棵普通树可以转换为二叉树，并且根节点同时拥有左子节点和右子节点。
在二叉搜索树（BST）中，节点可以通过先序遍历得到一个排序的序列。
在二叉搜索树（BST）中，任意节点的左子节点小于右子节点，但在堆（Heap）中，任意节点的左子节点可能小于也可能大于右子节点。
堆必须是满二叉树。

解答：

(A) 错误：
普通树可以转换为二叉树，但转换规则是：

左子节点表示该节点的第一个子节点。
右子节点表示该节点的兄弟节点。
转换后的二叉树不一定保证根节点有左子节点和右子节点。

(B) 错误：
在二叉搜索树（BST）中，中序遍历的结果是排序的序列，而不是先序遍历。先序遍历的顺序是按照“根-左-右”，无法保证节点按值排序。

(C) 正确：
在二叉搜索树（BST）中，左子节点的值总是小于其父节点，而右子节点的值总是大于其父节点。
而在堆（Heap）中，堆的性质只要求节点的值满足“堆序性质”，即：

最大堆：父节点的值大于等于子节点的值。
最小堆：父节点的值小于等于子节点的值。
堆没有要求左子节点和右子节点之间的大小关系，因此左子节点可能小于或大于右子节点。

(D) 错误：
堆必须是完全二叉树（Complete Binary Tree），而不是满二叉树（Full Binary Tree）。

完全二叉树：除了最后一层，所有层都被完全填满，最后一层的节点从左到右连续填充。
满二叉树：所有层的节点都被完全填满。

答案：
(C) 在二叉搜索树（BST）中，任意节点的左子节点小于右子节点，但在堆（Heap）中，任意节点的左子节点可能小于也可能大于右子节点。

解释：

1. 普通树转换成二叉树的规则并不保证根节点有两个子节点。
1. BST 排序使用中序遍历而非先序遍历。
1. 描述正确，堆中对子节点的顺序无要求。
1. 堆是完全二叉树，不是满二叉树。

问题：
以下哪个选项是错误的？

在图的遍历过程中，每个顶点只被访问一次。
图的遍历有两种方法：深度优先搜索（DFS）和广度优先搜索（BFS）。
图的深度优先搜索（DFS）不适合有向图。
图的深度优先搜索（DFS）是一个递归过程。

解答：

(A) 正确：
无论是深度优先搜索（DFS）还是广度优先搜索（BFS），在遍历过程中，每个顶点都会被访问一次，并标记为“已访问”，防止重复访问。

(B) 正确：
图的遍历有两种主要方法：

深度优先搜索（DFS）：从起始顶点开始，沿着一个方向尽可能深入，直到无法继续为止，然后回溯并探索其他路径。
广度优先搜索（BFS）：从起始顶点开始，逐层访问所有相邻顶点，依次扩展到更远的顶点。

(C) 错误：
深度优先搜索（DFS）不仅适用于无向图，也适用于有向图。在有向图中，DFS 可以遍历所有可以到达的顶点，还能用于检测强连通分量、拓扑排序等问题。

(D) 正确：
深度优先搜索（DFS）本质上是一个递归过程，递归地访问每个顶点的邻接顶点，直到所有路径都被探索完。也可以用栈实现非递归版本，但通常使用递归方法更为直观。

答案：
(C) 图的深度优先搜索（DFS）不适合有向图。

解释：

1. 和 (B) 描述了图遍历的基本特性，是正确的。
1. 是错误的，因为 DFS 同样适用于有向图。
1. 描述了 DFS 的递归特性，是正确的。

算法分析

问题：

为以下代码段的平均情况确定渐近时间复杂度 $\Theta$。假设所有变量均为整数类型。

代码分析：

(1) 代码段：

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

分析：

外循环运行 $5$ 次，每次内循环运行 $n$ 次。
总的执行次数为： $ T(n) = 5 n = (n) $

(2) 代码段：

sum = 0;
for (i = 1; i <= n; i++) // 外循环从 1 到 n
  for (j = n; j >= i; j--) // 内循环从 n 到 i
    sum++;

分析：

外循环运行 $n$ 次。
对于第 $i$ 次迭代，内循环从 $j = n$ 到 $j = i$，执行次数为 $(n - i + 1)$。
总执行次数为： $ T(n) = _{i=1}^n (n - i + 1) $ 化简求和公式： $ T(n) = n + (n-1) + (n-2) + + 1 = $ 因此，时间复杂度为： $ T(n) = (n^2) $

(3) 代码段：

sum = 0;
if (EVEN(n)) // 如果 n 是偶数
  for (i = 0; i < n; i++) // 循环运行 n 次
    sum++;
else // 如果 n 是奇数
  sum = sum + n; // 直接赋值

分析：

对于偶数 $n$：循环运行 $n$ 次，时间复杂度为 $\Theta(n)$。
对于奇数 $n$：只进行一次赋值操作，时间复杂度为 $\Theta(1)$。
在平均情况下，无论 $n$ 是偶数还是奇数，渐近复杂度都是由较高的复杂度主导。因此： $ T(n) = (n) $

答案：

$\Theta(n)$
$\Theta(n^2)$
$\Theta(n)$

解释：

1. 外循环运行常数次，内循环运行 $n$ 次，因此为 $\Theta(n)$。
1. 外循环和内循环叠加成等差数列的求和，结果为 $\Theta(n^2)$。
1. 由偶数或奇数情况决定复杂度，主要受 $\Theta(n)$ 支配。

程序填空

问题描述：

修改二分查找函数，使其在找不到 $ K $ 时，返回数组中比 $ K $ 大的最小元素的位置；若数组中所有元素都小于 $ K $，则返回 ERROR。
在双向循环链表中，完成将新节点 $ s $ 插入到指针 $ q $ 所指向节点之后的操作。
计算完全二叉树中 $ k $ 个节点的树高。

(1) 修改二分查找函数：

完整代码：

int newbinary(int array[], int n, int K) {
    int l = -1; // 左边界，初始为数组范围外
    int r = n;  // 右边界，初始为数组范围外
    while (l + 1 != r) { // 当左右边界相邻时停止
        int i = (l + r) / 2; // 查找中间位置
        if (K < array[i]) {
            r = i; // K 在左半部分
        } else if (K == array[i]) {
            return i; // 找到 K
        } else {
            l = i; // K 在右半部分
        }
    }
    // K 不在数组中，或者数组中所有元素都小于 K
    if (r < n) { // 数组中存在比 K 大的最小值
        return r;
    } else {
        return ERROR; // 数组中所有元素都小于 K
    }
}

解释：

初始化边界：
- $ l = -1 $：表示左边界在数组之外。
- $ r = n $：表示右边界在数组之外。
循环逻辑：
- 不断缩小 $ l $ 和 $ r $ 的范围，最终 $ r $ 指向比 $ K $ 大的最小值。
条件判断：
- $ r < n $：如果 $ r $ 在数组范围内，返回 $ r $ 指向的位置。
- 否则，返回 ERROR。

(2) 双向循环链表插入节点：

完成的代码：

s->prior = q;
s->next = q->next;
q->next->prior = s;
q->next = s;

解释：

设置新节点 $ s $ 的前驱和后继指针：
- $ s->prior = q $：新节点的前驱是 $ q $。
- $ s->next = q->next $：新节点的后继是 $ q $ 的后继节点。
更新其他节点的指针：
- $ q->next->prior = s $：将 $ q $ 的后继节点的前驱指向 $ s $。
- $ q->next = s $：将 $ q $ 的后继指向 $ s $。

(3) 完全二叉树的高度：

公式：

完全二叉树的高度为：
$ h = _2(k + 1) $
如果以 $ 1 $ 为根节点，树高从 $ 1 $ 开始。

解释：

对于完全二叉树，第 $ h $ 层最多有 $ 2^{h-1} $ 个节点。
若总共有 $ k $ 个节点，树高 $ h $ 满足：
$ 2^{h-1} k < 2^h $
即：
$ h = _2(k + 1) $

证明题

问题：

证明交换排序算法（冒泡排序、选择排序、插入排序等）在平均情况和最坏情况下的时间复杂度是 $\Theta(n^2)$。

解答与分析：

1. 交换排序算法的本质：

交换排序算法通过比较和交换两个元素的位置，使得列表逐步趋于有序。这包括：

冒泡排序（Bubble Sort）：通过相邻元素的交换逐步将最大值或最小值移动到正确位置。
选择排序（Selection Sort）：通过寻找当前未排序部分的最小值或最大值，并将其交换到正确位置。
插入排序（Insertion Sort）：逐步将元素插入到已排序部分的适当位置。

2. 时间复杂度分析：

假设列表 $L$ 含有 $n$ 个元素。以下是两种情况下的操作次数：

（1）最坏情况：

最坏情况下，列表完全逆序。
对于冒泡排序和插入排序，每次迭代需要逐个比较并交换（或插入）元素：
- 第 1 次需要比较 $n-1$ 次，
- 第 2 次需要比较 $n-2$ 次，
- ...
- 第 $n-1$ 次需要比较 1 次。
总的比较次数为： $ T(n) = (n-1) + (n-2) + + 1 = $
因此，最坏情况下的时间复杂度为： $ T(n) = (n^2) $

（2）平均情况：

对于所有可能的输入序列，每个序列需要的操作次数也在 $\frac{n(n-1)}{2}$ 的数量级上。
以冒泡排序为例，平均情况下，约有一半的元素对需要交换： $ = $
平均情况下的比较次数仍为 $\frac{n(n-1)}{2}$，因此平均复杂度为： $ T(n) = (n^2) $

3. 证明关键点：

比较对的数量：
在一个含 $n$ 个元素的列表中，有 $\binom{n}{2} = \frac{n(n-1)}{2}$ 个不同的元素对。每对元素在排序过程中都可能被比较一次，因此比较次数的上限为 $\frac{n(n-1)}{2}$。
冒泡排序和插入排序：
- 在最坏情况下，每次都需要比较和交换最多的元素对。
- 在平均情况下，约有一半的元素对需要被比较和交换。
选择排序：
- 每次需要从剩余的未排序部分选择最小值，比较次数固定为 $\frac{n(n-1)}{2}$。

总结：

交换排序算法在最坏情况和平均情况下的时间复杂度均为 $\Theta(n^2)$。

答案：

最坏情况：$\Theta(n^2)$
平均情况：$\Theta(n^2)$

解释：
无论是冒泡排序、选择排序还是插入排序，核心操作的时间复杂度取决于比较和交换的次数，这在最坏和平均情况下都是数量级为 $\frac{n(n-1)}{2}$。

堆

问题描述：

对以下的堆进行操作，并通过图示表示结果：

在堆中插入 40。
从堆中删除 30。
从堆中删除 28。

哈夫曼树

问题：

我们有如下字母及其频率表：

Letter	Frequency
a	5
b	25
c	3
d	6
e	10
f	11
g	36
h	4

需要完成的任务：

根据频率构建霍夫曼树，并给出每个字母的霍夫曼编码。
计算每个字母的期望比特长度（即加权平均编码长度）。
给出一个示例说明霍夫曼编码的优点。

答案：

1. 构建霍夫曼树

步骤：

从最小频率开始，将频率最低的两个字母合并成一个节点，重复此过程，直到形成一棵树。
合并过程如下：
- 初始频率表（字母 + 新节点用数字标记）： {c: 3, h: 4, a: 5, d: 6, e: 10, f: 11, b: 25, g: 36}
- 合并频率最低的 c (3) 和 h (4)，新节点频率为 7： {7: c+h, a: 5, d: 6, e: 10, f: 11, b: 25, g: 36}
- 合并 a (5) 和 d (6)，新节点频率为 11： {7: c+h, 11: a+d, e: 10, f: 11, b: 25, g: 36}
- 合并 7 (c+h) 和 e (10)，新节点频率为 17： {17: (c+h)+e, 11: a+d, f: 11, b: 25, g: 36}
- 合并 11 (a+d) 和 f (11)，新节点频率为 22： {17: (c+h)+e, 22: (a+d)+f, b: 25, g: 36}
- 合并 17 ((c+h)+e) 和 22 ((a+d)+f)，新节点频率为 39： {39: ((c+h)+e)+((a+d)+f), b: 25, g: 36}
- 合并 b (25) 和 g (36)，新节点频率为 61： {39: ((c+h)+e)+((a+d)+f), 61: b+g}
- 合并 39 和 61，新节点频率为 100，树构建完成。

霍夫曼树结构图（每个节点标注为频率）：

              (100)
             /     \
          (39)     (61)
         /   \     /   \
      (17)  (22) (25)  (36)
     /   \  /  \  
   (7)  (10)(11)(11)
  /  \        /  \
(3)  (4)    (5)  (6)
c    h      a    d

2. 霍夫曼编码

从根节点到叶节点，向左为 0，向右为 1。根据树的结构，编码如下：

Letter	Frequency	Huffman Code
c	3	0000
h	4	0001
a	5	0100
d	6	0101
e	10	001
f	11	011
b	25	10
g	36	11

3. 期望比特长度

期望比特长度公式：
$ L = _{i=1}^n P_i l_i $ 其中 $P_i$ 为字母频率的比例，$l_i$ 为编码长度。

计算： $ L = + + + + + + + $ $ L = 0.12 + 0.16 + 0.2 + 0.24 + 0.3 + 0.33 + 0.5 + 0.72 = 2.57 $

4. 示例：霍夫曼编码的优点

假设对以下字符串编码：hhhbbaagggg

固定长度编码： 需要 $ _2 8 = 3 $ 比特/字母，总长度为 $3 \times 11 = 33$ 比特。
霍夫曼编码：
- h: 0001 (4比特) × 3 = 12比特
- b: 10 (2比特) × 2 = 4比特
- a: 0100 (4比特) × 2 = 8比特
- g: 11 (2比特) × 4 = 8比特
- 总长：$12 + 4 + 8 + 8 = 32$ 比特。

霍夫曼编码比固定长度编码节省了 1 比特，且随着输入长度增加，节省效果更明显。

图论

相信你只要会区分Prim和迪杰斯特拉算法，就一定可以完成这道题。

Prim将整颗不断生成的树看成一个整体，去寻找距离这个整体最近的点。

问题：

我们需要使用 Prim 算法 构建一个图的最小生成树（MST）。已知图如下（边权重和顶点的连接关系会具体提供）：

要求：

以顶点 1 为起点，运行 Prim 算法。
列出边的访问顺序。
绘制最终的最小生成树（MST）。

2-3树

问题描述：

给定一个 2-3 树，需要按照以下顺序插入元素：26, 85, 7。
在每次插入后，画出插入后的 2-3 树，最终需要画出 3 幅图。

外部排序

问题：

假设有一个文件需要排序，文件的大小为 f 条记录，工作内存的大小为 M 条记录，初始的运行是通过替换选择算法创建的，每个运行文件的块大小为 s 条记录。为了充分利用工作内存，应使用多少路归并（x-way merge）？处理这个磁盘文件平均需要多少个归并过程？假设 f=200000，M=100，s=10，磁盘扇区的大小为 2 条记录，至少需要多少次磁盘读取？

解答：

计算x-way merge的值： x-way merge 的值由工作内存大小 M 和每个块的大小 s 计算得出： $ x = = = 10 $ 也就是说，我们使用 10 路归并。
计算归并的次数k： 假设每次归并后需要继续归并的记录数为 f，经过每一轮归并后，剩下的记录数会减少，直到只剩下一个块。归并的次数 k 可以通过以下公式计算： $ 2M x^k = f $ 其中，2M 是初始块的大小，x 是每次归并的路数，f 是总记录数。

将公式改写为： $ x^k = $ 对该式取对数，得到： $ k = _x $

代入已知数值：f=200000，M=100，s=10，x=10，得到： $ k = {10} = {10} = _{10} 1000 = 3 $ 因此，总共需要 3 轮归并。
计算每轮归并的磁盘读取次数： 每轮归并需要读取的块数为： $ = = 20000 $ 每读取一个块，需要访问磁盘的次数为： $ = = 5 $ 因此，每轮归并的磁盘读取次数为： $ 20000 = 100000 $
总磁盘读取次数： 总的磁盘读取次数为每轮归并的读取次数乘以归并轮数： $ 3 = 300000 $