2022年数据结构试卷回忆版

感谢学长所提供的回忆版，这下可以进行分析了。

选择题

问题 1: 算法分析的意义

选择题的一个常见问题是：算法分析的意义是什么？

答案：
算法分析的意义是评估一个算法在不同规模输入下的效率，帮助选择最适合的算法，减少计算资源的消耗，确保算法的可行性和实用性。

解释：
算法分析主要关注算法的时间复杂度和空间复杂度，帮助我们理解一个算法在处理大数据时的表现。例如，如果一个算法的时间复杂度是O(n^2)，那么在数据量很大的时候，它的效率就会变得非常低，可能不适合大规模数据处理。

问题 2: 完全二叉树的父子关系（根在0）

另一个问题是：完全二叉树的父子关系，根节点索引为0，如何确定父子节点？

答案：
在一个完全二叉树中，对于给定节点的索引i，

  • 父节点的索引为(i-1)//2。
  • 左子节点的索引为2*i + 1。
  • 右子节点的索引为2*i + 2。

解释：
完全二叉树是一种非常特殊的二叉树，它的每一层都被完全填满。通过节点的索引可以轻松地推算出父子节点的关系，根节点索引为0，依此类推。使用这种方式可以快速在数组中实现二叉树的结构。

问题 3: 如何快速选出最小的前十个数

最后，关于如何给定10000个数据，选出最小的前十个数：选择正确的排序算法。

答案：
最合适的算法是堆排序，特别是使用最小堆来提取最小的前十个数。

解释：
堆排序的时间复杂度为O(n log k)，其中n是总数据量，k是需要选取的前k个元素。相比O(n log n)的完全排序，堆排序能够以O(n log 10)的复杂度高效地选出最小的前十个元素，尤其在数据量非常大的情况下（例如10000个数据）。

程序填空

第一题：循环队列

问题描述：
这道程序填空题是关于循环队列，有两个空需要填充：

  1. 第一个空：判断队列是否满的条件。
  2. 第二个空：rear指针的调整。

答案：

image-20241204134936234 
1
2
3
4
5
// 判断队列是否满的条件
if ((rear + 2) % size == front) 

// 调整rear
rear = (rear + 1) % size;  // 循环队列中，rear的调整

解释：

  • 在循环队列中，当rear + 1等于front时，表示队列已经满了，无法再插入新元素。因此判断队列满的条件为(rear + 1) % size == front。
  • 循环队列通过取模运算保证队列的头尾连接，这样队列的大小保持不变，并且rear指针每次插入时都循环到队列的起始位置。

时间复杂度：
对于循环队列的操作，插入、删除、判断队列是否满、调整指针等操作的时间复杂度都是O(1)，因为这些操作只涉及指针的移动和简单的比较，不依赖于队列中元素的数量。

第二题：希尔排序

问题描述：
这道程序填空题是关于希尔排序，有三个空需要填充：

  1. 第一个空：插入排序的细节。
  2. 第二个空：希尔排序的细节，主要涉及步长的选择。
  3. 第三个空：调用一个函数。

答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 插入排序的细节
for (int i = gap; i < n; i++) {  
    int temp = arr[i];
    int j = i;
    while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
    }
    arr[j] = temp;
}

// 步长的选择（使用一个递减的步长序列）
for (gap = n / 2; gap > 0; gap /= 2) {  
    // 调用插入排序的函数
    shellSort(arr, n, gap);
}

解释：

  • 插入排序：在希尔排序中使用插入排序对每个步长分组进行排序。插入排序的核心是通过逐一比较和交换，确保小元素移到数组的前面。
  • 步长选择：希尔排序的关键在于步长的选择，常见的步长序列是从n/2开始，逐步减小，通常减半，直到步长为1。
  • 调用插入排序：在每个步长下，对数组元素执行插入排序，直到整个数组有序。

时间复杂度：

  • 希尔排序的时间复杂度是取决于步长序列的，通常在最优情况下为O(n log n)，最差情况下可能为O(n^2)，这取决于步长序列的选择。例如，如果使用较好的步长序列，希尔排序比直接的插入排序快很多。

第三题：二叉堆（小根堆）的下沉函数

问题描述：
这道程序填空题是关于二叉堆（小根堆）的下沉操作，有两个空需要填充：

  1. 第一个空：完全二叉树的父子关系（根节点索引为1）。
  2. 第二个空：比较三者（父节点和两个子节点）的大小，取最小的。

答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 父子关系的计算（根节点索引为1）
int leftChild = 2 * i;  // 左子节点的索引
int rightChild = 2 * i + 1;  // 右子节点的索引

