2019 CSP-J 普及组初赛真题及解析 · 完整43题

CCF 非专业级软件能力认证入门级（2019 年第一轮）完整真题。2019 年是 NOIP 转型为 CSP 的第一年，本题涵盖单项选择题 15 道、阅读程序题 3 道（18 小题）、完善程序题 2 道（10 小题），全部附答案与详解。

获取 2019CSP-J普及组初赛完整真题及详细解析.pdf

请关注状元编程公众号，回复 2019CSP-J

📋 文章速览

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

第 1 题（计算机网络）

中国的国家顶级域名是（ ）。

A. .cn B. .ch C. .chn D. .china

答案：A

解析：国家顶级域名（ccTLD）由 ISO 3166-1 标准指定，中国的国家顶级域名是 .cn，由 CNNIC 管理。.ch 是瑞士的域名。

第 2 题（位运算）

二进制数 11 1011 1001 0111 和 01 0110 1110 1011 进行按位与运算的结果是（ ）。

A. 01 0010 1000 1011 B. 01 0010 1001 0011 C. 01 0010 1000 0001 D. 01 0010 1000 0011

答案：D

解析：按位与运算规则：1&1=1，其余为 0。逐位对齐计算：

  11 1011 1001 0111& 01 0110 1110 1011= 01 0010 1000 0011

第 3 题（数据存储）

一个 32 位整型变量占用（ ）个字节。

A. 32 B. 128 C. 4 D. 8

答案：C

解析：1 字节（Byte）= 8 位（bit），32 / 8 = 4 字节。

第 4 题（程序阅读）

若有如下程序段，其中 s、a、b、c 均已定义为整型变量，且 a、c 均已赋值（c 大于 0）：

s = a;for (b = 1; b <= c; b++) s = s - 1;

则与上述程序段功能等价的赋值语句是（ ）。

A. s = a - c; B. s = a - b; C. s = s - c; D. s = b - c;

答案：A

解析：s 初值为 a，循环 c 次，每次减 1，共减少 c。所以 s = a - c。

第 5 题（二分查找）

设有 100 个已排好序的数据元素，采用折半查找时，最大比较次数为（ ）。

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

答案：A

解析：折半查找最大比较次数为 ⌊log₂n⌋ + 1。log₂64 = 6 < log₂100 < 7 = log₂128，所以 ⌊log₂100⌋ = 6，最大比较次数 = 6 + 1 = 7。

第 6 题（数据结构）

链表不具有的特点是（ ）。

A. 插入删除不需要移动元素 B. 不必事先估计存储空间 C. 所需空间与线性表长度成正比 D. 可随机访问任一元素

答案：D

解析：链表不支持随机访问（O(n)），只能顺序遍历。数组才支持 O(1) 随机访问。其余三个都是链表的优点。

第 7 题（组合数学）

把 8 个同样的球放在 5 个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的分法？（ ）

提示：8 个球都放在一个袋子里，无论哪个袋子都只算同一种分法。

A. 22 B. 24 C. 18 D. 20

答案：C

解析：将 8 分成不超过 5 个数之和（升序排列避免重复）：

共 1 + 4 + 5 + 5 + 3 = 18 种。

第 8 题（二叉树存储）

一棵二叉树采用顺序存储结构（根结点下标为 1，左孩子 2i，右孩子 2i+1），该数组的最大下标至少为（ ）。

A. 6 B. 10 C. 15 D. 12

答案：C

解析：根据题目图示，这是一棵右斜路径的树：根(1) → 右孩子(3) → 右孩子(7) → 右孩子(15)。最大下标为 15。

第 9 题（素数）

100 以内最大的素数是（ ）。

A. 89 B. 97 C. 91 D. 93

答案：B

解析：从大到小检查：97 不能被 2,3,5,7 整除（√97 < 10），是素数。93 = 3×31，91 = 7×13，89 是素数但不是最大的。

