2023 第一轮真题解析（一）：单项选择题

2023 年 CCF 非专业级软件能力认证（CSP-J/S 2023）第一轮认证于 2023 年 9 月 16 日举行。

本文为您带来 CSP-J 2023 第一轮真题解析（一）：单项选择题（共 15 题，每题 2 分，共计 30 分） 的原题还原、选项剖析与深度考点解析，涵盖 C++ 基础语法、数据结构、组合数学、进制转换、哈夫曼编码、图论拓扑排序 等核心知识点。

📌 一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

第 1 题

原题：
在 C++ 中，下面哪个关键字用于声明一个变量，其值不能被修改？
A. unsigned
B. const
C. static
D. mutable

正确答案： B

深度解析：
本题考查 C++ 的关键字功能与变量修饰符：

• const（常量修饰符）：用于声明一个只读变量/常量。一旦初始化后，其值就不能再被修改。若尝试修改 const 变量，编译器将抛出编译错误。
• unsigned（无符号修饰符）：表示无符号整数类型（非负数），扩展了正数表示范围，但不限制值是否可修改。
• static（静态修饰符）：限定变量的生存期为整个程序运行期间，以及控制链接属性/作用域，值依然可以被修改。
• mutable（可变修饰符）：专门用于修饰类的成员变量，使得该成员变量即使在 const 成员函数中也可以被修改。

第 2 题

原题：
八进制数 $12345670_8$ 和 $07654321_8$ 的和为（ ）
A. $22222221_8$
B. $21111111_8$
C. $22111111_8$
D. $22222211_8$

正确答案： D

深度解析：
本题考查 八进制加法运算。八进制下的加法规则为 “逢 8 进 1”。

我们进行竖式逐位相加（从右往左）：

  1 2 3 4 5 6 7 0 (8)
+ 0 7 6 5 4 3 2 1 (8)
---------------------

• 第 0 位（最右侧）：$0 + 1 = 1$
• 第 1 位：$7 + 2 = 9 = 8 \times 1 + 1$ （写 $1$，进 $1$）
• 第 2 位：$6 + 3 + 1(\text{进位}) = 10 = 8 \times 1 + 2$ （写 $2$，进 $1$）
• 第 3 位：$5 + 4 + 1(\text{进位}) = 10 = 8 \times 1 + 2$ （写 $2$，进 $1$）
• 第 4 位：$4 + 5 + 1(\text{进位}) = 10 = 8 \times 1 + 2$ （写 $2$，进 $1$）
• 第 5 位：$3 + 6 + 1(\text{进位}) = 10 = 8 \times 1 + 2$ （写 $2$，进 $1$）
• 第 6 位：$2 + 7 + 1(\text{进位}) = 10 = 8 \times 1 + 2$ （写 $2$，进 $1$）
• 第 7 位：$1 + 0 + 1(\text{进位}) = 2$

计算结果为 $22222211_8$，对应 D 选项。

第 3 题

原题：
阅读下述代码，请问修改 data 的 value 成员以存储 3.14，正确的方式是（ ）

union Data{
    int num;
    float value;
    char symbol;
};
union Data data;

A. data.value = 3.14;
B. value.data = 3.14;
C. data -> value = 3.14;
D. value->data = 3.14;

正确答案： A

深度解析：
本题考查 C++ 中 联合体（union）实例成员的访问方式：

1. data 是一个 union Data 类型的变量（普通对象），并非指针。
2. 访问结构体或联合体普通对象的成员，必须使用 点运算符（.），语法结构为：对象名.成员名。因此正确修改方式为 data.value = 3.14;。
3. 只有当变量是指向联合体/结构体的指针（如 union Data* p）时，才使用箭头运算符 p->value。

知识扩展： union（联合体）的所有成员共享同一块内存空间，其总内存大小等于最大成员的大小。赋值 data.value 会覆盖之前存放在 data 中的其他成员数据。

第 4 题

原题：
假设有一个链表的节点定义如下：

struct Node { int data; Node* next; };

现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，使其成员 data 的值为 42，并使新节点成为链表的第一个节点，下面哪个操作是正确的？（ ）
A. Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
B. Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
C. Node* newNode = new Node; newNode->data = 42; head->next = newNode;
D. Node* newNode = new Node; newNode->data = 42; newNode->next = head;

正确答案： A

深度解析：
本题考查单链表的 头插法（前插法） 步骤：

要在链表头部插入一个值为 42 的新节点，标准步骤为：

