01年数据结构试卷

这是一套很板的试卷。

选择题

(3) For sequential search:

问题：
对于顺序搜索（Sequential Search），以下哪一项是正确的？我们需要分析最佳、平均和最坏情况下的时间复杂度，并比较它们的渐近性。

注意三者的渐进复杂度分析。

选项分析：

顺序搜索简介：
顺序搜索是一种线性查找算法，逐一检查列表中的元素，直到找到目标元素或搜索结束。
- 最佳情况（Best Case）： 目标元素在第一个位置，时间复杂度 $ O(1) $。
- 平均情况（Average Case）： 假设目标元素可能出现在任意位置，平均需要检查 $ n/2 $ 个元素，时间复杂度 $ O(n) $。
- 最坏情况（Worst Case）： 目标元素在最后一个位置或不存在，需要检查所有 $ n $ 个元素，时间复杂度 $ O(n) $。
选项分析：
- (A) The best, average, and worst cases are asymptotically the same.
  错误。最佳情况的时间复杂度是 $ O(1) $，而平均和最坏情况是 $ O(n) $，它们的渐近性不同。
- (B) The best case is asymptotically better than the average and worst cases.
  正确。最佳情况是 $ O(1) $，显然比平均和最坏情况的 $ O(n) $ 更好。
- (C) The best and average cases are asymptotically better than the worst case.
  错误。平均情况和最坏情况的时间复杂度是相同的 $ O(n) $，没有渐近上的区别。
- (D) The best case is asymptotically better than the average case, and the average case is asymptotically better than the worst case.
  错误。最佳情况确实更好，但平均情况和最坏情况的时间复杂度是相同的。

答案：

(B) The best case is asymptotically better than the average and worst cases.

(4) We use the parent pointer representation for general trees to solve which problem?

父指针表示法用来解决并查集问题。

问题：
对于一般树的父指针表示法，我们主要用于解决哪类问题？

选项分析：

父指针表示法简介：
在父指针表示法中，每个节点都有一个指向其父节点的指针。这种表示法在处理需要回溯或关联父节点信息的问题时特别有用。
选项分析：
- (A) Shortest paths（最短路径）
  错误。最短路径问题通常与图的边权重相关，而与树的父指针表示无关。
- (B) General tree traversal（树的遍历）
  错误。树的遍历（如前序、后序）通常依赖于递归或显式栈，而不是父指针。
- (C) Equivalence classes（等价类）
  正确。父指针表示法通常用在并查集（Union-Find）中，用于处理等价类问题。父指针帮助高效地追踪节点所属的集合，通过路径压缩优化查询和合并操作。
- (D) Exact-match query（精确匹配查询）
  错误。精确匹配查询更适用于哈希表或二叉搜索树。

答案：

(C) Equivalence classes.

总结：

(3) 的答案是 (B)。
(4) 的答案是 (C)。

(5) The most effective way to reduce the time required by a disk-based program is to:

磁盘的访问太慢了，是最大的限制。

问题分析：
磁盘操作的速度远慢于内存操作，因此磁盘访问通常是影响磁盘程序性能的主要瓶颈。

选项分析：

(A) Improve the basic operations.
虽然改进基本操作有助于提高效率，但磁盘程序的主要性能瓶颈在于磁盘访问，而不是基本操作的执行时间。
(B) Minimize the number of disk accesses.
正确。磁盘访问比内存访问慢得多，因此减少磁盘访问次数是优化磁盘程序的最有效方式。这通常可以通过缓存、批量处理数据或优化访问模式来实现。
(C) Eliminate the recursive calls.
递归调用对程序效率的影响通常与磁盘访问无关。优化递归调用对减少栈内存使用可能有帮助，但对磁盘程序不是主要的优化方向。
(D) Reduce main memory use.
减少内存使用可能有助于减少内存压力，但通常不会直接显著降低磁盘程序的运行时间，反而可能导致更多磁盘访问，从而降低效率。

答案：

(B) Minimize the number of disk accesses.

(7) The buddy method creates which form of fragmentation?

考试不考，这里只是记录一下。

问题分析：
Buddy memory allocation 是一种内存分配算法，通过将内存分成大小为 2 的幂次的块来进行分配。主要问题在于分配和释放内存时会产生碎片。

选项分析：

Internal Fragmentation（内部碎片）：
External Fragmentation（外部碎片）：
Both a and b（两种都有）：
None of all above（以上都不是）：

答案：B:External Fragmentation（外部碎片）： **

(8) Tree indexing methods are meant to overcome what deficiency in hashing?

哈希无法解决范围问题，树可以。