第 10 题（最大公约数）

319 和 377 的最大公约数是（ ）。

A. 27 B. 33 C. 29 D. 31

答案：C

解析：辗转相除法：

377 ÷ 319 = 1 ... 58319 ÷ 58  = 5 ... 2958  ÷ 29  = 2 ... 0

GCD = 29。

第 11 题（贪心算法）

小胖想减肥，健身教练制定了两个训练方案：

• 方案一：每次连续跑 3 公里消耗 300 千卡（半小时）
• 方案二：每次连续跑 5 公里消耗 600 千卡（1 小时）

小胖周一到周四能抽出半小时跑步，周五到周日能抽出一小时跑步。每周最多跑 21 公里。每周最多消耗多少千卡？

A. 3000 B. 2500 C. 2400 D. 2520

答案：C

解析：贪心策略——优先选择单位公里消耗更高的方案。方案二每公里 120 千卡 > 方案一每公里 100 千卡。

• 周五~周日跑 3 次方案二：15 公里，消耗 1800 千卡
• 剩余可跑 6 公里 → 周一~周四选 2 天跑方案一：6 公里，消耗 600 千卡
• 总计：1800 + 600 = 2400 千卡

第 12 题（鸽巢原理）

一副 52 张牌（4 种花色各 13 张），随机抽取 13 张，则至少（ ）张牌的花色一致。

A. 4 B. 2 C. 3 D. 5

答案：A

解析：鸽巢原理：4 个巢（花色），13 只鸽子（牌）。13 = 3×4 + 1，至少有一个巢有 ⌊13/4⌋ + 1 = 4 张牌。

第 13 题（组合计数）

一些数字可以颠倒过来看：0、1、8 颠倒后不变，6 和 9 互换。5 位数字车牌中，倒过来恰好还是原来的车牌有多少个？

A. 60 B. 125 C. 75 D. 100

答案：C

解析：5 位车牌 abcde，倒转后为 e'd'c'b'a'，要求与原车牌相同。

• 第 1 位 a 和第 5 位 e 必须互为翻转对：{0,1,8} 自翻或 {6,9} 互翻 → 5 种（选定 a 后 e 确定）
• 第 2 位 b 和第 4 位 d 同理 → 5 种
• 第 3 位 c 必须自翻 → 3 种（0,1,8）

总计：5 × 5 × 3 = 75。

第 14 题（二叉树遍历）

已知后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，求前序遍历序列。

A. ABCDEFGHIJ B. ABDEGHJCFI C. ABDEGJHCFI D. ABDEGHJFIC

答案：B

解析：后序最后一个是根 A。中序中 A 的位置将树分为左子树 DBGEHJ 和右子树 CIF。

递归构建：

• A 的左子树：后序 DGJHEB，中序 DBGEHJ → 根 B 
• B 的左子树：D
• B 的右子树：后序 GJHE，中序 GEHJ → 根 E 
• E 的左子树：G
• E 的右子树：后序 JH，中序 HJ → 根 H 
• H 的右子树：J
• A 的右子树：后序 IFC，中序 CIF → 根 C 
• C 的右子树：后序 IF，中序 IF → 根 F 
• F 的左子树：I

前序遍历：ABDEGHJCFI。

第 15 题（计算机常识）

以下哪个奖项是计算机科学领域的最高奖？

A. 图灵奖 B. 鲁班奖 C. 诺贝尔奖 D. 普利策奖

答案：A

解析：图灵奖（Turing Award）由 ACM 设立，是计算机科学领域的最高奖项，被称为"计算机界的诺贝尔奖"。鲁班奖是建筑工程奖，普利策奖是新闻奖。

二、阅读程序题（共 18 小题）

阅读程序 1（约数位置大写转换）

#include<cstdio>#include<cstring>usingnamespace std;char st[100];intmain(){scanf("%s", st);int n = strlen(st);for (int i = 1; i <= n; ++i) {if (n % i == 0) {char c = st[i - 1];if (c >= 'a')                st[i - 1] = c - 'a' + 'A';        }    }printf("%s", st);return0;}

