SCUT2001

Select the correct choice.

(3) For sequential search,

  1. The best, average, and worst cases are asymptotically the same.

  2. The best case is asymptotically better than the average and worst cases.

  3. The best and average cases are asymptotically better than the worst case.

  4. The best case is asymptotically better than the average case, and the average case is asymptotically better than the worst case.

答案： (B)

解释： 顺序查找的最佳情况是目标元素在数组的第一个位置，仅需 \(O(1)\) 的时间复杂度。而平均情况和最坏情况需要遍历整个数组，分别为 \(O(n)\)。因此，最佳情况的复杂度比平均情况和最坏情况都要低。

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

  1. Inability to handle range queries.

  2. Inability to handle updates.

  3. Inability to handle large data sets.

  4. None of all above.

答案： (A)

解释： 哈希方法通常不支持范围查询（range queries），因为哈希表仅支持精确匹配查询。而树形索引（如 B 树或 AVL 树）可以按照顺序组织数据，支持高效的范围查询。

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

  1. The 2-3 tree has fewer nodes.

  2. The 2-3 tree has a higher branching factor.

  3. The 2-3 tree is height balanced.

  4. None of all above.

答案： (C)

解释： 2-3 树的主要优点是高度平衡，保证插入、删除和查找操作的时间复杂度始终为 \(O(\log n)\)。而普通二叉搜索树（BST）在插入不平衡数据时可能会退化为链表，导致 \(O(n)\) 的复杂度。

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

  1. All operations require \(O(\log n)\) time.

  2. \(m\) operations require a total of \(O(m \log n)\) time for \(m > n\).

  3. All operations require \(O(n)\) time.

  4. None of all above.

答案： (B)

解释： Splay 树是一种自调整二叉搜索树，其每次操作的最坏情况时间复杂度为 \(O(n)\)，但其在 \(m\) 次操作上的均摊时间复杂度为 \(O(\log n)\)。因此，选项 (B) 正确。

Trace by hand the execution of Quicksort algorithm on the array:

int a[] = {44, 77, 55, 99, 66, 33, 22, 88, 77}

Show the max-heap that results from running buildHeap on the following values stored in an array: 44, 66, 33, 88, 77, 55, 22.

通过 BuildHeap 构建最大堆的过程

初始数组表示

给定数组：
[ 44, 66, 33, 88, 77, 55, 22 ]

可以将其看作完全二叉树：

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

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

最后一个非叶节点索引为：

\[ \lfloor n/2 \rfloor - 1 = 2 \]

节点值为 \(33\)。从该节点开始对树进行 heapify 操作。

调整索引 2（值为 33）的子树

  • 左子节点：\(55\)，右子节点：\(22\)。
  • 最大值为 \(55\)，交换 \(33\) 和 \(55\)。

调整后的树为：

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

调整索引 1（值为 66）的子树

  • 左子节点：\(88\)，右子节点：\(77\)。
  • 最大值为 \(88\)，交换 \(66\) 和 \(88\)。

调整后的树为：

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

调整索引 0（值为 44）的子树

  • 左子节点：\(88\)，右子节点：\(55\)。
  • 最大值为 \(88\)，交换 \(44\) 和 \(88\)。

调整后的树为：

        88
     /     \
   44       55
  /  \     /  \
66   77   33   22
  • 继续对索引 1（值为 44）进行 heapify：
    • 左子节点：\(66\)，右子节点：\(77\)。
    • 最大值为 \(77\)，交换 \(44\) 和 \(77\)。

最终树为：

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

最终最大堆

最终堆的数组表示为：
[ 88, 77, 55, 66, 44, 33, 22 ]

这就是运行 BuildHeap 后得到的最大堆结果。

Using closed hashing, with double hashing to resolve collisions, insert the following keys into a hash table of eleven slots (the slots are numbered 0 through 10). The hash functions to be used are H1 and H2, defined below. You should show the hash table after all eight keys have been inserted. Be sure to indicate how you are using H1 and H2 to do the hashing.

\[ H1(k) = 3k \ mod \ 11 \\ H2(k) = 7k \ mod \ 10+1 \\ Keys: 22, 41, 53, 46, 30, 13, 1, 67. \]

