CSP-J 2025 入门级 第一轮试题（初赛）答案及解析

一、单项选择题

1. 一个 $32$ 位无符号整数可以表示的最大值，最接近下列哪个选项？（ ）。
   A. $4\times 10^9$
   B. $3\times 10^{10}$
   C. $2\times 10^9$
   D. $2\times 10^{10}$

正确答案：A
无符号整数的机器数没有符号位，每一位都可以表示数值。推导$n$位无符号整数表示数值的范围：
当机器数每位都为0时，该机器数表示的真值为$0$
当机器数每位都为1时，该机器数表示的数值最大，共$n$位1，$n$位1再加1后得到二进制数为1后有$n$个0，表示的数值为$2^n$，那么$n$位1表示的数值为$2^n-1$。
因此32位无符号整数可以表示的最大值为$2^{32}-1=4,294,967,295\approx 4\ast 10^9$
考试时手算，首先应该知道$2^{10}=1024\approx 10^3$，那么$2^{32}=2^{30}\ast 2^2=(2^{10}{)}^3\ast 4\approx 4\ast (10^3{)}^3=4\ast 10^9$
或者如果你已经背过int类型可以表示的数值范围大概为$-2\ast 10^9\sim 2\ast 10^9$，int是32位有符号整型，unsigned int为32位无符号整型，其表示的数值个数相同，因为是无符号整数，只能表示非负数，相当于把可以表示的数值区间在数轴上右移，一共大约为$4\ast 10^9$个数，当可以表示的最小值为0时，最大值自然为大概$4\ast 10^9$。选A。

2. 在 C++ 中，执行 int x = 255; cout << (x & (x - 1)); 后，输出的结果是？（ ）
   A. 255
   B. 254
   C. 128
   D. 0

正确答案：B
在$x>0$的前提下，记$x$的机器数（补码）形式为$0D...D\mathrm{10...0}$，其中$D$表示0或1，不同位置的$D$未必相同。其中出现的1是$x$在二进制下最低位的1，其后有若干位0（也可能没有0）。
那么$x-1$的机器数为$0D...D\mathrm{01...1}$
二者进行按位与运算，结果为：
_ $0D...D\mathrm{10...0}$
& $0D...D\mathrm{01...1}$
_ $0D...D\mathrm{0.....0}$
结果相比于$x$，少了最低位的$1$
在数值上看，$x$的值减少了最低位的1及其后面的0组成的数值，该值位最低位1的位权。
将255转为二进制，得11111111。（简单方法：已知$256=2^8$，其二进制为1后面8个0。再减1，得到255的二进制数为8个1）
x & (x-1) ，就是$x$减去其最低位的1的位权，255最低位1的位权为1，因此x & (x-1)的值为$255-1=254$，选B。

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

A. 5
B. 6
C. 7
D. 8

正确答案：B
递归函数求值的方法为：变递归为递推。
与该递归函数等价的递推过程为：
设$a_i=calc(i)$

int a[105];
a[1] = 1;
if(n%2 == 0)
	a[i] = a[i/2]+1;
else
	a[i] = a[i-1]+a[i-2];

手算完成递推：
$a_1=1$
$a_2=a_1+1=2$
$a_3=a_2+a_1=3$
$a_4=a_2+1=3$
$a_5=a_4+a_3=6$
因此$calc(5)=6$，选B。

4. 用 5 个权值 $10,12,15,20,25$ 构造哈夫曼树，该树的带权路径长度是多少？（ ）
   A. $176$
   B. $186$
   C. $196$
   D. $206$

正确答案：B
构造哈夫曼树的方法为：初始时每个结点为一棵树，该树的权值为结点上的权值。每次选择权值最小的两棵树进行合并，合并后得到的树的权值为两棵子树权值加和。
根据题目中给定的权值构建哈夫曼树：

结点的带权路径长度为：根到该结点的路径长度（路径上边的数目）乘以该结点的权值。
树的带权路径长度为每个叶子结点的带权路径长度之和。
根到10,12的路径长度为3，到25,15,20的路径长度为2。
因此该树的带权路径长度为：$$\begin{gathered} 10\ast 3+12\ast 3+25\ast 2+15\ast 2+20\ast 2 \\ =22\ast 3+60\ast 2=186 \end{gathered}$$，选B。

5. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于？（ ）
   A. 顶点数
   B. 边数
   C. 顶点数 + 边数
   D. 顶点数 * 2

正确答案：B
有向图中，每条有向边连接两个顶点，为出发点增加1个出度，为到达点增加1个入度。因此所有顶点入度的和就是边的数量，所有顶点出度的和也是边的数量。选B。

6. 从 5 位男生和 4 位女生中选出 4 人组成一个学习小组，要求学习小组中男生和女生都有。有多少种不同的选举方法？（ ）
   A. $126$
   B. $121$
   C. $120$
   D. $100$

正确答案：C
先分类，再分步。
4人中男女都有，可以分为3类：

1. 3男1女，要在5位男生中选出3位男生，方案数为$C_5^3$，而后再4位女生中选出1位女生，方案数为$C_4^1$，分步相乘，选出3男1女的总方案数为$C_5^3{C}_4^1$
2. 2男2女，方案数为$C_5^2{C}_4^2$
3. 1男3女，方案数为$C_5^1{C}_4^3$
   分类相加，总方案数为：$C_5^3{C}_4^1+C_5^2{C}_4^2+C_5^1{C}_4^3$
   $=C_5^2{C}_4^1+C_5^2{C}_4^2+C_5^1{C}_4^1=10\ast 4+10\ast 6+5\ast 4=120$，选C。

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

正确答案：C
由于表达式 (a && b) || (!c && a) 的两边的子表达式中都有a，可以考虑对a的值进行分类讨论。

• 当a为true时 (a && b) || (!c && a) =(true && b) || (!c && true) = b || !c
• 当a为false时 (a && b) || (!c && a) = (false && b) || (!c && false) = false

分别讨论当a为true或false时各选项表达式的值，看是否与表达式 (a && b) || (!c && a)的值相同。
A. 选项：a && (b || !c)

• 当a为true时，表达式为：true && (b || !c) = b || !c。
• 当a为false时，表达式为：false && (b || !c) = false，与给定表达式的值始终相同。

B. 选项：(a || !c) && (b || !c) && (a || a)，

• 当a为true时，表达式为：(true || !c) && (b || !c) && (true || true) = true && (b || !c) && true = b || !c。
• 当a为false时，表达式为：(false || !c) && (b || !c) && (false || false) = !c && (b || !c) && false = false，与给定表达式的值始终相同。

D. 选项：!(!a || !b) || (a && !c)，

• 当a为true时，表达式为：!(!true || !b) || (true && !c) = !(false || !b) || !c = !!b || !c = b || !c。
• 当a为false时，表达式为：!(!false || !b) || (false && !c) = !(true || !b) || false = !true = false，与给定表达式的值始终相同。

C. 选项：a && (!b || c)，

• 当a为false时，表达式为：false && (!b || c) = false，
• 当a为true时，表达式为：true && (!b || c) = !b || c，而给定表达式 (a && b) || (!c && a) 在a为true时转为的表达式是b || !c，二者的值并不始终相等。（如当b= false, c = true时，!b || c = !false || true = true, b || !c = false || !true = false，二者不相等），因此a && (!b || c)与给定表达式不始终相等，该题选C。

8. 已知 $f[0]=1,f[1]=1$，并且对于所有 $n\ge 2$ 有 $f[n]=(f[n-1]+f[n-2])\%7$。
   那么 $f[2025]$ 的值是多少？（ ）
   A. $2$
   B. $4$
   C. $5$
   D. $6$

正确答案：D
由于$f_i$的值为模7的结果，因此$0\le f_i\le 6$，而$f_i=(f_{i-1}+f_{i-2})\mathrm{mod}7$，所以是两个$0$到$6$的数加和模7，$(f_{i-1},f_{i-2})$两个数可能的取值只有$7\ast 7=49$种，如果进行50次递推，那么可以遇到50个数对$(f_{i-1},f_{i-2})$，根据鸽巢原理，其中至少存在两个数对是相同的。只要这两个数相同，那么接下来产生的序列就会相同，因此$f_i$序列的值一定会循环出现，一定存在循环节。

