2025 CCF 非专业级别软件能力认证第一轮（CSP-J1）答案及解析

 
一、单项选择题
答案：A
解析： 32位无符号整数的最大值是 2^{32}-1=4,294,967,295，约等于 4.29\times10^9，
因此最接近 4\times10^9。
答案：B
解析：x=255（二进制为 11111111），x-1=254（二进制为 11111110）。按位与操作 x&(x-1)
结果为 11111110，即十进制 254。
答案：B
解析： 计算 calc(5)：
calc(5) = calc(4) + calc(3)
calc(4) = calc(2) + 1，calc(2) = calc(1) + 1 = 1 + 1 = 2，所以 calc(4) = 2 + 1 = 3
calc(3) = calc(2) + calc(1) = 2 + 1 = 3
因此 calc(5) =3+3=6
答案：B
解析： 构造哈夫曼树：
合并权值 10 和 12，得到 22
合并权值 15 和 20，得到 35
合并权值 22 和 25，得到 47
合并权值 35 和 47，得到 82
带权路径长度 =10\times3+12\times3+15\times 2+20 \times 2+ 25 \times 2 = 30 + 36 +
30 + 40+50=186
答案：B
解析： 在有向图中，每条边贡献一个入度和一个出度，因此所有顶点的入度之和等于出度
之和，且都等于边数。
答案：C
解析： 总选法为 C(9,4)=126。减去全男生选法 C(5,4)=5 和全女生选法 C(4,4)=1，所以
126- 5- 1=120.
答案：C
解析： 原表达式化简为 a\land(b\lor\lnotc)。选项 C 为 a\land(\lnotb\lorc)，当 a 为
真、b 为假、c 为真时，原表达式为假，选项 C 为真，因此不始终相等。
答案：D
解析： 斐波那契数列模 7 的序列周期为 16。2025\mod16=9，对应 f[9]=6.
答案：B
解析： 在 C++ 中，string 类支持使用 + 运算符连接 string 对象和 char 字符。其他选项
错误：A 中 string 长度可变；C 中 length() 和 size() 相同；D 中 string 不以 \0 结尾，且
\0 不计入长度。
答案：C
解析：函数 solve 试图交换参数，但 b 是传值，不影响外部 y。执行后，x 变为 10，y 保
持不变为 10。
答案：B
解析：从 (1,1) 到 (4,5) 需要向下走 3 步，向右走 4 步，路径数为 C(7,3)=35 或 C(7,4)=
35.
答案：B
解析： 冒泡排序过程：
初始数组:{6,1,5,2,4}
第一趟交换 4 次：{1,5,2,4,6}
第二趟交换 2 次：{1,2,4,5,6}
总交换次数为 6 次。
答案：A
解析：八进制数 270_8=2\times64+7\times8+0=184_{10}。总和 720+184=904_{10}。
904 转换为十六进制：904\div16=56 余 8，56\div16=3 余 8，3\div16=0 余 3，所以
为 388_{16}.
答案：500
解析：完全二叉树有 n 个节点时，叶子节点数为 \lceiln/2\rceil。对于 n=1000，叶子节点
数为 500。
答案：A
解析： 模拟过程：
处理 7（奇）:pushS → S=[7]
处理 5（奇）:pushS → S=[7,5]
处理 8（偶）:popS → P=[5],S=[7]
处理 3（奇）:pushS → S=[7,3]
处理 1（奇）:pushS → S=[7,3,1]
处理 4（偶）:popS → P=[5,1],S=[7,3]
处理 2（偶）:popS → P=[5,1,3],S=[7]
因此 P 为 [5,1,3]
二、阅读程序
程序1
答案：V
解析： 输入为 2 时，内层循环 k 不执行，因此不会执行第 16 行的判断。
答案：X
解析： 删去 gcd(i,k)==1 后，程序会计数非两两互质的三元组，导致结果变大。
答案：V
解析： 当 n\geq3 时，至少存在三元组 (1,2,3) 满足条件，输出正整数。
答案：C
解析： 改为 gcd(a,a%b) 后，递归时第一个参数不变，可能死循环。
答案：B
解析： 输入为 8 时，输出为 42。
答案：A
解析： gcd(36,42) 计算过程：42mod36=6,gcd(36,6)=6。
程序2
答案：X
解析： 输入为 "31321" 时，输出为 3，不是 2。
答案：V
解析： ans[i] 表示前 i 个元素的最少组数，满足 1\leq\text{ans}[i]\leqn.
答案：V
解析： 删去去重代码后，数组可能包含重复元素，影响结果。
答案：B
解析： 执行第 18 行时，已退出循环，满足 a[i]-a[j]<=k，因此 B 不一定成立。
答案：A
解析： 输入为 n=100,k=2,a=\{1,2,\ldots,100\} 时，输出为 34。
答案：D
解析： 删去排序后，数组无序，可能导致输出答案变大、变小或死循环。
程序3
答案：V
解析： 输入为 "412341322" 时，LCS 长度为 2。
答案：V
解析： f[i][j] 是子问题 LCS 长度，不会超过全局 LCS 长度 f[n][n].
答案：X
解析： 删去后，f[i][j] 只在匹配时更新，否则为 0，影响结果。
答案：A
解析： LCS 长度满足 0\leq\text{LCS}\leqn，因此小于等于 n.
答案：A
解析： 排序后，LCS 长度可能变大或不变。
答案：B
解析： 当 a 为连续递增序列时，LCS 等价于 b 的最长递增子序列（LIS）。
三、完善程序
(1) 字符串解码
答案： 通常为 isalpha(ch)（选项未提供，根据逻辑推断）
解析： 判断当前字符是否为字母。
答案：B
解析： 计算数字字符串的值：count=count*10+(z[i]-'0').
答案：B
解析： 循环输出 ch 共 count 次：j<count.
答案：B
解析： 没有数字时，直接输出字符 ch.
答案：C
解析： 处理完字符后，索引 i 增加：i++.
(2) 精明与糊涂
答案：B
解析： 初始化 count 为 1。
答案：C
解析： 如果 count 为 0，需要设置新候选。
答案：D
解析： 判断候选和 i 是否互相指认为糊涂人：query(candidate, i)==false || query(i,
candidate)==false.
答案：A
解析： 抵消时，count 减少：count--.
答案：C
解析： 输出最终候选 candidate