以下是使用闭散列（closed hashing）结合双散列（double hashing）解决冲突来将给定键插入到有 11 个槽（编号从 0 到 10）的哈希表中的步骤及最终结果：

步骤一：计算每个键的初始哈希值（使用 \(H1\) 函数）

  1. 对于键 \(22\)：

\[ \begin{align*} H1(22)&=3\times22\bmod{11}\\ &=66\bmod{11}\\ &=0 \end{align*} \]

所以，键 \(22\) 初始尝试插入到槽 \(0\) 位置。

  1. 对于键 \(41\)：

\[ \begin{align*} H1(41)&=3\times41\bmod{11}\\ &=123\bmod{11}\\ &=2 \end{align*} \]

键 \(41\) 初始尝试插入到槽 \(2\) 位置。

  1. 对于键 \(53\)：

\[ \begin{align*} H1(53)&=3\times53\bmod{11}\\ &=159\bmod{11}\\ &=5 \end{align*} \]

键 \(53\) 初始尝试插入到槽 \(5\) 位置。

  1. 对于键 \(46\)：

\[ \begin{align*} H1(46)&=3\times46\bmod{11}\\ &=138\bmod{11}\\ &=6 \end{align*} \]

键 \(46\) 初始尝试插入到槽 \(6\) 位置。

  1. 对于键 \(30\)：

\[ \begin{align*} H1(30)&=3\times30\bmod{11}\\ &=90\bmod{11}\\ &=2 \end{align*} \]

键 \(30\) 初始尝试插入到槽 \(2\) 位置，此时与键 \(41\) 冲突（因为 \(H1(41)\) 也得到槽 \(2\)），需要使用双散列来解决冲突，我们接着计算 \(H2(30)\) 用于确定偏移量。

  1. 对于键 \(13\)：

\[ \begin{align*} H1(13)&=3\times13\bmod{11}\\ &=39\bmod{11}\\ &=6 \end{align*} \]

键 \(13\) 初始尝试插入到槽 \(6\) 位置，与键 \(46\) 冲突，需要用双散列解决冲突，计算 \(H2(13)\) 来确定偏移量。

  1. 对于键 \(1\)：

\[ \begin{align*} H1(1)&=3\times1\bmod{11}\\ &=3\bmod{11}\\ &=3 \end{align*} \]

键 \(1\) 初始尝试插入到槽 \(3\) 位置。

  1. 对于键 \(67\)：

\[ \begin{align*} H1(67)&=3\times67\bmod{11}\\ &=201\bmod{11}\\ &=3 \end{align*} \]

键 \(67\) 初始尝试插入到槽 \(3\) 位置，与键 \(1\) 冲突，需要用双散列来解决冲突，计算 \(H2(67)\) 确定偏移量。

步骤二：计算双散列的偏移量（使用 \(H2\) 函数，当出现冲突时）

  1. 对于键 \(30\)（与键 \(41\) 在槽 \(2\) 冲突）：

\[ \begin{align*} H2(30)&=7\times30\bmod{10}+1\\ &=210\bmod{10}+1\\ &=0 + 1\\ &=1 \end{align*} \]

由于初始槽 \(2\) 冲突，通过 \(H2(30)\) 得到偏移量为 \(1\)，尝试插入到槽 \((2 + 1)\bmod{11} = 3\bmod{11} = 3\) 位置，又与键 \(1\) 冲突，继续使用双散列，计算新的偏移量（还是基于 \(H2(30)\)，重复利用这个函数直到找到空闲槽）。再次计算偏移量还是 \(1\)，尝试插入到槽 \((3 + 1)\bmod{11} = 4\bmod{11} = 4\) 位置，该位置空闲，所以键 \(30\) 最终插入到槽 \(4\) 位置。

  1. 对于键 \(13\)（与键 \(46\) 在槽 \(6\) 冲突）：

\[ \begin{align*} H2(13)&=7\times13\bmod{10}+1\\ &=91\bmod{10}+1\\ &=1 + 1\\ &=2 \end{align*} \]