问题分析：
哈希表是一种高效的查找结构，但它有一些局限性。树型索引方法（如 B-树或 AVL 树）正是为了弥补这些不足而设计的。

选项分析：

(A) Inability to handle range queries.（无法处理范围查询）
- 哈希表的设计是为了快速查找单个键，而不是范围查询。由于哈希函数破坏了数据的顺序性，无法高效支持范围查询。
- 树型索引（如 B-树）保留了数据的顺序性，能高效处理范围查询。
  这是树型索引的主要优势。
(B) Inability to handle updates.（无法处理更新）
- 哈希表对插入和更新支持良好，通常复杂度为 $ O(1) $。
- 树型索引方法的更新效率通常较低，因此不是树型索引的优势。
(C) Inability to handle large data sets.（无法处理大数据集）
- 哈希表和树型索引都能扩展到大数据集，主要受限于内存或存储容量。
- 树型索引不是为解决这一问题而设计的。
(D) None of all above.（以上都不是）
- 不正确，因为选项 (A) 正确。

答案：

(A) Inability to handle range queries.

(9) The most important advantage of a 2-3 tree over a BST is that:

BST可能会出现退化的问题。

问题分析：

2-3 树是一种多路搜索树，其中每个节点可以有 2 个或 3 个子节点。它的主要特点是：

高度平衡：2-3 树始终保持平衡，因此查找、插入和删除的最坏时间复杂度是 $ O(n) $。
BST（普通二叉搜索树） 可能退化成链表结构（例如插入有序数据时），从而导致 $ O(n) $ 的最坏时间复杂度。

选项分析：

(A) The 2-3 tree has fewer nodes.
错误。2-3 树和 BST 的节点数相同，因为两者都存储相同的数据。
(B) The 2-3 tree has a higher branching factor.
部分正确。2-3 树允许每个节点有更多的分支（2 或 3 个子节点），这使树更“矮”。但这只是实现平衡的一部分原因，不是最重要的优势。
(C) The 2-3 tree is height balanced.
正确。2-3 树通过自动保持平衡，避免了 BST 退化的问题，这是它的最重要优势。
(D) None of all above.
错误，因为选项 (C) 正确。

答案：

(C) The 2-3 tree is height balanced.

(10) Which best characterizes the performance of the splay tree?

Splay的特点就是均摊。

问题分析：

Splay Tree 是一种自调整二叉搜索树，它通过伸展操作（将最近访问的节点移到树根）来优化性能。Splay Tree 的性能依赖于访问模式，有以下性质：

单次操作的最坏时间复杂度：$ O(n) $（树可能退化成链表）。
摊还复杂度（Amortized Complexity）：对于 $ m $ 次操作，总时间复杂度为 $ O(m n) $，即平均每次操作为 $ O(n) $。

选项分析：

(A) All operations require $ O(n) $ time.
错误。单次操作可能需要 $ O(n) $ 时间，摊还复杂度才是 $ O(n) $。
(B) $ m $ operations require a total of $ O(m n) $ time for $ m > n $.
正确。这是 Splay Tree 的摊还复杂度特性，符合实际性能描述。
(C) All operations require $ O(n) $ time.
错误。虽然单次操作可能达到 $ O(n) $，但总体性能远低于 $ O(n) $。
(D) None of all above.
错误，因为选项 (B) 正确。

答案：

(B) $ m $ operations require a total of $ O(m n) $ time for $ m > n $.

复杂度分析

只要不是特别复杂的递归分析，这一块基本都是送分题。

(1) Code Analysis

代码：

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

时间复杂度分析：

外层循环：固定执行 3 次。
内层循环：每次外层循环，内层循环执行 $ n $ 次。
总的循环次数：
$ T(n) = 3 n = O(n). $

答案：

$ (n). $

(2) Code Analysis

代码：

sum = 0;
for (i = 0; i < n; i++) // 外层循环，迭代 n 次
  for (j = 0; A[j] != i; j++) // 内层循环，条件由 A[j] 是否等于 i 决定
    sum++;

时间复杂度分析：

外层循环：迭代 $ n $ 次，变量 $ i $ 依次为 $ 0, 1, 2, , n-1 $。
内层循环：
- 假设 $ A $ 是一个包含 $ 0 $ 到 $ n-1 $ 的随机排列，内层循环的工作量取决于从数组 $ A $ 中找到值 $ i $ 的位置。
- 对于随机排列，元素 $ i $ 出现在数组 $ A $ 的平均位置是 $ $。
- 内层循环的平均复杂度为 $ O(n/2) = O(n) $。
总复杂度：
- 外层循环执行 $ n $ 次，每次内层循环的平均复杂度为 $ O(n) $。
- 总时间复杂度为：
  $ T(n) = n O(n) = O(n^2). $