// 下沉函数
int smallest = i;
if (leftChild <= n && arr[leftChild] < arr[smallest]) {
    smallest = leftChild;
}
if (rightChild <= n && arr[rightChild] < arr[smallest]) {
    smallest = rightChild;
}

if (smallest != i) {
    swap(arr[i], arr[smallest]);
    heapify(smallest);  // 递归调用下沉
}

解释：

  • 父子关系：在一个完全二叉树中，根节点的索引为1，左子节点的索引为2 * i，右子节点的索引为2 * i + 1。
  • 比较三者的大小：对于下沉操作，需要检查当前节点与其左右子节点的大小，找到最小的节点，然后交换。
  • 下沉操作：如果当前节点不是最小的节点，就需要交换当前节点和最小的子节点，并递归地对下沉后的节点继续进行调整。

时间复杂度：
二叉堆的下沉操作的时间复杂度为O(log n)，因为在最坏情况下需要沿着堆的深度（即高度）进行比较和交换。

解答题

第一题：给定前序和中序遍历，求后序遍历

问题描述：
给定二叉树的前序遍历和中序遍历，要求你输出二叉树的后序遍历结果。

答案： 假设前序遍历序列为 preorder[]，中序遍历序列为 inorder[]，可以通过递归的方法得到后序遍历结果。后序遍历的过程是：首先遍历左子树，再遍历右子树，最后访问根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void postOrder(int preorder[], int inorder[], int startPre, int endPre, int startIn, int endIn) {
    if (startPre > endPre || startIn > endIn) return;

    int root = preorder[startPre];  // 根节点是前序遍历的第一个元素
    int rootIndex = -1;

    // 在中序遍历中找到根节点的位置
    for (int i = startIn; i <= endIn; i++) {
        if (inorder[i] == root) {
            rootIndex = i;
            break;
        }
    }

    // 递归地处理左子树和右子树
    postOrder(preorder, inorder, startPre + 1, startPre + rootIndex - startIn, startIn, rootIndex - 1);
    postOrder(preorder, inorder, startPre + rootIndex - startIn + 1, endPre, rootIndex + 1, endIn);

    cout << root << " ";  // 后序遍历根节点
}

解释：

  1. 前序遍历的第一个节点是根节点。
  2. 在中序遍历中，根节点将左右子树分开。
  3. 递归地对左右子树进行相同的操作，最终输出后序遍历结果。

时间复杂度：

  • 每次在中序遍历中查找根节点的时间是O(n)，递归处理子树的总时间复杂度是O(n)，因此总时间复杂度为O(n)。

第二题：AVL树的插入和平衡

问题描述：
给定几个数字，要求插入到AVL平衡树中，并进行平衡操作，通常这涉及到单旋转的操作。

第三题：图的邻接表表示、入度计算和拓扑排序

问题描述：
给定一个有向图，要求用邻接表表示并计算每个节点的入度，最后进行拓扑排序。

答案：

  1. 邻接表表示：
1
2
3
4
5
6
7
// 图的邻接表表示
vector<vector<int>> adjList(n);  // n为节点数
for (int i = 0; i < m; i++) {    // m为边的数量
    int u, v;
    cin >> u >> v;
    adjList[u].push_back(v);  // 从u到v有一条边
}
  1. 计算入度：
1
2
3
4
5
6
vector<int> inDegree(n, 0);  // 初始化入度为0
for (int u = 0; u < n; u++) {
    for (int v : adjList[u]) {
        inDegree[v]++;  // v的入度加1
    }
}
  1. 拓扑排序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
queue<int> q;
for (int i = 0; i < n; i++) {
    if (inDegree[i] == 0) {
        q.push(i);  // 入度为0的节点入队
    }
}

vector<int> topoOrder;
while (!q.empty()) {
    int node = q.front();
    q.pop();
    topoOrder.push_back(node);

    // 更新邻接表中相邻节点的入度
    for (int neighbor : adjList[node]) {
        if (--inDegree[neighbor] == 0) {
            q.push(neighbor);
        }
    }
}

if (topoOrder.size() == n) {
    // 输出拓扑排序结果
    for (int node : topoOrder) {
        cout << node << " ";
    }
} else {
    cout << "图中有环，无法进行拓扑排序" << endl;
}

解释：

  • 邻接表表示：图中的每个节点通过一个数组存储其所有相邻的节点。
  • 入度计算：遍历图的所有边，对每个边的目标节点的入度加1。
  • 拓扑排序：使用Kahn算法，利用一个队列存储入度为0的节点，并逐步减少其相邻节点的入度，直到所有节点被处理。

