普及组程序专项02

二、阅读程序

(1) 素数筛选与统计

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

int main() {
    int n;
    cin >> n;
    vector<bool> is_prime(n + 1, true);
    vector<int> prime_count(n + 1, 0);
    
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * 2; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    
    for (int i = 2; i <= n; i++) {
        prime_count[i] = prime_count[i - 1];
        if (is_prime[i]) {
            prime_count[i]++;
        }
    }
    
    cout << prime_count[n] << endl;
    return 0;
}

判断题

1. 该程序使用埃拉托斯特尼筛法来标记素数。 ( )
2. 若输入n为20，则程序输出为7。 ( )
3. 该程序的时间复杂度为O(n log log n)。 ( )

选择题 4. 若输入n为30，则输出为（ ）。 A. 8 B. 9 C. 10 D. 11

5. 如果将第8行的j = i * 2改为j = i * i，对于输入n=20，程序的输出将会（ ）。 A. 不变 B. 变大 C. 变小 D. 程序会出错

(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);
}

int main() {
    // 构建二叉树: 
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    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;
    preorder(root, pre);
    inorder(root, in);
    
    cout << "前序遍历: ";
    for (int num : pre) cout << num << " ";
    cout << endl;
    
    cout << "中序遍历: ";
    for (int num : in) cout << num << " ";
    cout << endl;
    
    return 0;
}

判断题

1. 前序遍历的顺序是：根节点 -> 左子树 -> 右子树。 ( )
2. 中序遍历的顺序是：左子树 -> 根节点 -> 右子树。 ( )
3. 对于给定的二叉树，前序遍历结果是1 2 4 5 3。 ( )

选择题 4. 该二叉树的中序遍历结果是（ ）。 A. 4 2 5 1 3 B. 1 2 4 5 3 C. 4 5 2 3 1 D. 3 1 4 2 5

5. 如果要将后序遍历加入程序，后序遍历的顺序应该是（ ）。 A. 根节点 -> 左子树 -> 右子树 B. 左子树 -> 右子树 -> 根节点 C. 左子树 -> 根节点 -> 右子树 D. 右子树 -> 左子树 -> 根节点

(3) 动态规划-斐波那契数列

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

int main() {
    int n;
    cin >> n;
    
    if (n <= 1) {
        cout << n << endl;
        return 0;
    }
    
    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];
    }
    
    cout << dp[n] << endl;
    return 0;
}

判断题

1. 该程序使用动态规划方法计算斐波那契数列的第n项。 ( )
2. 斐波那契数列的定义是：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。 ( )
3. 如果将第13行的dp[i] = dp[i - 1] + dp[i - 2]改为dp[i] = dp[i - 1] + dp[i - 2] + 1，程序将计算不同的数列。 ( )

选择题 4. 若输入n为6，则输出为（ ）。 A. 5 B. 8 C. 13 D. 21

5. 该程序的时间复杂度是（ ）。 A. O(1) B. O(n) C. O(n²) D. O(2ⁿ)

(4) 快速排序算法

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

int partition(vector<int>& arr, int low, int 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() {
    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;
}

判断题

1. 快速排序是一种稳定的排序算法。 ( )
2. 在partition函数中，pivot元素选择的是数组的第一个元素。 ( )
3. 快速排序的最坏情况时间复杂度是O(n²)。 ( )

选择题 4. 快速排序的平均时间复杂度是（ ）。 A. O(n) B. O(n log n) C. O(n²) D. O(log n)

5. 如果输入数组已经是升序排列，快速排序的性能会（ ）。 A. 最好 B. 最差 C. 平均 D. 不确定

(5) 图的广度优先搜索

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

void BFS(vector<vector<int>>& graph, int start) {
    int n = graph.size();
    vector<bool> visited(n, false);
    queue<int> q;
    
    visited[start] = true;
    q.push(start);
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

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;
    BFS(graph, start);
    
    return 0;
}

判断题

1. BFS使用栈数据结构来存储待访问的节点。 ( )
2. 在BFS中，我们使用visited数组来标记节点是否已被访问。 ( )
3. BFS可以用于寻找图中的最短路径。 ( )

选择题 4. 对于有n个顶点和m条边的图，BFS的时间复杂度是（ ）。 A. O(n) B. O(m) C. O(n + m) D. O(n × m)

5. 如果图中存在环，BFS算法会（ ）。 A. 陷入无限循环 B. 正常结束 C. 抛出异常 D. 跳过环中的节点