数据结构15年B

大概浏览了一下试卷，这会是一张比较有难度的试卷。

选择题

问题1：插入元素到有序的基于数组的列表，并保持该数组有序。该插入算法的计算效率是多少？

选项：

O(1)
O(log n)
O(n)
O(n²)

解析：

对于一个有序的数组，当我们插入一个新元素时，我们首先需要找到插入的位置。这个过程可以通过二分查找完成，时间复杂度为 O(log n)。但是，找到插入位置后，我们还需要将元素插入该位置，移动该位置后的所有元素。因此，插入操作的总时间复杂度是 O(n)。

答案： (C) O(n)

问题2：线性索引对于所有以下情况都适用，除了哪个？

选项：

范围查询
精确匹配查询
插入/删除
内存中的应用

解析：

线性索引是一种按顺序排列的索引结构，对于范围查询和精确匹配查询通常效率较高。然而，插入和删除操作的效率较低，因为每次插入或删除元素时，都需要移动大量元素。因此，线性索引对于插入和删除操作并不理想。

答案： (C) 插入/删除

问题3：与二叉搜索树（BST）相比，2-3 树的最重要优势是什么？

选项：

2-3 树有更少的节点
2-3 树有更高的分支因子
2-3 树是高度平衡的
上述都不正确

解析：

2-3 树是一种自平衡的树结构，它在插入和删除操作时自动保持平衡。其关键优势在于高度平衡，这意味着在最坏情况下，树的高度较低，从而确保操作的时间复杂度是 O(log n)。相比之下，二叉搜索树（BST）在没有平衡操作时，可能会退化成链表，导致时间复杂度变为 O(n)。

答案： (C) 2-3 树是高度平衡的

问题4：在一个阶数为 5 的 B-树中，除了根节点之外，每个节点中至少包含多少个关键字？

选项：

解析：

在一个阶数为5的B-树中，除根节点外每个节点的关键字数量至少是（2）。

解释：对于阶数为m的B-树，除根节点外，每个节点中的关键字个数n满足：⌈m/2⌉ - 1 ≤ n ≤ m - 1。这里m = 5，⌈5/2⌉ - 1 = 3 - 1 = 2，所以除根节点外每个节点关键字数量至少是2个。

答案： (B) 2

问题5：使用归并排序对包含 20 个键的记录序列进行排序时，将执行多少次遍历（pass）？

选项：

解析：

归并排序是一种分治算法，每次遍历（pass）都会将相邻的元素合并成更大的有序块。每次归并的步骤都会将待排序的块数减半，直到块数为 1。对于 20 个元素，归并排序的 passes 次数是通过对数计算的，即 ⌈log₂(20)⌉。

$ _2 20 = 5 $

因此，归并排序需要 5 次遍历来完成排序。

答案： (D) 5

问题6：树索引方法旨在克服哈希中的什么缺陷？

选项：

无法处理范围查询
无法处理更新
无法处理大数据集
上述都不正确

解析：

哈希表的主要缺陷之一是它无法有效地处理范围查询。哈希表通过哈希函数直接定位数据，因此对于需要查找某个范围内的数据的查询（如 "查找所有键值在某一范围内的记录"）非常困难。而树索引（如 B-树）由于其有序结构，非常适合进行范围查询和范围操作。

答案： (A) 无法处理范围查询

问题7：如果输入顺序为 1, 2, 3, 4, 5, 6，哪个输出序列是不可能的？

选项：

2, 4, 3, 5, 1, 6
3, 2, 5, 6, 4, 1
1, 5, 4, 6, 2, 3
4, 5, 3, 6, 2, 1

解析：

栈是一种后进先出（LIFO）数据结构。也就是说，最后入栈的元素会最先出栈。我们需要检查哪个输出序列无法通过栈的顺序操作（推入和弹出）生成。

输入序列： 1, 2, 3, 4, 5, 6
栈操作： 每次将元素推入栈中，直到需要弹出元素为止。

检查每个选项：