时间复杂度：

  • 邻接表表示：时间复杂度为O(m)，其中m是边的数量。
  • 计算入度：时间复杂度为O(m)。
  • 拓扑排序：时间复杂度为O(n + m)，其中n是节点数，m是边数。

第四题：哈希和双哈希

问题描述：
给定一些数字，要求将其映射到哈希表中，并使用双哈希法解决冲突。

答案：

  1. 哈希映射：通过哈希函数将数值映射到哈希表中。
  2. 双哈希法：在发生冲突时，使用第二个哈希函数进行再哈希。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#define TABLE_SIZE 10

// 哈希函数
int hash1(int key) {
    return key % TABLE_SIZE;
}

// 双哈希函数
int hash2(int key) {
    return 7 - (key % 7);  // 第二个哈希函数，常用质数7
}

// 插入哈希表
void insert(int hashTable[], int key) {
    int index = hash1(key);
    if (hashTable[index] == -1) {
        hashTable[index] = key;
    } else {
        int i = 1;
        while (hashTable[(index + i * hash2(key)) % TABLE_SIZE] != -1) {
            i++;
        }
        hashTable[(index + i * hash2(key)) % TABLE_SIZE] = key;
    }
}

解释：

  • 哈希函数：使用一个简单的取模运算来将键映射到哈希表的索引。
  • 双哈希：当发生冲突时，使用第二个哈希函数计算步长来查找下一个位置。

时间复杂度：

  • 哈希插入：在最坏情况下

时间复杂度为O(1)，但在发生冲突时，双哈希的时间复杂度可能会变成O(n)，其中n是表的大小。

程序设计题

问题：期末考试分数排序与排名

期末考试结束了，教授想要了解第几名是谁，要求所使用的算法是O(n log n)级别的，且额外的空间开销为O(1)。

（1）你想用什么数据结构，说说你的设计。（10分）

答案： 我们可以使用原地排序算法来解决这个问题，最常用的满足O(n log n)时间复杂度并且额外空间开销为O(1)的排序算法是堆排序。堆排序是一种原地排序算法，使用堆这种数据结构来完成排序，并且它的时间复杂度为O(n log n)，额外空间开销为O(1)。

设计说明：

  • 使用最大堆来组织分数。在最大堆中，父节点的值总是大于或等于其子节点的值，因此根节点是当前堆中的最大元素。
  • 堆排序的过程中，不需要额外的存储空间，只需通过交换堆顶元素和堆的最后一个元素来实现排序。每次调整堆结构，堆的大小减小，直到堆完全排序。

（2）用什么算法？写出伪代码。（10分）

答案： 可以使用堆排序算法，具体的步骤如下：

  1. 构建最大堆。
  2. 交换堆顶元素和堆的最后一个元素。
  3. 减少堆的大小并调整堆。

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
HeapSort(arr):
    // Step 1: Build a max heap
    for i = n/2 - 1 to 0:   // 从最后一个非叶节点开始调整堆
        MaxHeapify(arr, i, n)

    // Step 2: Perform heap sort
    for i = n - 1 down to 1:
        // Swap the root (maximum element) with the last element
        Swap(arr[0], arr[i])
        // Reduce the heap size by 1
        MaxHeapify(arr, 0, i)  // Restore the max heap property

MaxHeapify(arr, i, n):
    left = 2 * i + 1
    right = 2 * i + 2
    largest = i

    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        Swap(arr[i], arr[largest])
        MaxHeapify(arr, largest, n)

解释：

  • Build Max Heap：首先构建最大堆，使得每个父节点大于其子节点，根节点即为最大元素。
  • MaxHeapify：调整堆的结构，确保堆的性质（父节点大于子节点）在交换后依然成立。
  • Swap：交换堆顶元素和最后一个元素，并逐步调整堆的结构以恢复最大堆的性质。

（3）说说你的算法的时间和空间开销。（5分）

答案：

  • 时间复杂度：
    • 建堆（MaxHeapify）需要O(n)时间，具体来说，它从最后一个非叶子节点开始，调整每个节点的堆结构。每次调整操作最多进行O(log n)的比较和交换，因此总时间复杂度为O(n)。
    • 堆排序的主循环需要O(n log n)的时间，因为每次都要执行O(log n)的堆调整操作，而堆调整操作在交换堆顶元素时进行。循环执行n次，因此总时间复杂度为O(n log n)。
  • 空间复杂度：
    • 堆排序是一个原地排序算法，其主要的空间开销仅用于存储输入数组，不需要额外的存储空间。
    • 除了输入数组，算法没有额外的数据结构开销，所有的操作都在输入数组上进行，因此空间复杂度为O(1)（不包括输入数组的存储空间）。

总结：

  • 时间复杂度：O(n log n)
  • 空间复杂度：O(1)