答案：

$ (n^2). $

(3) Code Analysis

代码：

sum = 0;
if (EVEN(n)) // 检查 n 是否为偶数
  for (i = 0; i < n; i++) // 如果 n 是偶数，执行这个循环
    sum++;
else // 如果 n 是奇数，执行这个分支
  sum = sum + n;

时间复杂度分析

分支条件：
- 如果 $ n $ 是偶数，执行一个循环，循环次数为 $ n $。
- 如果 $ n $ 是奇数，直接进行加法赋值 $ sum = sum + n $，这是一个常数时间操作 $ O(1) $。
最坏情况：
- 对于 $ n $ 是偶数的情况，循环次数为 $ n $，时间复杂度为 $ O(n) $。
- 对于 $ n $ 是奇数的情况，时间复杂度为 $ O(1) $。
平均情况：
- 不论 $ n $ 的偶奇性如何，最坏复杂度仍然由 $ O(n) $ 主导，因为偶数情况的复杂度更高。

答案：

$ (n). $

解释

尽管对于奇数 $ n $ 的情况，执行时间是常数 $ O(1) $，但复杂度分析通常考虑最坏情况。对于本代码，最坏情况发生在 $ n $ 是偶数时，复杂度为 $ O(n) $。因此总体复杂度为 $ (n) $。

O(n)建堆问题

使用 buildheap 算法将数组 44, 66, 33, 88, 77, 55, 22 构造成一个 max-heap。

Max-Heap 规则

二叉堆（Binary Heap）：
- 是完全二叉树（Complete Binary Tree）。
- 节点值满足：父节点的值 大于等于 其子节点的值（Max-Heap）。
buildheap 算法：
- 从最后一个非叶子节点开始，对每个节点执行 heapify 操作（调整子树使其成为堆）。
- 时间复杂度： $ O(n) $。
数组表示的堆：
- 父节点：索引 $ i $。
- 左子节点：索引 $ 2i + 1 $。
- 右子节点：索引 $ 2i + 2 $。

初始数组

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

对应的完全二叉树：

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

步骤 1：从最后一个非叶子节点开始调整

最后一个非叶子节点索引是 $\lfloor \frac{n}{2} \rfloor - 1 = 2$（值为 $33$）。

调整子树以满足 Max-Heap

节点：33，子节点为 55 和 22
最大值为 $ 55 $，将 $ 33 $ 和 $ 55 $ 交换：

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

步骤 2：调整索引 1 的节点（值为 66）

节点：66，子节点为 88 和 77
最大值为 $ 88 $，将 $ 66 $ 和 $ 88 $ 交换：

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

步骤 3：调整索引 0 的节点（值为 44）

节点：44，子节点为 88 和 55
最大值为 $ 88 $，将 $ 44 $ 和 $ 88 $ 交换：

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

继续调整节点 44 的子树（值为 44，子节点为 66 和 77）
最大值为 $ 77 $，将 $ 44 $ 和 $ 77 $ 交换：
1
2
3
4
5
88
/ \
77 55
/ \ / \
66 44 33 22

最终 Max-Heap

数组表示：
$ 88, 77, 55, 66, 44, 33, 22 $

树形结构：

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

答案：

最终的 Max-Heap 数组为：
$ $

哈希问题

使用 闭合哈希（Closed Hashing）和 双重哈希（Double Hashing）解决冲突，将以下键插入一个包含 11 个槽的哈希表（槽编号从 0 到 10）。使用下面定义的哈希函数 H1 和 H2 进行哈希。你需要在插入所有八个键后显示哈希表，并注明如何使用 H1 和 H2 进行哈希。

H1(k) = 3k mod 11
H2(k) = 7k mod 10 + 1

键： 22, 41, 53, 46, 30, 13, 1, 67

步骤和解释

首先，我们创建一个哈希表，大小为 11 个槽，初始化为 null：

1	Hash Table: [null, null, null, null, null, null, null, null, null, null, null]

我们将每个键插入表中，按照 H1 和 H2 计算位置，并在发生碰撞时使用双重哈希解决。

键 22 的插入

H1(22) = 3 * 22 mod 11 = 66 mod 11 = 0
插入位置：槽 0。

更新哈希表：

1	Hash Table: [22, null, null, null, null, null, null, null, null, null, null]

键 41 的插入

H1(41) = 3 * 41 mod 11 = 123 mod 11 = 2
插入位置：槽 2。