初始槽 \(6\) 冲突，偏移量为 \(2\)，尝试插入到槽 \((6 + 2)\bmod{11} = 8\bmod{11} = 8\) 位置，该位置空闲，键 \(13\) 插入到槽 \(8\) 位置。

  1. 对于键 \(67\)（与键 \(1\) 在槽 \(3\) 冲突）：

\[ \begin{align*} H2(67)&=7\times67\bmod{10}+1\\ &=469\bmod{10}+1\\ &=9 + 1\\ &=10 \end{align*} \]

初始槽 \(3\) 冲突，偏移量为 \(10\)，尝试插入到槽 \((3 + 10)\bmod{11} = 2\bmod{11} = 2\) 位置，又冲突（与键 \(41\) 冲突），继续计算新的偏移量（还是基于 \(H2(67)\) ），重复这个过程，再次得到偏移量 \(10\)，尝试插入到槽 \((2 + 10)\bmod{11} = 1\bmod{11} = 1\) 位置，该位置空闲，所以键 \(67\) 最终插入到槽 \(1\) 位置。

步骤三：得到最终的哈希表状态

槽编号 键值
0 22
1 67
2 41
3 1
4 30
5 53
6 46
7
8 13
9
10

在整个插入过程中，先使用 \(H1\) 函数确定初始的插入槽位置，当出现冲突时，使用 \(H2\) 函数计算偏移量，通过不断尝试找到空闲的槽位置来插入键值，最终得到上述的哈希表状态。

A palindrome is a string that reads the same forwards as backwards. Using only a fixed number of stacks and queues, the stack and queue ADT functions, and a fixed number of int and char variables, write an algorithm to determine if a string is a palindrome. Assume that the string is read from standard input one character at a time. The algorithm should output true or false as appropriate.

判断字符串是否是回文串的算法

使用 一个栈 和 一个队列，并结合栈和队列的基本操作来实现对回文字符串的判断。

算法步骤

  1. 初始化数据结构：

    • 创建一个栈（stack）和一个队列（queue）来存储字符。
    • 准备少量的 int 和 char 变量用于辅助操作。

  2. 输入处理：

    • 从标准输入逐个读取字符。
    • 对于每个字符，将其压入栈（stack）并加入队列（queue）。

  3. 回文验证：

    • 当栈和队列都非空时，进行以下操作：
      • 从栈中弹出一个字符（后进先出）。
      • 从队列中取出一个字符（先进先出）。
      • 比较两个字符：
        • 如果不相等，说明字符串不是回文串，输出 false 并终止程序。
    • 如果栈和队列均为空且未发现不匹配，说明字符串是回文串，输出 true。

伪代码

算法 isPalindrome
    输入：一个逐字符读取的字符串
    输出：true（是回文串）或 false（不是回文串）

    初始化一个空栈 stack
    初始化一个空队列 queue

    // 将字符存入栈和队列
    while (未到输入结束)
        读取一个字符 c
        将 c 压入栈 stack
        将 c 加入队列 queue

    // 比较栈和队列中的字符
    while (栈非空 且 队列非空)
        从栈中弹出一个字符 stackChar
        从队列中取出一个字符 queueChar

        如果 stackChar ≠ queueChar
            输出 false
            返回

    // 如果所有字符匹配，则是回文串
    输出 true
结束

执行示例

输入："madam"

  1. 栈和队列填充：

    • 栈（自顶向下）：m, a, d, a, m
    • 队列（从前到后）：m, a, d, a, m

  2. 字符比较：

    • 比较 m（栈顶弹出）和 m（队首取出）→ 相等。
    • 比较 a 和 a → 相等。
    • 比较 d 和 d → 相等。
    • 比较 a 和 a → 相等。
    • 比较 m 和 m → 相等。

结果：所有字符均匹配，输出 true。

C++ 实现

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

bool isPalindrome() {
    stack<char> stack;
    queue<char> queue;
    char c;

    // 逐个读取字符并存入栈和队列
    while (cin >> c) {
        stack.push(c);
        queue.push(c);
    }

    // 比较栈和队列中的字符
    while (!stack.empty() && !queue.empty()) {
        char stackChar = stack.top();
        char queueChar = queue.front();
        stack.pop();
        queue.pop();

        if (stackChar != queueChar) {
            return false; // 不是回文串
        }
    }

    return true; // 是回文串
}

