ID: 1398

客观题

难度: 9

上传者:

Teacher_chen

标签>

CSP-J1

CSP 2025 入门级第一轮

第 1 题

一个 $32$ 位无符号整数可以表示的最大值，最接近下列哪个选项？（ {{ select(1) }}）

$4 \times 10^9$
$3 \times 10^{10}$
$2 \times 10^9$
$2 \times 10^{10}$

第 2 题

在 C++ 中，执行 int x = 255; cout << (x & (x - 1)); 后，输出的结果是？（ {{ select(2) }}）

$255$
$254$
$128$
$0$

第 3 题

函数 calc(n) 的定义如下，则 calc(5) 的返回值是多少？（）

int calc(int n) {
    if (n <= 1) return 1;
    if (n % 2 == 0) return calc(n / 2) + 1;
    else return calc(n - 1) + calc(n - 2);
}

（ {{ select(3) }}）

第 4 题

用 $5$ 个权值 $10, 12, 15, 20, 25$ 构造哈夫曼树，该树的带权路径长度是多少？（ {{ select(4) }}）

$176$
$186$
$196$
$206$

第 5 题

在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于？（ {{ select(5) }}）

顶点数
边数
顶点数 + 边数
顶点数 $\times 2$

第 6 题

从 $5$ 位男生和 $4$ 位女生中选出 $4$ 人组成一个学习小组，要求学习小组中男生和女生都有。有多少种不同的选法？（ {{ select(6) }}）

$126$
$121$
$120$
$100$

第 7 题

假设 $a, b, c$ 都是布尔变量，逻辑表达式 (a && b) || (!c && a) 的值与下列哪个表达式不始终相等？（ {{ select(7) }}）

a && (b || !c)
(a || !c) && (b || !c) && (a || a)
a && (!b || c)
!(!a || !b) || (a && !c)

第 8 题

已知 $f[0] = 1$ , $f[1] = 1$ ，并且对于所有 $n \geq 2$ 有 $f[n] = (f[n-1] + f[n-2]) \% 7$ 。那么 $f[2025]$ 的值是多少？（ {{ select(8) }}）

第 9 题

下列关于 C++ string 类的说法，正确的是？（ {{ select(9) }}）

string 对象的长度在创建后不能改变。
可以使用 + 运算符直接连接一个 string 对象和一个 char 类型的字符。
string 的 length() 和 size() 方法返回的值可能不同。
string 对象必须以 '\0' 结尾，且这个结尾符计入 length()。

第 10 题

考虑以下 C++ 函数：

void solve(int &a, int b) {
    a = a + b;
    b = a - b;
    a = a - b;
}
int main() {
    int x = 5, y = 10;
    solve(x, y);
}

（ {{ select(10) }}）在 main 函数调用 solve 后， $x$ 和 $y$ 的值分别是？

$5,10$
$10,5$
$10,10$
$5,5$

第 11 题

一个 $8 \times 8$ 的棋盘，左上角坐标为 $(1,1)$ ，右下角为 $(8,8)$ 。一个机器人从 $(1,1)$ 出发，每次只能向右或向下走一格。要到达 $(4,5)$ ，有多少种不同的路径？（ {{ select(11) }}）

$20$
$35$
$56$
$70$

第 12 题

某同学用冒泡排序对数组 $\{6, 1, 5, 2, 4\}$ 进行升序排序，请问需要进行多少次元素交换？（ {{ select(12) }}）

第 13 题

十进制数 $720_{10}$ 和八进制数 $270_8$ 的和用十六进制表示是多少？（ {{ select(13) }}）

$388_{16}$
$3DE_{16}$
$288_{16}$
$990_{16}$

第 14 题

一棵包含 $1000$ 个结点的完全二叉树，其叶子结点的数量是多少？（ {{ select(14) }}）

$499$
$512$
$500$
$501$

第 15 题

给定一个初始为空的整数栈 $S$ 和一个空的队列 $P$ 。我们按顺序处理输入的整数队列 $A: 7, 5, 8, 3, 1, 4, 2$ 。对于队列 $A$ 中的每一个数，执行以下规则：如果该数是奇数，则将其压入栈 $S$ ；如果该数是偶数，且栈 $S$ 非空，则弹出一个栈顶元素，并加入到队列 $P$ 的末尾；如果该数是偶数，且栈 $S$ 为空，则不进行任何操作。当队列 $A$ 中的所有数都处理完毕后，队列 $P$ 的内容是什么？（ {{ select(15) }}）

$5,1,3$
$7,5,3$
$3,1,5$
$5,1,3,7$