1. 动态创建新节点：Node* newNode = new Node;
2. 为新节点的数据域赋值：newNode->data = 42;
3. 将新节点的指针域指向原头节点：newNode->next = head;
4. 更新头指针指向新节点：head = newNode;

完整连起来即为 A 选项的代码。

选项错因分析：

• B 错在修改了 head->data = 42，篡改了原头节点的数据且未设置新节点数值。
• C 错在将 head->next 指向新节点，破坏了原本的后续链表结构。
• D 错在漏掉了更新头指针 head = newNode;，新节点未能真正成为新的头节点。

第 5 题

原题：
根节点的高度为 1，一棵拥有 2023 个节点的三叉树高度至少为（ ）
A. 6
B. 7
C. 8
D. 9

正确答案： C

深度解析：
本题考查 多叉树的高度与节点数关系。

为了使高度至少（即尽可能小），该三叉树必须是完全/满三叉树（每一层都尽可能填满）。

对于一棵高度为 $h$ 的满三叉树，各层节点数依次为：

• 第 1 层：$3^0 = 1$
• 第 2 层：$3^1 = 3$
• 第 3 层：$3^2 = 9$
• $\dots$
• 第 $h$ 层：$3^{h-1}$

高度为 $h$ 的满三叉树能容纳的最大节点总数 $N(h)$ 为等比数列求和：

我们逐个代入选项计算最大节点容量：

• 当 $h = 6$ 时：$N(6) = \frac{3^6 - 1}{2} = \frac{729 - 1}{2} = 364$ （小于 2023）
• 当 $h = 7$ 时：$N(7) = \frac{3^7 - 1}{2} = \frac{2187 - 1}{2} = 1093$ （小于 2023）
• 当 $h = 8$ 时：$N(8) = \frac{3^8 - 1}{2} = \frac{6561 - 1}{2} = 3280$ （大于 2023）

因为 $1093 < 2023 \le 3280$，所以要容纳 2023 个节点，三叉树的高度至少为 8。

第 6 题

原题：
小明在某一天中依次有七个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息。则小明一共有（ ）种选择时间段的方案。
A. 31
B. 18
C. 21
D. 33

正确答案： B

深度解析：
本题考查 组合数学与分类讨论 / 插空思想。

设 7 个时间段编号为 $1, 2, 3, 4, 5, 6, 7$。选出的练习时间段之间必须至少间隔 $2$ 个未选的时间段。

我们按选出的练习时间段数量 $k$（$k \ge 1$）进行分类讨论：

1. 当选择 $k = 1$ 个时间段时：
   可以在 7 个时间段中任意选择 1 个，共有 $\binom{7}{1} = 7$ 种方案。

2. 当选择 $k = 2$ 个时间段时：
   两个选择的时间段之间至少隔 2 个时间段。设选出的第 1 个时间段为 $x$，第 2 个时间段为 $y$，必须满足 $y - x \ge 3$。

   • 若 $x = 1$：$y$ 可选 $4, 5, 6, 7$（$4$ 种）
   • 若 $x = 2$：$y$ 可选 $5, 6, 7$（$3$ 种）
   • 若 $x = 3$：$y$ 可选 $6, 7$（$2$ 种）
   • 若 $x = 4$：$y$ 可选 $7$（$1$ 种）
     方案数为：$4 + 3 + 2 + 1 = 10$ 种。
     （亦可用公式：在 $7 - (2-1) \times 2 = 5$ 个位置中选 2 个点，$\binom{5}{2} = 10$ 种）

3. 当选择 $k = 3$ 个时间段时：
   选 3 个时间段至少需要占用的长度为：选 1 个 + 隔 2 个 + 选 1 个 + 隔 2 个 + 选 1 个 = $1 + 2 + 1 + 2 + 1 = 7$ 个时间段。
   刚好占用完所有 7 个时间段，因此只有唯一一种组合方案，即选择 $\{1, 4, 7\}$，方案数为 $1$ 种。

4. 当选择 $k \ge 4$ 个时间段时：
   选择 4 个时间段至少需要 $1 + 2 + 1 + 2 + 1 + 2 + 1 = 10$ 个时间段，超过了总数 7，因此方案数为 $0$。

总方案数 $= 7 + 10 + 1 = 18$ 种。

第 7 题

原题：
以下关于高精度运算的说法错误的是（ ）
A. 高精度计算主要是用来处理大整数或需要保留多位小数的运算
B. 大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商
C. 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关
D. 高精度加法运算的关键在于逐位相加并处理进位

正确答案： C

深度解析：
本题考查 高精度算法的概念与时间复杂度：