int main() {
    if (isPalindrome()) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }
    return 0;
}

算法分析

  1. 时间复杂度：

    • 栈和队列填充：$ O(n) $
    • 字符比较：$ O(n) $
    • 总时间复杂度：$ O(n) $。

  2. 空间复杂度：

    • 栈和队列各存储 $ n $ 个字符，空间复杂度为 $ O(n) $。

总结

通过栈的后进先出特性和队列的先进先出特性，可以轻松实现对回文字符串的判断，且算法高效，逻辑清晰。

Write a recursive function named search that takes as input a binary tree (NOT a BST!) and a value K, and returns true if value K appears in the tree and false otherwise. Your function should have the following prototype:

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

递归实现搜索非二叉搜索树的值

以下是实现 search 函数的递归版本，该函数用于在非二叉搜索树（普通二叉树）中查找指定值 $ K $。因为树不是二叉搜索树，我们需要遍历整棵树的所有节点。

C++ 实现

template <class Key, class Elem, class KEComp>
bool search(BinNode<Elem>* subroot, Key K) {
    // 基础情况：当前子树为空，返回 false
    if (subroot == nullptr) {
        return false;
    }

    // 检查当前节点的值是否等于目标值 K
    if (KEComp::eq(subroot->value(), K)) {
        return true;
    }

    // 递归地搜索左子树和右子树
    return search<Key, Elem, KEComp>(subroot->left(), K) ||
           search<Key, Elem, KEComp>(subroot->right(), K);
}

详细解释

1. 基础情况（递归终止条件）

  • 如果当前子树为空（subroot == nullptr），说明已经到达叶子节点的末端，返回 false。

2. 当前节点检查

  • 比较当前节点的值是否与目标值 $ K $ 相等。
  • 使用 KEComp::eq 实现通用的比较逻辑（例如，整数比较、字符串比较等）。

3. 递归搜索左右子树

  • 分别对当前节点的左子树和右子树递归调用 search 函数。
  • 如果目标值在左子树或右子树中找到，立即返回 true。

4. 短路逻辑

  • 使用 || 短路逻辑：一旦在左子树中找到 $ K $，右子树将不会被搜索，节省计算资源。

伪代码

算法 search(subroot, K)
    输入：subroot（当前子树的根节点），K（目标值）
    输出：true（找到 K）或 false（未找到 K）

    如果 subroot == nullptr
        返回 false

    如果 subroot.value == K
        返回 true

    返回 search(subroot.left, K) || search(subroot.right, K)

示例

假设有如下二叉树：

     5
   /   \
  3     7
 / \   / \
2   4 6   8

调用示例：

struct IntComp {
    static bool eq(int a, int b) {
        return a == b;
    }
};

BinNode<int>* root = ...; // 初始化二叉树
int key = 6;

bool found = search<int, int, IntComp>(root, key);
std::cout << (found ? "找到" : "未找到") << std::endl;

执行过程：

  1. 从根节点 5 开始：

    • 检查 5 == 6（不相等）。
    • 递归搜索左子树 3 和右子树 7。

  2. 左子树 3：

    • 检查 3 == 6（不相等）。
    • 递归搜索左子树 2 和右子树 4。

  3. 节点 2 和 4：

    • 均返回 false。

  4. 右子树 7：

    • 检查 7 == 6（不相等）。
    • 递归搜索左子树 6 和右子树 8。

  5. 节点 6：

    • 检查 6 == 6（相等），返回 true。

最终输出：找到。

时间复杂度分析

  • 最坏情况：需要遍历所有节点，时间复杂度为 $ O(n) $，其中 $ n $ 是树的节点数。
  • 最佳情况：在根节点或靠近根的子树中找到目标值，时间复杂度接近 $ O(1) $。

总结

这个递归算法通过深度优先搜索（DFS）在普通二叉树中查找目标值，逻辑清晰且高效。它的灵活性来源于模板设计和通用比较器 KEComp，适用于各种类型的树节点值。