程序功能：遍历 i=1 到 n，如果 i 是 n 的约数，则将第 i 个字符（从 1 开始计数）从小写转为大写。

第 16 题（判断）

输入的字符串只能由小写字母或大写字母组成。（ ）

A. 正确 B. 错误

答案：B

解析：程序没有限制输入字符类型，可以包含数字、符号等。非小写字母的字符不受 c >= 'a' 条件影响。

第 17 题（判断）

若将第 8 行的 i = 1 改为 i = 0，程序运行时会发生错误。（ ）

A. 正确 B. 错误

答案：A

解析：i=0 时执行 n % i 即 n % 0，除零错误，程序崩溃。

第 18 题（判断）

若将第 8 行的 i <= n 改为 i * i <= n，程序运行结果不会改变。（ ）

A. 正确 B. 错误

答案：B

解析：改为 i*i <= n 后只检查 ≤ √n 的约数。例如 n=10 时，约数 5 和 10 都大于 √10 ≈ 3.16，不会被检查到，第 5 和第 10 个字符不会转换。

第 19 题（判断）

若输入的字符串全部由大写字母组成，那么输出的字符串就跟输入的字符串一样。（ ）

A. 正确 B. 错误

答案：A

解析：大写字母不满足 c >= 'a'，转换条件不会触发，输出与输入相同。

第 20 题（单选）

若输入的字符串长度为 18，那么输入的字符串跟输出的字符串相比，至多有（ ）个字符不同。

A. 18 B. 6 C. 10 D. 1

答案：B

解析：18 的约数有 1, 2, 3, 6, 9, 18，共 6 个。最多 6 个位置可能被转换。

第 21 题（单选）

若输入的字符串长度为（ ），那么输入的字符串跟输出的字符串相比，至多有 36 个字符不同。

A. 36 B. 100000 C. 1 D. 128

答案：B

解析：需要找约数个数为 36 的数。100000 = 2⁵ × 5⁵，约数个数 = (5+1)×(5+1) = 36。

阅读程序 2（双向匹配）

#include<cstdio>usingnamespace std;int n, m;int a[100], b[100];intmain(){scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i)        a[i] = b[i] = 0;for (int i = 1; i <= m; ++i) {int x, y;scanf("%d%d", &x, &y);if (a[x] < y && b[y] < x) {if (a[x] > 0)                b[a[x]] = 0;if (b[y] > 0)                a[b[y]] = 0;            a[x] = y;            b[y] = x;        }    }int ans = 0;for (int i = 1; i <= n; ++i) {if (a[i] == 0)            ++ans;if (b[i] == 0)            ++ans;    }printf("%d\n", ans);return0;}

程序功能：处理 m 对 (x, y) 匹配关系。a[x] 记录 x 当前匹配的 y 值，b[y] 记录 y 当前匹配的 x 值。只有当新匹配优于现有匹配时才更新（贪心选择最优），并清除旧匹配。最后统计未匹配的位置数。

第 22 题（判断）

当 m > 0 时，输出值一定小于 2n。（ ）

A. 正确 B. 错误

答案：A

解析：m > 0 时至少有一对成功匹配，a[x] 和 b[y] 至少各有一个不为 0，所以 ans ≤ 2n - 2 < 2n。

第 23 题（判断）

执行完第 27 行的 ++ans 时，ans 一定是偶数。（ ）

A. 正确 B. 错误

答案：B

解析：n=2, m=1, x=1, y=2 时，a[1]=2, b[2]=1。遍历 i=1 时 a[1]≠0 不计数，b[1]=0 则 ans=1（奇数）。

第 24 题（判断）

a[i] 和 b[i] 不可能同时大于 0。（ ）

A. 正确 B. 错误

答案：B