• A 选项：正确。当数值超过语言原生数据类型（如 long long 或 double 的精度极限）时，必须使用高精度计算（通常用数组或字符串模拟）。
• B 选项：正确。这是模拟手算竖式除法的标准步骤（高精度除以低精度）。
• C 选项：错误！ 普通高精度乘法（模拟竖式乘法）的时间复杂度为 $O(N \times M)$，其中 $N$ 和 $M$ 分别为两个乘数的位数。因此，运算时间取决于两个整数的位数乘积，而不仅仅是“较长者的位数”。即使采用 FFT / NTT 加速，复杂度也与两个整数的总位数有关。
• D 选项：正确。高精度加法的本质就是模拟低位到高位的逐位相加，同时维护进位变量 carry。

题目要求选择说法错误的选项，故选 C。

第 8 题

原题：
后缀表达式 6 2 3 + - 3 8 2 / + * 2 ^ 3 + 对应的中缀表达式是（ ）
A. ((6-(2+3))*(3+8/2))^2+3
B. 6-2+3*3+8/2^2+3
C. (6-(2+3))*((3+8/2)^2)+3
D. 6-((2+3)*(3+8/2))^2+3

正确答案： A

深度解析：
本题考查 后缀表达式（逆波兰表达式）转换为中缀表达式。

我们使用栈模拟表达式转换过程（从左往右扫描）：

1. 遇到数字 6, 2, 3 入栈 $\rightarrow$ 栈内容：[6, 2, 3]
2. 遇到算符 +：弹出 3 和 2，组合为 (2 + 3) 入栈 $\rightarrow$ 栈内容：[6, (2 + 3)]
3. 遇到算符 -：弹出 (2 + 3) 和 6，组合为 (6 - (2 + 3)) 入栈 $\rightarrow$ 栈内容：[(6 - (2 + 3))]
4. 依次压入数字 3, 8, 2 $\rightarrow$ 栈内容：[(6 - (2 + 3)), 3, 8, 2]
5. 遇到算符 /：弹出 2 和 8，组合为 (8 / 2) 入栈 $\rightarrow$ 栈内容：[(6 - (2 + 3)), 3, (8 / 2)]
6. 遇到算符 +：弹出 (8 / 2) 和 3，组合为 (3 + 8 / 2) 入栈 $\rightarrow$ 栈内容：[(6 - (2 + 3)), (3 + 8 / 2)]
7. 遇到算符 *：弹出两个子式，组合为 ((6 - (2 + 3)) * (3 + 8 / 2)) 入栈
8. 遇到数字 2 入栈，随后遇到 ^（乘方）：弹出 2 和前式，组合为 ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 入栈
9. 遇到数字 3 入栈，随后遇到 +：组合为 ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3

对比选项，完美对应 A 选项。

第 9 题

原题：
数 $101010_2$ 和 $166_8$ 的和为（ ）
A. $(10110000)_2$
B. $(236)_8$
C. $(158)_{10}$
D. $(A0)_{16}$

正确答案： D

深度解析：
本题考查 不同进制数之间的转换与加法运算。

最稳妥的求解方式是将各进制数统一转换为 十进制 进行运算：

1. 将 $101010_2$ 转为十进制：
   

   $$101010_2 = 1 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 0 \times 2^0 = 32 + 8 + 2 = 42_{10}$$

2. 将 $166_8$ 转为十进制：
   

   $$166_8 = 1 \times 8^2 + 6 \times 8^1 + 6 \times 8^0 = 64 + 48 + 6 = 118_{10}$$

3. 求两数十进制之和：
   

   $$42_{10} + 118_{10} = 160_{10}$$

4. 校验各选项对应的十进制值：

   • A 项 $(10110000)_2 = 128 + 32 + 16 = 176_{10} \neq 160$
   • B 项 $(236)_8 = 2 \times 64 + 3 \times 8 + 6 = 158_{10} \neq 160$
   • C 项 $(158)_{10} = 158_{10} \neq 160$
   • D 项 $(A0)_{16} = 10 \times 16^1 + 0 \times 16^0 = 160_{10}$ （由于 $A=10$）

因此正确答案为 D。

第 10 题

原题：
假设有一组字符 {a, b, c, d, e, f}，对应的频率分别为 5%, 9%, 12%, 13%, 16%, 45%。请问以下哪个选项是字符 a,b,c,d,e,f 分别对应的一组哈夫曼编码？（ ）
A. 1111, 1110, 101, 100, 110, 0
B. 1010, 1001, 1000, 011, 010, 00
C. 000, 001, 010, 011, 10, 11
D. 1010, 1011, 110, 111, 00, 01

