华南理工大学15年数据结构A卷

数据结构15A

这应该也会是一张有趣的试卷。

归并排序程序填空

需要了解一下归并排序的原理，如果可以背诵一下代码就更好了。

问题：填写 C++ 代码以实现 Mergesort 算法

给定一个模板函数框架来实现 归并排序（Mergesort），需要填充以下空白部分。

template <class Elem, class Comp>
void mergesort(Elem A[], Elem temp[],
               int left, int right) {
  int mid = ____①_____; 
  if (____②___) return; 
  mergesort<Elem,Comp>(A, temp, left, mid);
  mergesort<Elem,Comp>(A, temp, mid+1, right);
  for (int i=left; i<=right; i++) // Copy
    temp[i] = A[i];
  int i1 = left; int i2 = mid + 1;
  for (int curr=left; curr<=right; curr++) {
    if (i1 == mid+1)      // Left exhausted
      A[curr] = ____③_____ ;
    else if (i2 > right)  // Right exhausted
      A[curr] = ___ ④_____; 
    else if (Comp::lt(temp[i1], temp[i2]))
      A[curr] =  ____⑤_____; 
    else A[curr] = ____⑥_____; 
}

解答：

1. 填写 ①（计算中间位置 mid）：

mid 是当前子数组的中间位置，它的计算方法是：

mid = (left + right) / 2;

这将 left 和 right 之间的范围对半分割，为递归的子数组创建两个部分。

2. 填写 ②（递归终止条件）：

当 left 等于 right 时，表示子数组中只剩下一个元素，不需要进一步分割，排序已经完成。递归的终止条件是：

if (left >= right) return;

3. 填写 ③（左子数组已耗尽时的处理）：

如果左侧的部分已经完全合并，剩下的元素都在右侧，因此需要将右侧的当前元素复制到原数组：

A[curr] = temp[i2++];

这将从右侧的数组中取出元素填充回原数组 A。

4. 填写 ④（右子数组已耗尽时的处理）：

如果右侧的部分已经完全合并，剩下的元素都在左侧，因此需要将左侧的当前元素复制到原数组：

A[curr] = temp[i1++];

这将从左侧的数组中取出元素填充回原数组 A。

5. 填写 ⑤（当左侧元素小于右侧元素时的处理）：

如果当前左侧的元素小于右侧的元素，则将左侧元素复制到原数组：

A[curr] = temp[i1++];

6. 填写 ⑥（当右侧元素小于左侧元素时的处理）：

如果当前右侧的元素小于左侧的元素，则将右侧元素复制到原数组：

A[curr] = temp[i2++];

完整的代码：

template <class Elem, class Comp>
void mergesort(Elem A[], Elem temp[],
               int left, int right) {
  int mid = (left + right) / 2;  // ①
  if (left >= right) return;  // ②
  mergesort<Elem,Comp>(A, temp, left, mid);
  mergesort<Elem,Comp>(A, temp, mid+1, right);
  
  // Copy data to temp[]
  for (int i = left; i <= right; i++)  // Copy
    temp[i] = A[i];
  
  int i1 = left; 
  int i2 = mid + 1;
  
  // Merge the two sorted halves
  for (int curr = left; curr <= right; curr++) {
    if (i1 == mid + 1)  // Left exhausted
      A[curr] = temp[i2++];  // ③
    else if (i2 > right)  // Right exhausted
      A[curr] = temp[i1++];  // ④
    else if (Comp::lt(temp[i1], temp[i2]))
      A[curr] = temp[i1++];  // ⑤
    else
      A[curr] = temp[i2++];  // ⑥
  }
}

解释：

1. 步骤 ①：计算中间位置 mid，将当前区间 [left, right] 分成两部分。
2. 步骤 ②：递归的终止条件，当数组只有一个元素时不再进行分割。
3. 步骤 ③：当左子数组已处理完毕，剩下的都是右子数组的元素，直接从右子数组中取出元素。
4. 步骤 ④：当右子数组已处理完毕，剩下的都是左子数组的元素，直接从左子数组中取出元素。
5. 步骤 ⑤：如果左子数组的当前元素小于右子数组的当前元素，将左子数组的元素放入原数组。
6. 步骤 ⑥：如果右子数组的当前元素小于左子数组的当前元素，将右子数组的元素放入原数组。

总结：

该代码实现了 归并排序（Mergesort）算法，递归地将数组分成两部分，直到每部分只有一个元素，然后再合并这些部分。在合并过程中使用辅助数组 temp[]，逐一比较左右子数组的元素，最终将有序的元素合并回原数组 A[]。

最小生成树

Prim's algorithm for finding the minimum-cost spanning tree starts with a given vertex and grows the tree one edge at a time, always choosing the edge with the smallest weight that connects a vertex in the tree to a vertex outside the tree.

Given the vertices and the order $ a, b, e, c, d $, let's proceed with Prim's algorithm step by step:

1. Start at vertex $ a $:
   • Begin with vertex $ a $.
2. Choose the next vertex $ b $:
   • Select the edge $ (a, b) $ with weight $ 2 $.
3. Choose the next vertex $ e $:
   • Select the edge $ (a, e) $ with weight $ 3 $.
4. Choose the next vertex $ c $:
   • Select the edge $ (e, c) $ with weight $ 4 $.
5. Choose the next vertex $ d $:
   • Select the edge $ (c, d) $ with weight $ 5 $.

img

简单的BFS代码书写

问题描述：

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

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

输入：一棵二叉树。

输出：按照广度优先顺序遍历二叉树的节点。

解题思路：

广度优先搜索（BFS）是一种逐层遍历树或图的算法。具体实现时，可以使用队列来辅助进行层次遍历。遍历的顺序是先访问根节点，然后访问其左右子节点，依此类推。

C++代码：

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

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

// 广度优先搜索（BFS）遍历
void bfs(TreeNode* root) {
    if (root == nullptr) {
        return;  // 如果树为空，直接返回
    }
    
    queue<TreeNode*> q;  // 创建队列来辅助BFS
    q.push(root);  // 将根节点加入队列
    
    while (!q.empty()) {
        TreeNode* node = q.front();  // 获取队列的第一个节点
        q.pop();  // 弹出队列的第一个节点
        cout << node->data;  // 输出当前节点的数据
        
        // 将当前节点的左右子节点加入队列（如果存在）
        if (node->left != nullptr) {
            q.push(node->left);
        }
        if (node->right != nullptr) {
            q.push(node->right);
        }
    }
}

int main() {
    // 构建二叉树
    TreeNode* root = new TreeNode('A');
    root->left = new TreeNode('B');
    root->right = new TreeNode('C');
    root->left->left = new TreeNode('D');
    root->left->right = new TreeNode('E');
    root->right->left = new TreeNode('F');
    root->right->right = new TreeNode('G');
    
    // 调用BFS遍历并输出结果
    cout << "BFS遍历结果: ";
    bfs(root);
    cout << endl;
    
    return 0;
}

解释：

1. TreeNode结构体：定义了二叉树的节点结构，包含一个字符类型的数据域 data，以及指向左右子节点的指针 left 和 right。

2. bfs函数：实现了广度优先搜索的核心部分。通过队列 queue<TreeNode*> q 来辅助遍历树节点。首先，将根节点入队，然后逐层遍历树，输出每个节点的数据，并将该节点的左右子节点（如果存在）加入队列。

3. 主函数：创建了一个二叉树并调用 bfs 函数来进行广度优先遍历，最后输出遍历结果。

输出：

BFS遍历结果: ABCDEFG

时间复杂度：

• 由于每个节点只访问一次，因此时间复杂度是 O(n)，其中 n 是二叉树的节点数。

空间复杂度：

• 由于使用了队列来存储节点，空间复杂度是 O(n)，最坏情况下队列中存储的是树的最后一层节点。