递推找规律，已知> $f_0=f_1=1$，因此递推过程中如果出现连续两项都为1，那么就找到了循环节。
$f_0=1,f_1=1,f_2=2,f_3=3,f_4=5,f_5=1$
$f_6=6,f_7=0,f_8=6,f_9=6,f_{10}=5$
$f_{11}=4,f_{12}=2,f_{13}=6,f_{14}=1,f_{15}=0$
$f_{16}=1,f_{17}=1,f_{18}=\mathrm{2...}$
从$f_0$到$f_{15}$共16个数，循环节长度为16。
下一个循环节为$f_{16}$到$f_{31}$
…
每个循环节为$f_{16x}$到$f_{16x+15}$
每个循环节中各位值的值对应相等，即$f_i=f_{i\mathrm{mod}16}$
要想求第2025项的值，$f_{2025}=f_{2025\mathrm{mod}16}=f_9=6$
因此本题选D。

9. 下列关于 C++ string 类的说法，正确的是？（ ）
   A. string 对象的长度在创建后不能改变。
   B. 可以使用 + 运算符直接连接一个 string 对象和一个 char 类型的字符。
   C. string 的 length() 和 size() 方法返回的值可能不同。
   D. string 对象必须以 '\0' 结尾，且这个结尾符计入 length()。

正确答案：B
A. string对象的长度在创建后可以改变，比如可以调用成员函数push_back在末尾添加字符，或使用+=在末尾添加字符或字符串，或使用成员函数erase删除子串，这些操作都可以改变string对象的长度。A选项错误。
B. 选项正确。C++ STL已重载了string对象和char字符之间进行+运算的运算符，作用是连接字符和字符串。例：string s = "abc"; char c = 'x';，那么s+c表达式的值为为string("abcx")，c+s表达式的值为string("xabc")。
C. string类对象的成员函数length和size的返回值相同，都为unsigned long long类型整数，表示该字符串的长度，即字符串中的字符个数。
D. string对象底层的字符数组中确实要以’\0’结尾，但’\0’不计入字符串的长度，调用length()求字符串的长度时，其长度不包括’\0’。

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

在 main 函数调用 solve 后，$x$ 和 $y$ 的值分别是？（ ）
A. $5,10$
B. $10,5$
C. $10,10$
D. $5,5$

正确答案：C
solve函数的逻辑为交换变量$a、b$的值
设初始时$a=x,b=y$
执行a = a+b，执行后$a=x+y$
执行b = a-b，执行后$b=a-b=x+y-y=x$
执行a = a - b，执行后$a=a-b=x+y-x=y$
最终$a=y,b=x$，完成了交换两变量的值
$x=5,y=10$，传入函数后，$a、b$两参数的值为$a=5,b=10$，交换二者的值后$a=10,b=5$。
solve函数的$a$参数为传引用，引用外部传入的实参$x$。在函数内变量$a$发生变化，那么实参$x$也会随之发生变化。$b$参数为传值，是传入实参$y$的复制，如果$b$发生变化，$y$不会变化。
因此$a$变为$10$后，$x$的值也变为$10$，而$y$的值不变，还是$10$。选C。

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

正确答案：B
动态规划经典问题：
状态定义：$d{p}_{i,j}$：从$(1,1)$到$(i,j)$的路径数。
状态转移方程：走到$(i,j)$的上一步可以是到达$(i,j-1)$或$(i-1,j)$，走到$(i,j)$的路径数是走到$(i,j-1)$的路径数与走到$(i-1,j)$的路径数的加和。
因此$d{p}_{i,j}=d{p}_{i-1,j}+d{p}_{i,j-1}$
初值：$d{p}_{1,1}=1,d{p}_{1,j}=1,d{p}_{i,1}=1$
填表格递推计算$d{p}_{4,5}$，第1行和第1列的值都为1。其余每个格子的值都为其上方和左侧格子的值加和。

