2024信息学奥赛CSP-J考试真题测试

一、单项选择题（共15题，每题2分，共计30分）

每题有且仅有一个正确选项，选择后点击“提交核对”查看答案及解析

二、阅读程序（共计40分）

判断题正确填√，错误填×；除特殊说明外，判断题1.5分，选择题3分

（1）素数统计程序

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int countPrimes(int n) {
    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (isPrime(i)) {
            count++;
        }
    }
    return count;
}

int sumPrimes(int n) {
    int sum = 0;
    for (int i = 2; i <= n; i++) {
        if (isPrime(i)) {
            sum += i;
        }
    }
    return sum;
}

int main() {
    int x;
    cin >> x;
    cout << countPrimes(x) << " " << sumPrimes(x) << endl;
    return 0;
}

（2）最小成本路径程序

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

int compute(vector<int> &cost) {
    int n = cost.size();
    vector<int> dp(n + 1, 0);
    dp[1] = cost[0];
    
    for (int i = 2; i <= n; i++) {
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i - 1];
    }
    
    return min(dp[n], dp[n - 1]);
}

int main() {
    int n;
    cin >> n;
    vector<int> cost(n);
    
    for (int i = 0; i < n; i++) {
        cin >> cost[i];
    }
    
    cout << compute(cost) << endl;
    return 0;
}

（3）递归求和程序

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

int customFunction(int a, int b) {
    if (b == 0) {
        return a;
    }
    return a + customFunction(a, b - 1);
}

int main() {
    int x, y;
    cin >> x >> y;
    int result = customFunction(x, y);
    cout << pow(result, 2) << endl;
    return 0;
}

三、完善程序（单选题，每小题3分，共计30分）

根据题目要求，从每题给出的四个选项中，选出最恰当的一项填入空白处

（1）判断平方数

问题：给定一个正整数 n，判断这个数是不是完全平方数，即存在一个正整数 x 使得 x 的平方等于 n。试补全程序。

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

bool isSquare(int num) {
    int i = ①;
    int bound = ②;
    for (; i <= bound; ++i) {
        if (③) {
            return ④;
        }
    }
    return ⑤;
}

int main() {
    int n;
    cin >> n;
    if (isSquare(n)) {
        cout << n << " is a Square number" << endl;
    } else {
        cout << n << " is not a Square number" << endl;
    }
    return 0;
}

（2）汉诺塔问题

给定三根柱子，分别标记为A、B和C。初始状态下，柱子A上有若干个圆盘，这些圆盘从上到下按从小到大的顺序排列。任务是将这些圆盘全部移到柱子C上，且必须保持原有顺序不变。在移动过程中，需要遵守以下规则：1. 只能从一根柱子的顶部取出圆盘，并将其放入另一根柱子的顶部；2. 每次只能移动一个圆盘；3. 小圆盘必须始终在大圆盘之上。试补全程序。

#include <bits/stdc++.h>
using namespace std;

void move(char src, char tgt) {
    cout << "从柱子" << src << "挪到柱子上" << tgt << endl;
}

void dfs(int i, char src, char tmp, char tgt) {
    if (i == ①) {
        move(②);
        return;
    }
    dfs(i-1, ③);
    move(src, tgt);
    dfs(⑤, ④);
}

int main() {
    int n;
    cin >> n;
    dfs(n, 'A', 'B', 'C');
}