(A) 2, 4, 3, 5, 1, 6： 这是可能的。操作顺序可以是推入 1, 2 后弹出 2，然后推入 3, 4 后弹出 4, 3，然后推入 5, 6 最后弹出 1 和 5, 6。
(B) 3, 2, 5, 6, 4, 1： 这是可能的。操作顺序是推入 1, 2, 3 后弹出 3, 2，然后推入 4, 5, 6 最后弹出 6, 5, 4, 1。
(C) 1, 5, 4, 6, 2, 3： 这是不可能的。为了让 5 和 4 出现，必须先推入 1, 2, 3，然后再推入 5, 4，但是 5 和 4 必须先弹出，导致无法按给定顺序出栈。
(D) 4, 5, 3, 6, 2, 1： 这是可能的。推入顺序可以是 1, 2, 3, 4, 5, 6，按照 LIFO 顺序弹出元素。

答案： (C) 1, 5, 4, 6, 2, 3

问题8：以下代码段的时间复杂度是多少？

sum1 = 0;
for (k = 1; k <= n; k *= 2)  // 循环 1
    for (j = 1; j <= n; j++)  // 循环 2
        sum1++;

选项：

Θ(n)
Θ(n²)
Θ(n log n)
Θ(log n)

解析：

分析代码：

外层循环： for (k = 1; k <= n; k *= 2)，每次 k 都是前一次的两倍，即进行对数次数的循环。外层循环的次数为 log₂ n，因此外层循环的时间复杂度为 O(log n)。
内层循环： for (j = 1; j <= n; j++)，这个循环从 1 到 n 进行迭代，所以内层循环的时间复杂度是 O(n)。

因此，整个代码的时间复杂度是外层循环的 O(log n) 乘以内层循环的 O(n)，即： $ O(n) O(n) = O(n n) $

答案： (C) Θ(n log n)

问题9：下列四个二叉树中，哪一个不是完全二叉树？

选C。

问题10：对于以下图，广度优先遍历（BFS）的结果之一是：

选项：

acbdieghf
abcideghf
abcdefghi
abcidgehf

解析：

广度优先遍历（BFS）是从起始节点开始，逐层访问每个节点。在 BFS 中，节点按照它们的层级顺序被访问，从左到右逐层进行遍历。

答案是D。

构造树

还是构造树，就不讲解了。

哈夫曼树

没有一张卷子不考察哈夫曼树的。

建堆

很板的建堆，注意一个删除非根节点的建堆即可。

哈希

每次都是这道双哈希，没有变过。

2-3树

考察一个2-3树的插入，估计不敢考太难。

最小生成树

掌握两个板子的原理即可。

硬盘读取

掌握板子。

一个简单的程序填空

实现拓补排序，很好的华工！！！

填写正确的C++代码以实现拓扑排序程序。

给定的代码框架是一个实现拓扑排序的基本框架，下面是如何填充每个空白位置的说明：

代码框架：

void topsort(Graph* G, Queue<int>* Q) {
  int* Count = new int[G->n()];  // 初始化入度数组
  int v, w;

  // ① 初始化入度数组
  for (v = 0; v < G->n(); v++) 
    Count[v] = 0;  // 初始化每个节点的入度为 0

  // ② 处理每一条边
  for (v = 0; v < G->n(); v++)   // 遍历每个节点
    for (w = G->first(v); w < G->n(); w = G->next(v, w))
      Count[w]++;  // 为每个目标节点增加一个入度

  // ③ 初始化队列
  for (v = 0; v < G->n(); v++)   // 查找入度为 0 的节点
    if (Count[v] == 0)            // 没有前驱节点的节点
      Q->enqueue(v);  // 将该节点加入队列

  // 处理队列中的节点
  while (Q->length() != 0) {  // 队列不为空时继续处理
    v = Q->dequeue();         // 取出队列中的一个节点
    printout(v);              // 打印出该节点（或执行相关操作）

    // ⑤ 减少相邻节点的入度
    for (w = G->first(v); w < G->n(); w = G->next(v, w)) {
      Count[w]--;  // 将当前节点 v 的所有邻接节点的入度减少 1

      // ⑥ 检查入度是否为 0，如果是，表示该节点已经可以访问
      if (Count[w] == 0) 
        Q->enqueue(w);  // 将入度为 0 的节点加入队列
    }
  }

  // 释放内存
  delete [] Count; 
  Count = NULL;
}