更新哈希表：

1	Hash Table: [22, null, 41, null, null, null, null, null, null, null, null]

键 53 的插入

H1(53) = 3 * 53 mod 11 = 159 mod 11 = 5
插入位置：槽 5。

更新哈希表：

1	Hash Table: [22, null, 41, null, null, 53, null, null, null, null, null]

键 46 的插入

H1(46) = 3 * 46 mod 11 = 138 mod 11 = 6
插入位置：槽 6。

更新哈希表：

1	Hash Table: [22, null, 41, null, null, 53, 46, null, null, null, null]

键 30 的插入

H1(30) = 3 * 30 mod 11 = 90 mod 11 = 2
插槽 2 已经被 41 占用，发生碰撞。
使用 H2(30) 计算新的位置：
H2(30) = 7 * 30 mod 10 + 1 = 210 mod 10 + 1 = 0 + 1 = 1
计算新的插槽：槽 2 + H2(30) = 2 + 1 = 3（槽 3 为空）。
插入位置：槽 3。

更新哈希表：

1	Hash Table: [22, null, 41, 30, null, 53, 46, null, null, null, null]

键 13 的插入

H1(13) = 3 * 13 mod 11 = 39 mod 11 = 6
插槽 6 已被 46 占用，发生碰撞。
使用 H2(13) 计算新的位置：
H2(13) = 7 * 13 mod 10 + 1 = 91 mod 10 + 1 = 1 + 1 = 2
计算新的插槽：槽 6 + H2(13) = 6 + 2 = 8（槽 8 为空）。
插入位置：槽 8。

更新哈希表：

1	Hash Table: [22, null, 41, 30, null, 53, 46, null, 13, null, null]

键 1 的插入

H1(1) = 3 * 1 mod 11 = 3 mod 11 = 3
插槽 3 已被 30 占用，发生碰撞。
使用 H2(1) 计算新的位置：
H2(1) = 7 * 1 mod 10 + 1 = 7 mod 10 + 1 = 7 + 1 = 8
计算新的插槽：槽 3 + H2(1) = 3 + 8 = 11 mod 11 = 0（槽 0 已被 22 占用）。
使用双重哈希继续冲突解决：
插槽 0 + H2(1) = 0 + 8 = 8（槽 8 已被 13 占用）。
插槽 8 + H2(1) = 8 + 8 = 16 mod 11 = 5（槽 5 已被 53 占用）。
插槽 5 + H2(1) = 5 + 8 = 13 mod 11 = 2（槽 2 已被 41 占用）。
插槽 2 + H2(1) = 2 + 8 = 10（槽 10 为空）。
插入位置：槽 10。

更新哈希表：

1	Hash Table: [22, null, 41, 30, null, 53, 46, null, 13, null, 1]

键 67 的插入

H1(67) = 3 * 67 mod 11 = 201 mod 11 = 3
插槽 3 已被 30 占用，发生碰撞。
使用 H2(67) 计算新的位置：
H2(67) = 7 * 67 mod 10 + 1 = 469 mod 10 + 1 = 9 + 1 = 10
计算新的插槽：槽 3 + H2(67) = 3 + 10 = 13 mod 11 = 2（槽 2 已被 41 占用）。
插槽 2 + H2(67) = 2 + 10 = 12 mod 11 = 1（槽 1 为空）。
插入位置：槽 1。

更新哈希表：

1	Hash Table: [22, 67, 41, 30, null, 53, 46, null, 13, null, 1]

最终哈希表

1	Hash Table: [22, 67, 41, 30, null, 53, 46, null, 13, null, 1]

答案总结

通过使用双重哈希，所有 8 个键已成功插入哈希表，解决了冲突。哈希表的最终状态是：

1	[22, 67, 41, 30, null, 53, 46, null, 13, null, 1]

栈和队列问题

回文是一个字符串，无论是从前往后读还是从后往前读都一样。使用有限数量的栈和队列，栈和队列的基本操作，以及有限数量的整数和字符变量，编写一个算法来判断一个字符串是否是回文。假设字符串是从标准输入中逐个字符读取的。算法应根据情况输出 true 或 false。

算法设计

为了判断一个字符串是否是回文，可以利用栈和队列的特性：

栈：后进先出（LIFO），可以用来存储字符串的字符。
队列：先进先出（FIFO），可以用来存储字符串的字符。

我们可以将字符串的字符逐个读入队列和栈中，然后逐个比较栈和队列的元素是否相等。具体步骤如下：