第 16 题

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 A，错误填 B；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

#include <algorithm>
#include <cstdio>
#include <cstring>
inline int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
int main() {
    int n;
    scanf("%d", &n);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            for (int k = j + 1; k <= n; ++k) {
                if (gcd(i, j) == 1 && gcd(j, k) == 1 && gcd(i, k) == 1) {
                    ++ans;
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

判断题

16.（ $1$ 分）当输入为 $2$ 时，程序并不会执行第 $16$ 行的判断语句。（ {{ input(16) }}）
17. 将第 $16$ 行中的 && gcd(i,k)==1 删去不会影响程序运行结果。（ {{ input(17) }}）
18. 当输入的 $n \geq 3$ 的时候，程序总是输出一个正整数。（ {{ input(18) }}）

单选题

将第 $7$ 行的 gcd(b, a%b) 改为 gcd(a, a%b) 后，程序可能出现的问题是（ {{ select(19) }}）。

输出的答案大于原答案。
输出的答案小于原答案。
程序有可能陷入死循环。
可能发生整型溢出问题。

当输入为 $8$ 的时候，输出为（ {{ select(20) }}）。

$37$
$42$
$35$
$25$

调用 $\gcd(36, 42)$ 会返回（ {{ select(21) }}）。

$6$
$252$
$3$
$2$

第 17 题

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int n, k;
int a[200007];
int ans[200007];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    std::sort(a + 1, a + n + 1);
    n = std::unique(a + 1, a + n + 1) - a - 1;
    for (int i = 1, j = 0; i <= n; ++i) {
        for (; j < i && a[i] - a[j + 1] > k; ++j) 
            ;
        ans[i] = ans[j] + 1;
    }
    printf("%d\n", ans[n]);
    return 0;
}

判断题

当输入为 3 1 3 2 1 时，输出结果为 $2$ 。（{{ input(22) }} ）
假设输入的 $n$ 为正整数，输出的答案一定小于等于 $n$ ，大于等于 $1$ 。（ {{ input(23) }}）
将第 14 行的 n = std::unique(a + 1, a + n + 1) - a - 1; 删去后，有可能出现与原本代码不同的输出结果。（{{ input(24) }} ）

单选题

假设输入的 $a$ 数组和 $k$ 均为正整数，执行第 18 行代码时，一定满足的条件不包括（ {{ select(25) }}）。

$j < i$
$a[i] - a[j] > k$
$j < n$
$a[j] < a[i]$

当输入的 $n=100$ 、 $k=2$ 、 $a = \{1, 2, \dots, 100\}$ 时，输出为（ {{ select(26) }}）。

$34$
$100$
$50$
$33$

假设输入的 $a$ 数组和 $k$ 均为正整数，但 $a$ 数组不一定有序，则若误删去第 13 行的 std::sort(a + 1, a + n + 1);，程序有可能出现的问题有（ {{ select(27) }}）。

输出的答案比原本答案更大
输出的答案比原本答案更小
出现死循环行为
以上均可能发生

第 18 题

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int f[5007][5007];
int a[5007], b[5007];
int n;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &b[i]);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            f[i][j] = std::max(f[i][j], std::max(f[i - 1][j], f[i][j - 1]));
            if (a[i] == b[j]) {
                f[i][j] = std::max(f[i][j], f[i - 1][j - 1] + 1);
            }
        }
    }
    printf("%d\n", f[n][n]);
    return 0;
}

判断题

当输入 4 1 2 3 4 1 3 2 2 时，输出为 2。（ {{ input(28) }}）
当程序运行完毕后，对于所有的 $1 \leq i, j \leq n$ ，都一定有 $f[i][j] \leq f[n][n]$ 。（ {{ input(29) }}）
将第 18 行的 f[i][j] = std::max(f[i][j], std::max(f[i-1][j], f[i][j-1])); 删去后，并不影响程序运行结果。（{{ input(30) }} ）

单选题

输出的答案满足的性质有（ {{ select(31) }}）。

小于等于 $n$
大于等于 $0$
不一定大于等于 $1$
以上均是

如果在 16 行的循环前加上以下两行：

std::sort(a+1, a+n+1);  
std::sort(b+1, b+n+1);

则答案会（ {{ select(32) }}）。

变大或不变
变小或不变
一定变大
不变

（本题在原卷中被删除）如果输入的 $a = \{1, 2, \dots, n\}$ ，而且 $b$ 数组中数字均为 $1 \sim n$ 中的正整数，则上述代码等价于下面哪个问题：（ {{ select(33) }}）。