正确答案： A

深度解析：
本题考查 哈夫曼树（Huffman Tree）的构建与前缀码性质。

哈夫曼树的构建过程（每次挑选权值最小的两个节点合并）：

1. 初始频率：a:5%, b:9%, c:12%, d:13%, e:16%, f:45%
2. 合并 a(5) 和 b(9) $\rightarrow$ 得到新节点 (14)
3. 剩余：c(12), d(13), (14), e(16), f(45)
4. 合并 c(12) 和 d(13) $\rightarrow$ 得到新节点 (25)
5. 剩余：(14), e(16), (25), f(45)
6. 合并 (14) 和 e(16) $\rightarrow$ 得到新节点 (30)
7. 剩余：(25), (30), f(45)
8. 合并 (25) 和 (30) $\rightarrow$ 得到新节点 (55)
9. 合并 (55) 和 f(45) $\rightarrow$ 得到根节点 (100)

推导各字符在树中的深度（编码长度）：

• f 频率最高（45%），直接连在根节点下 $\rightarrow$ 编码长度为 1
• c(12) 和 d(13) 在 (25) 节点下 $\rightarrow$ 编码长度为 3
• e(16) 在 (30) 节点下 $\rightarrow$ 编码长度为 3
• a(5) 和 b(9) 在最底层的 (14) 节点下 $\rightarrow$ 编码长度为 4

字符 a,b,c,d,e,f 对应的编码长度应依次为 4, 4, 3, 3, 3, 1。

检查各选项编码长度：

• A 选项：长度依次为 $4, 4, 3, 3, 3, 1$。且校验无任何编码是另一个编码的前缀（满足前缀码条件）。
• B 选项：c 的编码 1000 长度为 4，与哈夫曼树不符。
• C 选项：a 的编码 000 长度为 3，不符。
• D 选项：f 的编码 01 长度为 2，不符合最优树结构。

因此正确答案为 A。

第 11 题

原题：
给定一棵二叉树，其前序遍历结果为：ABDECFG，中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么？（ ）
A. EDBGFCA
B. EDGBFCA
C. DEBGFCA
D. DBEGFCA

正确答案： A

深度解析：
本题考查 已知二叉树的前序遍历与中序遍历还原二叉树并求后序遍历。

建树分析：

1. 前序首字符 A 为根节点。在中序 DEBACFG 中定位 A：
   • 左子树中序：DEB
   • 右子树中序：CFG
2. 分析左子树 DEB：
   • 对应前序中的 BDE，可知左子树根节点为 B。
   • 在中序 DEB 中，B 的左侧为 DE，无右侧。
   • 前序中先出现 D 后出现 E，可知 D 为 B 的左孩子；中序 DE 说明 E 为 D 的右孩子。
3. 分析右子树 CFG：
   • 对应前序中的 CFG，可知右子树根节点为 C。
   • 在中序 CFG 中，C 无左侧，右侧为 FG。
   • 前序 FG 表明 F 为 C 的右孩子，G 为 F 的右孩子。

二叉树结构图解：

       A
      / \
     B   C
    /     \
   D       F
    \       \
     E       G

求后序遍历（左 $\rightarrow$ 右 $\rightarrow$ 根）：

• 左子树后序：E -> D -> B
• 右子树后序：G -> F -> C
• 根节点：A

组合后序遍历结果为：EDBGFCA，对应 A 选项。

第 12 题

原题：
考虑一个有向无环图，该图包含 4 条有向边：$(1, 2)$, $(1, 3)$, $(2, 4)$ 和 $(3, 4)$。以下哪个选项是这个有向无环图的一个有效的拓扑排序？（ ）
A. 4, 2, 3, 1
B. 1, 2, 3, 4
C. 1, 2, 4, 3
D. 2, 1, 3, 4

正确答案： B

深度解析：
本题考查 有向无环图（DAG）的拓扑排序。

拓扑排序规则： 对于图中的任意一条有向边 $(u, v)$，在拓扑序列中顶点 $u$ 必须排在顶点 $v$ 之前。

根据题目给出的 4 条边：

1. 边 $(1, 2)$：顶点 1 必须排在 2 之前
2. 边 $(1, 3)$：顶点 1 必须排在 3 之前
3. 边 $(2, 4)$：顶点 2 必须排在 4 之前
4. 边 $(3, 4)$：顶点 3 必须排在 4 之前

检查各选项：