i \ j	1	2	3	4	5
1	1	1	1	1	1
2	1	2	3	4	5
3	1	3	6	10	15
4	1	4	10	20	35

因此$d{p}_{4,5}=35$，选B。

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

正确答案：B
冒泡排序会不断交换相邻元素，每次交换减少1个逆序对，所以冒泡排序交换元素的次数为逆序对的数量。可以枚举所有数对求逆序对，先确定第1个数，而后在其后的数中枚举第2个数，看枚举到的数对是否为前大后小的逆序对。
6为第1个数，构成逆序对$(6,1),(6,5),(6,2),(6,4)$
1为第1个数，没有逆序对。
5为第1个数，构成逆序对$(5,2),(5,4)$
2为第1个数，没有逆序对。
因此共有6个逆序对，进行冒泡排序会交换元素6次。选B

13. 十进制数 $720_{10}$ 和八进制数 $270_8$ 的和用十六进制表示是多少？（ ）
    A. $388_{16}$​
    B. $3D{E}_{16}$​
    C. $288_{16}$​
    D. $990_{16}$​

正确答案：A
由于二进制和八进制、十六进制可以快速转换，因此考虑将十进制转为这三种进制之一。而如果转为二进制，位数较多，有些难算，不如转为8进制。
除基取余，使用短除法将十进制数转为八进制。
$720÷8=\mathrm{90......0}$
$90÷8=\mathrm{11......2}$
$11÷8=\mathrm{1......3}$
$1÷8=\mathrm{0......1}$
从下向上取每一位，得到$720_{10}=1320_8$
两个八进制数相加，可以用竖式计算，逢八进一。$1320_8+270_8=1610_8$
而后要转为十六进制。可以先将八进制转为二进制，每位八进制数转为3位二进制数。而后将二进制数转为十六进制数，每4位二进制数转为一位十六进制数。
$1610_8=1,110,001,000_2=11,1000,1000_2=388_{16}$
因此本题选A。

14. 一棵包含 $1000$ 个结点的完全二叉树，其叶子结点的数量是多少？（ ）
    A. $499$
    B. $512$
    C. $500$
    D. $501$

正确答案：C
$n$个结点的完全二叉树，使用顺序存储结构存入数组，结点地址为数组下标。地址为$i$的结点左孩子地址为$2i$，右孩子地址为$2i+1$，双亲地址为$\lfloor \frac{i}{2}\rfloor$。$n$个结点的完全二叉树最后一个结点的地址为$n$，其双亲结点地址为$\lfloor \frac{n}{2}\rfloor$，该结点是最后一个分支结点（如果该结点不是最后一个分支结点，那么其后还有结点存在孩子结点，该孩子结点的地址将大于$n$，而$n$是最后一个结点，不会有结点的地址大于$n$）。
因此地址在$[1,\lfloor \frac{n}{2}\rfloor ]$范围内的结点都是分支结点，共有$\lfloor \frac{n}{2}\rfloor$个。地址在$[\lfloor \frac{n}{2}\rfloor +1,n]$中的结点都是叶子结点，共有$n-\lfloor \frac{n}{2}\rfloor =\lceil \frac{n}{2}\rceil$个。
因此$n$个结点的完全二叉树的叶子结点的数量为$\lceil \frac{n}{2}\rceil$。
该题$n=1000$，叶子结点的数量为$\lceil \frac{1000}{2}\rceil =500$，选C。

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

正确答案：A
根据题目要求在纸上模拟栈和队列。栈为后进先出，队列为先进先出。

当前元素	操作	执行操作后栈内元素（左侧栈底，右侧栈顶）	队列元素（左侧队头，右侧队尾）
7	入栈	7
5	入栈	7 5
8	出栈	7	5
3	入栈	7 3	5
1	入栈	7 3 1	5
4	出栈	7 3	5 1
2	出栈	7	5 1 3

最后队列中的元素为5 1 3，选A。

二、阅读程序

阅读程序(1)
阅读程序(2)
阅读程序(3)

三、完善程序

完善程序(1)
完善程序(2)