求 $b$ 数组去重后的长度
求 $b$ 数组的最长上升子序列
求 $b$ 数组的长度
求 $b$ 数组的最大值

第 19 题

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

（1）（字符串解码）“行程长度编码”（Run-Length Encoding）是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符。压缩规则如下：i) 如果原始字符串中一个字符连续出现 $N$ 次（ $N \geq 2$ ），在压缩字符串中它被表示为“字符 + 数字 $N$ ”。例如，编码 A12 代表 $12$ 个连续的字符 A。ii) 如果原始字符串中一个字符只出现 $1$ 次，在压缩字符串中它就表示为该字符本身。例如，编码 B 代表 $1$ 个字符 B。

以下程序实现读取压缩字符串并输出其原始的、解压后的形式。试补全程序。

#include <cctype>
#include <iostream>
#include <string>
using namespace std;

int main() {
    string z;
    cin >> z;
    string s = "";

    for (int i = 0; i < z.length(); ) {
        char ch = z[i];

        if (__①__ && isdigit(z[i + 1])) {
            i++;
            int count = 0;
            while (i < z.length() && isdigit(z[i])) {
                count = __②__;
                i++;
            }
            for (int j = 0; j < __③__; ++j) {
                s += ch;
            }
        } else {
            s += __④__;
            __⑤__;
        }
    }

    cout << s << endl;
    return 0;
}

①处应填（ {{ select(34) }}）

i < z.length()
i - 1 >= 0
i + 1 < z.length()
isdigit(z[i])

②处应填（ {{ select(35) }}）

count + (z[i] - '0')
count * 10 + (z[i] - '0')
z[i] - '0'
count + 1

③处应填（ {{ select(36) }}）

count - 1
count
10
z[i] - '0'

④处应填（ {{ select(37) }}）

z[i+1]
ch
z.back()
(char)z[i] + 1

⑤处应填（ {{ select(38) }}）

i--
i = i + 2
i++
// 不执行任何操作

第 20 题

（2）（精明与糊涂）有 $N$ 个人，分为两类：
i) 精明人：永远能正确判断其他人是精明还是糊涂；
ii)糊涂人：判断不可靠，会给出随机的判断。

已知精明人严格占据多数，即如果精明人有 $k$ 个，则满足 $k > N/2$ 。

你只能通过函数 $\text{query}(i, j)$ 让第 $i$ 个人判断第 $j$ 个人：返回 $\text{true}$ 表示判断结果为“精明人”；返回 $\text{false}$ 表示判断结果为“糊涂人”。你的目标是，通过这些互相判断，找出至少一个百分之百确定的精明人。同时，你无需关心 $\text{query}(i, j)$ 的内部实现。

以下程序利用“精明人占多数”的优势。设想一个“消除”的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选人必然属于多数派，即精明人。

例如，假设有三人 $0, 1, 2$ 。如果 $0$ 说 $1$ 是糊涂人，而 $1$ 也说 $0$ 是糊涂人，则 $0$ 和 $1$ 至少有一个是糊涂人。程序将同时淘汰 $0$ 和 $1$ 。由于三人里至少有两个精明人，我们确定 $2$ 是精明人。

试补全程序。

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

int N;
bool query(int i, int j);

int main() {
    cin >> N;

    int candidate = 0;
    int count = __①__;
    for (int i = 1; i < N; ++i) {
        if (__②__) {
            candidate = i;
            count = 1;
        } else {
            if (__③__) {
                __④__;
            } else {
            count++;
            }
        }
    }
    cout << __⑤__ << endl;
    return 0;
}

①处应填（ {{ select(39) }}）

0
1
N
-1

②处应填（ {{ select(40) }}）

count < 0
count == 1
count == 0
query(candidate, i) == false

③处应填（ {{ select(41) }}）

query(candidate, i) == false
query(i, candidate) == true
query(candidate, i) == false && query(i, candidate) == false
query(candidate, i) == false || query(i, candidate) == false

④处应填（ {{ select(42) }}）

count--
break
count++
candidate = i

⑤处应填（ {{ select(43) }}）

N - 1
count
candidate
0

#P1395. CSP 2025 入门级第一轮

CSP 2025 入门级第一轮

CSP 2025 入门级第一轮

第 1 题

第 2 题

第 3 题

第 4 题

第 5 题

第 6 题

第 7 题

第 8 题

第 9 题

第 10 题

第 11 题

第 12 题

第 13 题

第 14 题

第 15 题

第 16 题

阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 A，错误填 B；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

判断题

单选题

第 17 题

判断题

单选题

第 18 题

判断题

单选题

第 19 题

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

第 20 题

登录