参考答案及解析

阅读程序 (1) 素数筛选与统计

判断题

1. √ 程序使用埃拉托斯特尼筛法标记素数
2. × n=20时，素数有2,3,5,7,11,13,17,19共8个，输出为8
3. √ 埃拉托斯特尼筛法的时间复杂度为O(n log log n)

选择题 4. C n=30时，素数有2,3,5,7,11,13,17,19,23,29共10个 5. A 将j=i2改为j=ii是筛法的优化，不影响结果但提高效率

阅读程序 (2) 二叉树遍历

判断题

1. √ 前序遍历顺序正确
2. √ 中序遍历顺序正确
3. × 前序遍历结果应为1 2 4 5 3

选择题 4. A 中序遍历结果：4 2 5 1 3 5. B 后序遍历顺序：左子树 -> 右子树 -> 根节点

阅读程序 (3) 动态规划-斐波那契数列

判断题

1. √ 使用动态规划计算斐波那契数列
2. √ 斐波那契数列定义正确
3. √ 修改递推公式将计算不同的数列

选择题 4. B F(6)=8 5. B 时间复杂度为O(n)

阅读程序 (4) 快速排序算法

判断题

1. × 快速排序是不稳定的排序算法
2. × pivot选择的是最后一个元素
3. √ 最坏情况时间复杂度是O(n²)

选择题 4. B 平均时间复杂度是O(n log n) 5. B 已排序数组是快速排序的最坏情况

阅读程序 (5) 图的广度优先搜索

判断题

1. × BFS使用队列而不是栈
2. √ visited数组用于标记已访问节点
3. √ BFS可以用于无权图的最短路径查找

选择题 4. C BFS的时间复杂度是O(n + m) 5. B visited数组确保每个节点只访问一次，不会陷入无限循环

参考程序及详细解析

程序1：素数筛选完整实现

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

int main() {
    int n;
    cin >> n;
    
    // 使用埃拉托斯特尼筛法
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            // 从i*i开始标记，因为2*i, 3*i, ..., (i-1)*i已经被标记过了
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    
    // 统计素数个数
    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            count++;
        }
    }
    
    cout << count << endl;
    return 0;
}

解析：埃拉托斯特尼筛法通过标记倍数来筛选素数，优化后从i²开始标记，时间复杂度O(n log log n)。

程序2：二叉树三种遍历完整实现

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

struct Node {
    int value;
    Node* left;
    Node* right;
    Node(int v) : value(v), left(nullptr), right(nullptr) {}
};

void preorder(Node* root, vector<int>& result) {
    if (root == nullptr) return;
    result.push_back(root->value);
    preorder(root->left, result);
    preorder(root->right, result);
}

void inorder(Node* root, vector<int>& result) {
    if (root == nullptr) return;
    inorder(root->left, result);
    result.push_back(root->value);
    inorder(root->right, result);
}

void postorder(Node* root, vector<int>& result) {
    if (root == nullptr) return;
    postorder(root->left, result);
    postorder(root->right, result);
    result.push_back(root->value);
}

int main() {
    // 构建示例二叉树
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    
    vector<int> pre, in, post;
    preorder(root, pre);
    inorder(root, in);
    postorder(root, post);
    
    cout << "前序遍历: ";
    for (int num : pre) cout << num << " ";
    cout << endl;
    
    cout << "中序遍历: ";
    for (int num : in) cout << num << " ";
    cout << endl;
    
    cout << "后序遍历: ";
    for (int num : post) cout << num << " ";
    cout << endl;
    
    return 0;
}

解析：二叉树遍历是基础算法，前序（根左右）、中序（左根右）、后序（左右根）有不同的应用场景。

程序3：动态规划多种实现

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

// 递归方法（不推荐，效率低）
int fib_recursive(int n) {
    if (n <= 1) return n;
    return fib_recursive(n - 1) + fib_recursive(n - 2);
}

// 动态规划方法
int fib_dp(int n) {
    if (n <= 1) return n;
    
    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

// 空间优化方法
int fib_optimized(int n) {
    if (n <= 1) return n;
    
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    
    return b;
}

int main() {
    int n;
    cin >> n;
    
    cout << "递归结果: " << fib_recursive(n) << endl;
    cout << "动态规划结果: " << fib_dp(n) << endl;
    cout << "优化空间结果: " << fib_optimized(n) << endl;
    
    return 0;
}

解析：展示了斐波那契数列的三种实现方法，重点理解动态规划的思想和空间优化技巧。

程序4：快速排序优化实现

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

// 随机选择pivot的partition函数
int partition(vector<int>& arr, int low, int high) {
    // 随机选择pivot，避免最坏情况
    int random = low + rand() % (high - low + 1);
    swap(arr[random], arr[high]);
    
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    srand(time(0)); // 设置随机种子
    
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    quickSort(arr, 0, n - 1);
    
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    return 0;
}

解析：优化版快速排序通过随机选择pivot避免最坏情况，保持平均O(n log n)的时间复杂度。

程序5：BFS最短路径实现

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

// BFS求最短路径
vector<int> BFS_shortest_path(vector<vector<int>>& graph, int start) {
    int n = graph.size();
    vector<int> distance(n, -1); // -1表示不可达
    queue<int> q;
    
    distance[start] = 0;
    q.push(start);
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        for (int neighbor : graph[node]) {
            if (distance[neighbor] == -1) { // 未访问过
                distance[neighbor] = distance[node] + 1;
                q.push(neighbor);
            }
        }
    }
    
    return distance;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n);
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u); // 无向图
    }
    
    int start;
    cin >> start;
    
    vector<int> distances = BFS_shortest_path(graph, start);
    
    cout << "从节点" << start << "到各节点的最短距离:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "节点" << i << ": " << distances[i] << endl;
    }
    
    return 0;
}

解析：BFS可以用于无权图的最短路径查找，通过记录每个节点的距离来实现。

这套模拟题涵盖了普及组常见的算法知识点，包括素数筛选、二叉树遍历、动态规划、快速排序和BFS等，题目难度和风格与原始卷子保持一致，全部为判断题和选择题。