解析：当 x=i 且某个 y 使 a[i]=y，同时 b[i] 也被另一对匹配设置时，两者可以同时大于 0。例如 x=4, y=4 时 a[4]=4 且 b[4]=4。

第 25 题（判断）

若程序执行到第 13 行时，x 总是小于 y，那么第 15 行不会被执行。（ ）

A. 正确 B. 错误

答案：B

解析：第 13 行 if (a[x] < y && b[y] < x) 中的比较是 x 与 x 比较、y 与 y 比较，与 x 和 y 的大小关系无关。当 x < y 但 a[x] 已有旧匹配时，第 15 行仍会执行。

第 26 题（单选）

若 m 个 x 两两不同，且 m 个 y 两两不同，则输出的值为（ ）。

A. 2n - 2m B. 2n + 2 C. 2n - 2 D. 2n

答案：A

解析：x 和 y 都两两不同时，每对匹配都成功且不会被覆盖。共 m 对匹配，a 数组有 m 个非零，b 数组有 m 个非零。ans = 2n - 2m。

第 27 题（单选）

若 m 个 x 两两不同，且 m 个 y 都相等，则输出的值为（ ）。

A. 2n - 2 B. 2n C. 2m D. 2n - 2m

答案：A

解析：m 个不同的 x 都匹配同一个 y，但 b[y] 只记录最大的 x。最终只有 1 对匹配成功（a[x_max]=y, b[y]=x_max），ans = 2n - 2。

阅读程序 3（分治最小值树）

#include<iostream>usingnamespace std;constint maxn = 10000;int n;int a[maxn], b[maxn];intf(int l, int r, int depth){if (l > r)return0;int min = maxn, mink;for (int i = l; i <= r; ++i) {if (min > a[i]) {            min = a[i];            mink = i;        }    }int lres = f(l, mink - 1, depth + 1);int rres = f(mink + 1, r, depth + 1);return lres + rres + depth * b[mink];}intmain(){    cin >> n;for (int i = 0; i < n; ++i)        cin >> a[i];for (int i = 0; i < n; ++i)        cin >> b[i];    cout << f(0, n - 1, 1) << endl;return0;}

程序功能：在区间 [l, r] 中找到 a 数组最小值位置 mink，递归处理左右子区间。最终结果 = Σ(depth × b[mink])，构建的是一棵以最小值为根的笛卡尔树，depth 为节点深度。

第 28 题（判断）

如果 a 数组有重复的数字，则程序运行会发生错误。（ ）

A. 正确 B. 错误

答案：B

解析：有重复数字时，min > a[i] 使用严格大于，取第一个最小值的位置，不会出错。

第 29 题（判断）

如果 b 数组全为 0，则输出为 0。（ ）

A. 正确 B. 错误

答案：A

解析：返回值 = lres + rres + depth × b[mink]。b 全为 0 时，每层递归贡献 0，最终输出 0。

第 30 题（单选）

当 n=100 时，最坏情况下，与第 12 行的比较运算执行的次数最接近的是（ ）。

A. 5000 B. 600 C. 6 D. 100

答案：A

解析：最坏情况是链形树（a 数组有序），深度 100 层。第 12 行比较次数 = 100 + 99 + 98 + ... + 1 = 5050 ≈ 5000。

第 31 题（单选）

当 n=100 时，最好情况下，与第 12 行的比较运算执行的次数最接近的是（ ）。

A. 100 B. 6 C. 5000 D. 600

答案：D

解析：最好情况是平衡树（a 数组中间最小），深度约 log₂100 ≈ 6.6 层。每层比较约 100 次，总比较次数 ≈ 6 × 100 = 600。

第 32 题（单选）

当 n=10 时，若 b[i] = i+1，那么输出最大为（ ）。

A. 386 B. 383 C. 384 D. 385

答案：D

解析：最大值出现在链形树（a 有序），depth 从 1 到 10：