• A 项 4, 2, 3, 1：顶点 4 排在 1 之前，违反约束。
• B 项 1, 2, 3, 4：1 在 2,3 之前，2,3 在 4 之前，完全满足要求！
• C 项 1, 2, 4, 3：4 排在 3 之前，违反了边 $(3, 4)$ 的要求。
• D 项 2, 1, 3, 4：2 排在 1 之前，违反了边 $(1, 2)$ 的要求。

正确答案选 B。

第 13 题

原题：
在计算机中，以下哪个选项描述的数据存储容量最小（ ）
A. 字节 (byte)
B. 比特 (bit)
C. 字 (word)
D. 千字节 (kilobyte)

正确答案： B

深度解析：
本题考查 计算机存储单位基本概念：

• 比特（bit / 位）：计算机中最基础、最小的数据存储单位，表示一个二进制位（0 或 1）。
• 字节（Byte）：计算机数据存储的基本计量单位，$1 \text{ Byte} = 8 \text{ bits}$。
• 字（Word）：计算机处理数据时一次性存取、加工的二进制代码组，大小与 CPU 字长有关（如 32 位机器中 $1 \text{ Word} = 4 \text{ Bytes} = 32 \text{ bits}$）。
• 千字节（KB）：$1 \text{ KB} = 1024 \text{ Bytes} = 8192 \text{ bits}$。

根据换算关系：$\text{bit} < \text{Byte} \le \text{Word} < \text{KB}$，因此**比特（bit）**最小。

第 14 题

原题：
一个班级有 10 个男生和 12 个女生。如果要选出一个 3 人的小组，并且小组中必须至少包含 1 个女生，那么有多少种可能的组合？（ ）
A. 1420
B. 1770
C. 1540
D. 2200

正确答案： A

深度解析：
本题考查 组合数学与计数问题。

全班总人数 $= 10 + 12 = 22$ 人。要求选出 3 人，且至少有 1 个女生。

方法一：反向剔除法（正难则反，推荐）

1. 不加限制地从 22 人中任选 3 人的总组合数：

   $$C_{22}^3 = \frac{22 \times 21 \times 20}{3 \times 2 \times 1} = 1540$$

2. 不符合要求的组合数（即选出的 3 人全为男生，没有女生）：

   $$C_{10}^3 = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$$

3. 符合“至少包含 1 个女生”的组合数：

   $$\text{满足要求的组合数} = C_{22}^3 - C_{10}^3 = 1540 - 120 = 1420$$

方法二：分类讨论法

• 情形 1：1 女 2 男
  $C_{12}^1 \times C_{10}^2 = 12 \times 45 = 540$
• 情形 2：2 女 1 男
  $C_{12}^2 \times C_{10}^1 = 66 \times 10 = 660$
• 情形 3：3 女 0 男
  $C_{12}^3 = \frac{12 \times 11 \times 10}{6} = 220$

两种方法计算结果一致，对应 A 选项。

第 15 题

原题：
以下哪个不是操作系统？（ ）
A. Linux
B. Windows
C. Android
D. HTML

正确答案： D

深度解析：
本题考查 计算机基础知识与系统软件常识：

• A. Linux：开源的操作系统内核及基于该内核的各类操作系统发行版（如 Ubuntu, CentOS 等）。
• B. Windows：微软公司开发的广泛应用于个人电脑和服务器的操作系统。
• C. Android：谷歌公司基于 Linux 内核开发的移动设备操作系统。
• D. HTML：全称 HyperText Markup Language（超文本标记语言），是用于创建网页结构的标记语言，属于应用层文档规范，不是操作系统。

正确答案选 D。

💡 总结与备考建议

从 2023 年 CSP-J 第一轮单项选择题来看，考察重点非常清晰：

1. 基础计算机常识（第 1, 13, 15 题）：掌握关键字、存储单位与操作系统等概念。
2. 进制与数据表示（第 2, 9 题）：熟练掌握二进制、八进制、十进制、十六进制之间的相互转换与对位计算。
3. 数据结构基础（第 3, 4, 5, 11, 12 题）：链表插入、多叉树节点与高度关系、二叉树遍历还原、有向无环图的拓扑排序等是高频考点。
4. 组合数学与算法（第 6, 7, 8, 10, 14 题）：重点考察分类讨论/插空法、表达式转换（栈的应用）、哈夫曼编码的前缀码机制以及高精度运算复杂度分析。

建议同学们在备考时加强动手草稿计算能力（进制转换与树/图的推演），理解算法原理而非机械背诵！

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号