读取字符串：逐个字符读取字符串，并同时将字符存入栈和队列。
比较字符：从栈中弹出字符，并从队列中取出字符进行比较。如果每一对字符都相等，则说明是回文；否则不是。

栈和队列操作

栈操作：
- push(c)：将字符 c 推入栈中。
- pop()：从栈中弹出一个字符。
队列操作：
- enqueue(c)：将字符 c 放入队列。
- dequeue()：从队列中取出一个字符。

算法步骤

初始化一个空的栈 S 和一个空的队列 Q。
逐个字符读取输入，直到结束：
- 对于每个字符 c，执行：
  - 将字符 c 压入栈 S。
  - 将字符 c 入队到队列 Q。
在读取完所有字符后，进行比较：
- 从栈中弹出一个字符，并从队列中出队一个字符。
- 比较栈弹出的字符和队列出队的字符，如果两者不同，则输出 false，表示不是回文。
如果所有字符都相同，则输出 true，表示是回文。

算法实现

#include <iostream>
#include <stack>
#include <queue>
#include <string>
using namespace std;

bool is_palindrome() {
    // 创建一个栈和队列
    stack<char> stack;
    queue<char> queue;

    // 读取字符串输入
    string input_string;
    cout << "请输入字符串：";
    cin >> input_string;

    // 将字符串字符依次压入栈和入队列
    for (char c : input_string) {
        stack.push(c);
        queue.push(c);
    }

    // 比较栈和队列中的元素
    while (!stack.empty()) {
        if (stack.top() != queue.front()) {
            return false;  // 如果有不同的字符，则不是回文
        }
        stack.pop();
        queue.pop();
    }

    return true;  // 如果所有字符都相同，则是回文
}

int main() {
    // 调用函数并输出结果
    if (is_palindrome()) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }

    return 0;
}

说明

栈和队列操作：栈是使用列表来模拟的，队列是使用 collections.deque 来模拟的。
时间复杂度：
- 入栈和入队列的操作是 O(1)，对每个字符都做一次操作。
- 弹栈和出队列的操作也是 O(1)，每个字符只弹出和出队一次。
- 总的时间复杂度是 O(n)，其中 n 是字符串的长度。
空间复杂度：
- 需要额外存储栈和队列，空间复杂度是 O(n)，其中 n 是字符串的长度。

例子

输入：

1	请输入字符串：racecar

输出：

true

输入：

1	请输入字符串：hello

输出：

false

总结

此算法通过栈和队列结合使用，逐个比较字符，判断给定字符串是否是回文。它利用栈和队列的特性，以较高的效率判断字符串的回文性质。

二叉树递归问题

编写一个名为 search 的递归函数，输入一个二叉树（不是二叉搜索树）和一个值 K，如果在树中找到 K，则返回 true，否则返回 false。函数应具有以下原型：

1 2	template <class Key, class Elem, class KEComp> bool search ( BinNode<Elem>* subroot, Key K);

解答

算法思路

递归基准条件：
- 如果当前节点为空（即树为空或已经递归到树的叶子节点），返回 false。
- 如果当前节点的值等于 K，返回 true。
递归过程：
- 否则，递归搜索左子树和右子树。
- 如果左子树或右子树中找到了 K，则返回 true；否则，返回 false。

函数设计

输入参数：
- subroot: 当前子树的根节点。
- K: 要搜索的值。
递归处理：
- 检查当前节点的值是否与 K 相等。
- 如果相等，则返回 true。
- 否则，递归检查左子树和右子树。

时间复杂度

最坏情况下，递归遍历整个树，时间复杂度是 O(n)，其中 n 是树中节点的个数。

空间复杂度

递归深度最深为树的高度，因此空间复杂度是 O(h)，其中 h 是树的高度。

代码实现

template <class Key, class Elem, class KEComp>
bool search(BinNode<Elem>* subroot, Key K) {
    // 如果当前节点为空，返回 false
    if (subroot == nullptr) {
        return false;
    }
    
    // 如果当前节点的值等于 K，返回 true
    if (subroot->data == K) {
        return true;
    }
    
    // 递归搜索左子树和右子树
    return search(subroot->left, K) || search(subroot->right, K);
}

解释

函数原型：
- BinNode<Elem>* subroot：指向当前子树的根节点。
- Key K：要查找的值 K。
递归逻辑：
- 如果当前节点 subroot 为 nullptr，则说明没有找到该节点，返回 false。
- 如果当前节点的值等于 K，返回 true。
- 否则，递归搜索当前节点的左子树和右子树，只要其中一个子树中找到了 K，就返回 true。
终止条件：
- 如果节点为空，或值等于 K，都能在递归中终止。