1×1 + 2×2 + 3×3 + ... + 10×10 = 385。

第 33 题（单选）

当 n=100 时，若 b[i] = 1，那么输出最小为（ ）。

A. 582 B. 580 C. 579 D. 581

答案：B

解析：b 全为 1 时，输出 = Σ(depth × 1) = 所有节点深度之和。最小深度和出现在完全平衡二叉树：

总计 = 1 + 2 + 12 + 32 + 80 + 192 + 259 = 580。

三、完善程序题（共 10 小题）

完善程序 1（矩阵变幻 · 分形递归）

有一个奇幻的矩阵，在不停地变幻。数字 0 变成矩阵 [0 0; 0 1]，数字 1 变成矩阵 [1 1; 1 0]。最初矩阵只有一个元素 0，变幻 n 次后的矩阵是什么？

例如：变幻 1 次后为 0011（2×2），变幻 2 次后为 0000010100110110（4×4）。

#include<cstdio>usingnamespace std;int n;constint max_size = 1 << 10;int res[max_size][max_size];voidrecursive(int x, int y, int n, int t){if (n == 0) {        res[x][y] = __1__;return;    }int step = 1 << (n - 1);recursive(__2__, n - 1, t);recursive(x, y + step, n - 1, t);recursive(x + step, y, n - 1, t);recursive(__3__, n - 1, !t);}intmain(){scanf("%d", &n);recursive(0, 0, __4__);int size = __5__;for (int i = 0; i < size; ++i) {for (int j = 0; j < size; ++j)printf("%d", res[i][j]);putchar('\n');    }return0;}

第 34 题

① 处应填（ ）。

A. n % 2 B. 0 C. t D. 1

答案：C

解析：递归到 n=0 时填充单个像素。t 是当前变换状态（0 或 1），决定了填充的值。0 变幻为 [0 0; 0 1]，1 变幻为 [1 1; 1 0]，所以基础值就是 t。

第 35 题

② 处应填（ ）。

A. x - step, y - step B. x, y - step C. x - step, y D. x, y

答案：D

解析：四个子矩阵对应左上、右上、左下、右下。左上角就是原始坐标 (x, y)。

第 36 题

③ 处应填（ ）。

A. x - step, y - step B. x + step, y + step C. x - step, y D. x, y - step

答案：B

解析：第四个 recursive 调用对应右下角子矩阵，坐标为 (x + step, y + step)。注意它传入 !t（翻转状态），因为变幻规则中右下角取反。

第 37 题

④ 处应填（ ）。

A. n - 1, n % 2 B. n, 0 C. n, n % 2 D. n - 1, 0

答案：B

解析：从 n 次变幻开始递归，初始状态 t=0（矩阵最初为 0）。

第 38 题

⑤ 处应填（ ）。

A. 1 << (n + 1) B. 1 << n C. n + 1 D. 1 << (n - 1)

答案：B

解析：变幻 n 次后矩阵边长为 2ⁿ，即 1 << n。验证：n=1 时边长 2，n=2 时边长 4。

完善程序 2（双关键字计数排序）

使用双关键字计数排序，将 n 对整数按 (a, b) 从小到大排序。先对第二关键字 b 排序，再对第一关键字 a 排序。

#include<cstdio>#include<cstring>usingnamespace std;constint maxn = 10000000;constint maxs = 10000;int n;unsigned a[maxn], b[maxn], res[maxn], ord[maxn];unsigned cnt[maxs + 1];intmain(){scanf("%d", &n);for (int i = 0; i < n; ++i)scanf("%d%d", &a[i], &b[i]);memset(cnt, 0, sizeof(cnt));for (int i = 0; i < n; ++i)        __1__;  // 利用 cnt 数组统计数量for (int i = 0; i < maxs; ++i)        cnt[i + 1] += cnt[i];for (int i = 0; i < n; ++i)        __2__;  // 记录初步排序结果memset(cnt, 0, sizeof(cnt));for (int i = 0; i < n; ++i)        __3__;  // 利用 cnt 数组统计数量for (int i = 0; i < maxs; ++i)        cnt[i + 1] += cnt[i];for (int i = n - 1; i >= 0; --i)        __4__;  // 记录最终排序结果for (int i = 0; i < n; ++i)printf("%d %d\n", __5__);return0;}

