CSP - J & S 解析

注：本文为赛后解析汇总，题目与答案主要参考公开的赛题 / 解析。

目录 (S 组还没写完)

  • CSP - J（初赛 / 普及组）
    • 单项选择题（1–15）
    • 阅读程序（若干）
    • 编程题（简要思路）

CSP - J（普及组） — 逐题解析

一、单项选择题（15 题）

下面按题号给出题目要点、正确选项与详细推导（尽量把常见误解、易错点都写清楚）。

1. 32 位无符号整数能表示的最大值最接近哪个选项？

  • 答案：A
  • 理由：32 位无符号整数范围是
1
0 ~ 2^{32} - 1 = 4294967295

约等于 $$ 4.294967295\times10^9 $$ ，最接近选项 A（约 $$ 4.29\times10^9 $$ ）。

2. C++ 中 int x = 255; cout << (x & (x-1)); 的输出？

  • 答案：B（254）
  • 理由：255 的二进制是 11111111（低 8 位），x-1 为 11111110，按位与得 11111110 即 254。常见技巧：x & (x-1) 清除最低位的 1 位。

3. 递归 calc(n)，求 calc(5)。

1
2
3
4
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);
}

  • 答案：B（6）

  • 计算过程：

    • calc(5) = calc(4) + calc(3)
    • calc(4) = calc(2) + 1 = (calc(1)+1)+1 = 1+1+1 = 3
    • calc(3) = calc(2) + calc(1) = 2 + 1 = 3
    • 所以 calc (5) = 3 + 3 = 6。

4. 用权值 10、12、15、20、25 构造哈夫曼树，WPL（带权路径长度）是多少？

  • 答案：B（186）
  • 理由：按哈夫曼合并最小权值：合并 10 + 12 = 22；15 + 20 = 35；22 + 25 = 47；35 + 47 = 82。计算各叶子深度（示例最优合并得到深度）：10、12 在深度 3；15、20、25 在深度 2。带权和为 10×3 + 12×3 + 15×2 + 20×2 + 25×2 = 186。

提示：构造哈夫曼树时每次取最小两项合并是贪心策略的核心，留意权值相等时合并顺序不会影响最终 WPL。

5. 有向图中所有顶点入度之和等于什么？

  • 答案：B（边数）
  • 理由：每条有向边贡献一个出度和一个入度，统计所有顶点的入入度之和等于边数。同理出度之和也等于边数。

6. 从 5 男生 & 4 女生中选 4 人，要求男女都存在的组合数？

  • 答案：C（120）
  • 理由：总选法 C (9,4)=126，去掉全男 C (5,4)=5 和全女 C (4,4)=1，得到 126-5-1 = 120。

7. 逻辑表达式

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

与下列哪个不恒等？

  • 答案：C（a && (!b || c)）
  • 理由：原式可提取 a 得到 a && (b || !c)。逐项化简可验证 A、B、D 等价，而 C 与原式在某些 a,b,c 取值下不等（例如 a = 1,b = 0,c = 1 时：原式为 0，但 C 为 1）。

8. 序列 f [0]=1,f [1]=1, f [n]=(f [n-1]+f [n-2])%7，求 f [2025]

  • 答案：D（6）
  • 理由：模 7 的斐波那契序列周期性（Pisano 周期）长度为 16（经题目解析或直接计算可得）。2025 mod 16 = 9，于是 f [2025] = f [9]。手算出前 9 项得到 f [9]=6。

9. 关于 C++ std::string 的正确说法？

  • 选项：A. 长度不可变 B. 可以 string + char C. length () 与 size () 可能不同 D. 必须以 \0 结尾且计入 length
  • 答案：B
  • 理由：std::string 支持和重载 operator+，可以和 char 连接；A、C、D 都是错误认识（string 长度可变，length ()==size ()，内部可能有 \0 但不计入 length）。

10. 调用函数 solve(int &a, int b) 后 main 中 x,y 的值？

1
2
3
4
5
6
7
8
9
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);
}
  • 答案：C（10, 10）
  • 分析：a 是对 x 的引用，b 是值传递。函数体实现了交换 a 与 b 的值但仅影响局部 b，最终 x 变为 10，y 保持 10。

11. 机器人从 (1,1) 走到 (4,5)，每步右或下，共几条路径？

  • 答案：B（35）
  • 理由：需向下 3 步、向右 4 步，总共 7 步，路径数为 C (7,3)=35。

12. 用冒泡排序对数组 {6,1,5,2,4} 升序，总交换次数？

  • 答案：B（6）
  • 演算：逐轮模拟冒泡可统计交换次数：第一轮 4 次，第二轮 2 次，共 6 次。

13. 720₁₀ + 270₈ 的十六进制表示？

  • 答案：A（388₁₆）
  • 步骤：270₈ = 184₁₀；720 + 184 = 904；904 十六进制为 388。

14. 包含 1000 个结点的完全二叉树叶子结点数？

  • 答案：C（500）
  • 理由：完全二叉树叶子结点数为 ceil(n/2)，当 n = 1000，叶子约 500。

15. 处理序列规则（奇数入栈、偶数出栈到队列）的最后队列内容？A:5,1,3

  • 答案：A（5,1,3）
  • 逐步模拟：按题给顺序模拟入栈 / 出栈过程得到结果 [5,1,3]。

二、阅读程序（节选并解析重要题目）

说明：此处以卷面给出的程序为基础，逐题给出结论与理由（原题为判断题与选择题混合）。我把关键代码放入代码块里以便阅读。

(1) 三重循环计数两两互质三元组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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);
}

答题要点：

  • 输入为 2 时，最内层循环 k 的起始为 j+1 会超出范围，所以第 16 行判断不会执行 → 正确。
  • 若删去 gcd(i,k)==1 条件，会把一些 i,k 非互质但其它两对互质的三元组计入 → 错误。
  • 当 n ≥ 3 时，至少存在三元组 (1,2,3) 满足两两互质，因此输出为正整数 → 正确。
  • 将 gcd(b,a%b) 改为 gcd(a,a%b) 会破坏欧几里得算法（可能返回错误或死循环），最可能的影响是输出 小于 原答案（原解析给出 B）。
  • 当 n = 8 实测满足条件的三元组数量为 25（可手算或暴力脚本验证）。
  • gcd(36,42) 返回 6（经典欧几里得过程）。

(2) 去重后基于差值分组的贪心 / 滑动窗口风格算法

1
2
3
4
5
6
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;
}

要点：

  • 本题考察排序 + 去重 + 双指针 / 滑动窗口处理。
  • 给出的断言与选项解析（例如输入 3 1 3 2 1 输出为 2）可按解析重现。
  • 若删除 std::sort 会导致算法前提被破坏，结果可能变大、变小或不确定 → 综上选项 D。

(3) LCS / 动态规划模板（伪代码中存在细节）

1
2
3
4
5
6
for(int i=1;i<=n;++i)
  for(int j=1;j<=n;++j){
    f[i][j] = max(f[i][j], max(f[i-1][j], f[i][j-1]));
    if(a[i]==b[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
  }
printf("%d\n", f[n][n]);

要点：

  • 参考标准 LCS（最长公共子序列）DP 状态转移，注意边界初始化与 max 的写法。
  • 判断题与选项一般围绕数组越界、初始化、复杂度等展开。

注：阅读程序题较多，以上给出典型题的逐题思路与关键易错点。在最终文档下方我也列出了完整的逐题答案（来源整理）。