填空解释：

① 初始化入度数组
我们需要将每个节点的入度初始化为 0，因为拓扑排序依赖于节点的入度。
1
Count[v] = 0; // 初始化每个节点的入度为 0
② 处理每一条边
在这里，我们遍历图中所有的边。对于每一条边（从 v 到 w），我们需要增加目标节点 w 的入度，表示该节点有一个前驱节点。
1
Count[w]++; // 为每个目标节点增加一个入度
③ 初始化队列
将所有入度为 0 的节点（没有前驱的节点）加入队列中。我们将这些节点作为拓扑排序的起点。
1
Q->enqueue(v); // 将入度为 0 的节点加入队列
④ 处理队列中的节点
我们从队列中取出节点 v，并打印出来，表示对该节点的拓扑排序访问。
1
v = Q->dequeue(); // 取出队列中的一个节点
⑤ 减少相邻节点的入度
对于当前节点 v，我们将它的所有邻接节点（即 v 指向的节点）的入度减 1，表示一个前驱节点已经被访问完毕。
1
Count[w]--; // 将当前节点 v 的所有邻接节点的入度减少 1
⑥ 检查入度是否为 0
如果某个节点的入度减为 0，表示该节点可以被访问，我们将它加入队列中进行后续处理。
1
2
if (Count[w] == 0)
Q->enqueue(w); // 将入度为 0 的节点加入队列

总结：

① Count[v] = 0;
② Count[w]++;
③ Q->enqueue(v);
④ v = Q->dequeue();
⑤ Count[w]--;
⑥ if (Count[w] == 0) Q->enqueue(w);

BFS代码书写

编写一个程序，按广度优先搜索（BFS）顺序访问二叉树的所有节点。例如，给定以下二叉树，遍历结果是 ABCDEFG。

     A
   /   \
  B     C
 / \   / \
D   E F   G

解答：

1. BFS（广度优先搜索）简介：

BFS 是一种逐层访问节点的算法，通常使用队列来辅助实现。首先访问根节点，然后访问所有与根节点相邻的节点，接着访问其子节点，直到所有节点都被访问过。

2. C++实现：

#include <iostream>
#include <queue>

using namespace std;

// 定义二叉树节点
struct Node {
    char data;
    Node* left;
    Node* right;
    Node(char val) : data(val), left(nullptr), right(nullptr) {}
};

// 广度优先搜索遍历二叉树
void bfs(Node* root) {
    if (root == nullptr) return;  // 如果树为空，直接返回

    queue<Node*> q;  // 创建一个队列
    q.push(root);     // 将根节点加入队列

    while (!q.empty()) {
        Node* current = q.front();  // 取出队列中的第一个节点
        cout << current->data << " ";  // 打印当前节点的值
        q.pop();  // 弹出队列中的节点

        // 如果当前节点有左子节点，加入队列
        if (current->left != nullptr) {
            q.push(current->left);
        }

        // 如果当前节点有右子节点，加入队列
        if (current->right != nullptr) {
            q.push(current->right);
        }
    }
}

int main() {
    // 创建二叉树
    Node* root = new Node('A');
    root->left = new Node('B');
    root->right = new Node('C');
    root->left->left = new Node('D');
    root->left->right = new Node('E');
    root->right->left = new Node('F');
    root->right->right = new Node('G');
    
    // 执行广度优先遍历
    cout << "BFS traversal result: ";
    bfs(root);  // 输出结果应该是：A B C D E F G
    cout << endl;

    return 0;
}

解释：

结构体 Node：定义了二叉树的节点结构，每个节点包含 data（存储节点数据）、left（指向左子节点）、right（指向右子节点）。
bfs 函数：实现广度优先搜索遍历二叉树。使用一个队列来存储节点，首先将根节点加入队列。然后依次从队列中取出节点，访问它们的左子节点和右子节点，并将这些子节点加入队列。这样就实现了逐层遍历。
main 函数：创建了一棵示例二叉树，并调用 bfs 函数进行遍历。