第 39 题

① 处应填（ ）。

A. ++cnt[i] B. ++cnt[b[i]] C. ++cnt[a[i] * maxs + b[i]] D. ++cnt[a[i]]

答案：B

解析：第一轮先对第二关键字 b 排序，统计每个 b[i] 值出现的次数。

第 40 题

② 处应填（ ）。

A. ord[--cnt[a[i]]] = i B. ord[--cnt[b[i]]] = a[i] C. ord[--cnt[a[i]]] = b[i] D. ord[--cnt[b[i]]] = i

答案：D

解析：前缀和后 cnt[b[i]] 表示 b[i] 的排名上限。倒序放置保证稳定性，ord[--cnt[b[i]]] = i 记录第 b 排名对应的原始下标。

第 41 题

③ 处应填（ ）。

A. ++cnt[b[i]] B. ++cnt[a[i] * maxs + b[i]] C. ++cnt[a[i]] D. ++cnt[i]

答案：C

解析：第二轮对第一关键字 a 排序，统计每个 a[i] 值出现的次数。

第 42 题

④ 处应填（ ）。

A. res[--cnt[a[ord[i]]]] = ord[i] B. res[--cnt[b[ord[i]]]] = ord[i] C. res[--cnt[b[i]]] = ord[i] D. res[--cnt[a[i]]] = ord[i]

答案：A

解析：倒序遍历 ord 数组（按 b 排序的结果），用 a 的值作为关键字放入最终位置。a[ord[i]] 取出按 b 排序后第 i 个元素的第一关键字，ord[i] 记录原始下标。

第 43 题

⑤ 处应填（ ）。

A. a[i], b[i] B. a[res[i]], b[res[i]] C. a[ord[res[i]]], b[ord[res[i]]] D. a[res[ord[i]]], b[res[ord[i]]]

答案：B

解析：res[i] 记录第 i 小元素在原始序列中的下标，所以输出 a[res[i]] 和 b[res[i]]。

📊 答案速查表

单项选择题

阅读程序题

完善程序题

🎯 考点分布分析

单项选择题（15 题）

阅读程序题（18 题）

完善程序题（10 题）

🏆 高频考点

1. 约数与数论（贯穿全卷）

约数判定（16-21）、GCD 辗转相除（10）、素数判定（9）——数论基础是 CSP-J 的核心考点。

2. 组合数学（每年必考）

• 整数划分：球放袋子问题（7）
• 鸽巢原理：抽牌花色（12）
• 对称计数：车牌翻转（13）

3. 二叉树（重点中的重点）

• 顺序存储下标计算（8）
• 前序+中序+后序遍历转换（14）
• 笛卡尔树递归构建（28-33）

4. 计数排序（经典算法）

双关键字计数排序是 2019 年的压轴题，体现了 CSP-J 对非比较排序的考察。

📚 备考建议

1. 数论基础要扎实：约数个数公式、辗转相除法、素数判定必须熟练
2. 组合数学多练：整数划分、鸽巢原理、乘法原理是常考题型
3. 二叉树三大遍历：前序+中序建树、后序+中序建树必须掌握
4. 计数排序：理解前缀和 + 倒序放置保证稳定性的原理
5. 分治递归：理解递归状态传递（如 t → !t 翻转）
6. 多刷历年真题：2019 年是 CSP 改革第一年，题型具有里程碑意义

💡 推荐阅读：本公众号已发布 2020-2025 年 CSP-J/S 初赛真题解析系列，欢迎翻阅历史文章系统备考！