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

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

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

第 1 题

原题：
以下哪种功能没有涉及 C++ 语言的面向对象特性支持：（ ）。
A. C++ 中调用 printf 函数
B. C++ 中调用用户定义的类成员函数
C. C++ 中构造一个 class 或 struct
D. C++ 中构造来源于同一基类的多个派生类

正确答案： A

深度解析：
本题考查 C++ 的 面向对象特性。

• printf 是 C 语言的输入输出库函数，属于面向过程的函数调用，并没有涉及面向对象的特性（如封装、继承、多态）。
• B、C、D 选项分别涉及了类的成员函数、类的定义以及类的继承派生，都是典型的面向对象特性。

第 2 题

原题：
有 6 个元素，按照 6, 5, 4, 3, 2, 1 的顺序进入栈 S，请问下列哪个出栈序列是非法的（ ）。
A. 5, 4, 3, 6, 1, 2
B. 4, 5, 3, 1, 2, 6
C. 3, 4, 6, 5, 2, 1
D. 2, 3, 4, 1, 5, 6

正确答案： C

深度解析：
本题考查 栈的后进先出（LIFO）特性。根据进栈顺序 6, 5, 4, 3, 2, 1 逐个模拟：

• A 项：6, 5 进，5 出；4 进，4 出；3 进，3 出；此时栈顶是 6，6 出；2, 1 进，1 出，2 出。合法。
• B 项：6, 5, 4 进，4 出；此时栈顶是 5，5 出；3 进，3 出；2, 1 进，1 出，2 出；最后栈顶是 6，6 出。合法。
• C 项：6, 5, 4, 3 进，3 出；此时栈顶是 4，4 出；此时栈顶应该是 5。但选项中下一个出栈的是 6，而 6 在 5 的下面，无法越过 5 直接出栈。非法。
• D 项：6, 5, 4, 3, 2 进，2 出；此时栈顶是 3，3 出；栈顶是 4，4 出；1 进，1 出；此时栈顶是 5，5 出；最后 6 出。合法。

第 3 题

原题：
运行以下代码片段的行为是（ ）。

1 2 3 4 5

int x = 101; int y = 201; int *p = &x; int *q = &y; p = q;

A. 将 x 的值赋为 201
B. 将 y 的值赋为 101
C. 将 q 指向 x 的地址
D. 将 p 指向 y 的地址

正确答案： D

深度解析：
本题考查 指针的基本赋值操作： 代码中 p 和 q 都是指针变量。q 存储的是 y 的地址。 执行 p = q; 即把 q 中存储的地址赋值给 p，因此 p 也变成了指向 y 的地址，并不会改变 x 或 y 变量本身的值。

第 4 题

原题：
链表和数组的区别包括（ ）。
A. 数组不能排序，链表可以
B. 链表比数组能存储更多的信息
C. 数组大小固定，链表大小可动态调整
D. 以上均正确

正确答案： C

深度解析：
本题考查 数组与链表的基本性质：

• A 选项错误：数组和链表都可以进行排序操作（如数组使用快排，链表使用归并排序）。
• B 选项错误：存储信息的容量取决于可用内存，并不存在链表必定比数组能存储更多信息的说法，且链表为了维护结构还需要额外的空间存储指针。
• C 选项正确：普通数组在声明时必须指定大小且大小不可变（静态分配内存连续）；而链表可以利用指针动态分配内存，大小可随时动态调整。

第 5 题

原题：
对假设栈 S 和队列 Q 的初始状态为空。存在 e1 ~ e6 六个互不相同的数据，每个数据按照进栈 S、出栈 S、进队列 Q、出队列 Q 的顺序操作，不同数据间的操作可能会交错。已知栈 S 中依次有数据 e1、e2、e3、e4、e5 和 e6 进栈，队列 Q 依次有数据 e2、e4、e3、e6、e5 和 e1 出队列。则栈 S 的容量至少是（ ）个数据。
A. 2
B. 3
C. 4
D. 6

正确答案： B

深度解析：
本题考查 栈与队列的性质及混合模拟。 队列 Q 是先进先出，所以出队列的顺序也就是进队列的顺序。根据题意，数据是先出栈再进队列，因此队列的出队顺序其实就等同于栈的出栈顺序。 已知入栈顺序为：e1, e2, e3, e4, e5, e6。出栈顺序为：e2, e4, e3, e6, e5, e1。 我们模拟栈的操作过程，计算栈中最大元素个数：

1. 进 e1 （栈中元素：e1，共 1 个）
2. 进 e2 （栈中元素：e1, e2，共 2 个）
3. 出 e2 （栈中元素：e1，共 1 个）
4. 进 e3 （栈中元素：e1, e3，共 2 个）
5. 进 e4 （栈中元素：e1, e3, e4，共 3 个） <– 此时达到最大容量 3
6. 出 e4 （栈中元素：e1, e3，共 2 个）
7. 出 e3 （栈中元素：e1，共 1 个）
8. 进 e5 （栈中元素：e1, e5，共 2 个）
9. 进 e6 （栈中元素：e1, e5, e6，共 3 个） <– 再次达到最大容量 3
10. 出 e6 （栈中元素：e1, e5，共 2 个）
11. 出 e5 （栈中元素：e1，共 1 个）
12. 出 e1 （栈空）

模拟过程中，栈内同时存在的最大元素个数为 3，因此栈的容量至少是 3。

第 6 题

原题：
对表达式 a+(b-c)*d 的前缀表达式为（ ），其中 +、-、* 是运算符。
A. *+a-bcd
B. +a*-bcd
C. abc-d*+
D. abc-+d

正确答案： B

深度解析：
本题考查 中缀表达式转前缀表达式。 转换可以借助表达式树（或括号法）： a + ((b - c) * d)

1. (b - c) 的前缀为：- b c
2. (b - c) * d 的前缀为：* - b c d
3. a + 上述结果 的前缀为：+ a * - b c d 最终结果：+a*-bcd。

第 7 题

原题：
假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 10%, 15%, 30%, 16%, 29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d 的编码长度（ ）位。
A. 1
B. 2
C. 2 或 3
D. 3

正确答案： B

深度解析：
本题考查 哈夫曼树的构造过程： 初始频率：a(10), b(15), d(16), e(29), c(30)。

1. 取最小的两个 a(10) 和 b(15) 合并，得到新节点 25。剩余权重：16, 25, 29, 30。
2. 取最小的两个 d(16) 和 25 合并，得到新节点 41。剩余权重：29, 30, 41。
3. 取最小的两个 e(29) 和 c(30) 合并，得到新节点 59。剩余权重：41, 59。
4. 将最后的 41 和 59 合并为根节点 100。

推导各字符在哈夫曼树中的深度：

• 根节点 100 有两个子节点 41 和 59。
• 41 的子节点为 d(16) 和 25。因此 d 位于树的第 2 层（深度为 2）。
• d 的哈夫曼编码长度为 2 位。

第 8 题

原题：
一棵有 $n$ 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。
A. 8、18
B. 10、18
C. 8、19
D. 10、19

正确答案： C

深度解析：
本题考查 完全二叉树的数组顺序存储性质。 对于存储在数组下标 $i$ 的结点（根节点下标为 1）：

• 左子结点下标为 $2 \times i$
• 右子结点下标为 $2 \times i + 1$
• 父结点下标为 $\lfloor i / 2 \rfloor$

题目中指定结点位置为 $i = 9$：

• 其父结点位置为 $\lfloor 9 / 2 \rfloor = 4$。
• 父结点 4 的两个孩子分别是 $2 \times 4 = 8$ 和 $2 \times 4 + 1 = 9$。因此 9 的左兄弟结点位置为 8。
• 结点 9 的右子结点位置为 $2 \times 9 + 1 = 19$。

兄弟结点为 8，右子结点为 19。

第 9 题

原题：
考虑由 $N$ 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。
A. $N - 1$
B. $N$
C. $N + 1$
D. $N^2$

正确答案： B

深度解析：
本题考查 有向图的连通性与邻接矩阵。 在图论中，“有向连通图”通常指的是 强连通图（即任意两个顶点互相可达）。 为了构成一个包含 $N$ 个顶点的强连通图，最少需要用 $N$ 条有向边构成一个包含所有顶点的大环。 每一条有向边在邻接矩阵中对应一个非零元素。因此至少需要 $N$ 条边，对应邻接矩阵中至少存在 $N$ 个非零元素。

第 10 题

原题：
以下对数据结构的表述不恰当的一项为：（ ）。
A. 图的深度优先遍历算法常使用的数据结构为栈。
B. 栈的访问原则后进先出，队列的访问原则是先进先出。
C. 队列常常被用于广度优先搜索算法。
D. 栈与队列存在本质不同，无法用栈实现队列。

正确答案： D

深度解析：
本题考查 基础数据结构特性。

• A 项正确，DFS（深度优先搜索）本质是递归，底层使用系统调用栈；也可以手动使用栈来非递归实现。
• B、C 项均正确描述了栈、队列的基本原则及典型应用场景（队列用于 BFS）。
• D 项错误！我们可以使用两个栈来模拟实现一个队列的全部功能（一个专门负责入栈，一个专门负责出栈处理）。因此“无法用栈实现队列”的说法是错误的。

第 11 题

原题：
以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）：（ ）。
A. p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
B. p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
C. s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
D. s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

正确答案： D

深度解析：
本题考查 双向链表的结点插入操作顺序。 假设 p 的原后继结点为 q（即 p->next）。我们需要在 p 和 q 之间插入 s。为避免丢失 q 的指针，关键是在修改 p->next 之前，必须先处理好与原后继结点的连接。 分析 D 选项的操作：

1. s->next=p->next; $\rightarrow$ 将 s 的后继指向原来的 q。
2. p->next->prev=s; $\rightarrow$ 将原来 q 的前驱指向 s。
3. s->prev=p; $\rightarrow$ 将 s 的前驱指向 p。
4. p->next=s; $\rightarrow$ 最后，将 p 的后继指向 s。 整个顺序逻辑严密，没有任何指针丢失的错误。A 和 C 选项中在赋值 p->next=s 之后，又使用了 p->next，导致逻辑谬误。

第 12 题

原题：
以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。
A. 冒泡排序算法是稳定的
B. 简单选择排序是稳定的
C. 简单插入排序是稳定的
D. 归并排序算法是稳定的

正确答案： B

深度解析：
本题考查 十大排序算法的稳定性： 排序算法的“稳定性”是指：相等的元素在排序后，相对顺序保持不变。

• 冒泡排序、简单插入排序、归并排序均可以通过严谨的边界判断做到稳定。
• 简单选择排序是不稳定的。例如序列 [5, 5, 2]，第一趟寻找最小值 2 并与第一个位置交换，序列变为 [2, 5, 5]，导致原来两个 5 的相对位置被破坏。

第 13 题

原题：
八进制数 32.1 对应的十进制数是（ ）。
A. 24.125
B. 24.250
C. 26.125
D. 26.250

正确答案： C

深度解析：
本题考查 带小数的进制转换。 将八进制 $32.1_8$ 按权展开转为十进制：

• 整数部分 $32_8 = 3 \times 8^1 + 2 \times 8^0 = 24 + 2 = 26$
• 小数部分 $0.1_8 = 1 \times 8^{-1} = \frac{1}{8} = 0.125$ 两者相加为 $26.125$。

第 14 题

原题：
一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab 有（ ）个内容互不相同的子串。
A. 12
B. 13
C. 14
D. 15

正确答案： B

深度解析：
本题考查 字符串子串及去重计算。 我们按子串长度枚举：

• 长度 0（空串）：""（1个）
• 长度 1：a, b, c（去重后 3个）
• 长度 2：ab, bc, ca（去重后 3个，末尾的 ab 与前面重复）
• 长度 3：abc, bca, cab（3个）
• 长度 4：abca, bcab（2个）
• 长度 5：abcab（1个） 总计：$1 + 3 + 3 + 3 + 2 + 1 = 13$ 个。

第 15 题

原题：
以下对递归方法的描述中，正确的是：（ ）。
A. 递归是允许使用多组参数调用函数的编程技术
B. 递归是通过调用自身来求解问题的编程技术
C. 递归是面向对象和数据而不是功能和逻辑的编程语言模型
D. 递归是将用某种高级语言转换为机器代码的编程技术

正确答案： B

深度解析：
本题考查 递归编程基础概念。 递归的本质特征就是函数在执行过程中直接或间接地调用自身。

• A 是函数重载/多态的特点。
• C 描述的是面向对象编程（OOP）模型。
• D 描述的是编译/解释技术。 因此正确答案选 B。

💡 总结

CSP-J 2022 第一轮选择题覆盖的知识点相对经典且基础：

1. 栈与队列：是近几年考察的极高频考点，不仅要了解其进出原则，还需要熟练应对交错出入栈的手算推演模拟（如第 2、5 题）。
2. 树与二叉树：哈夫曼编码与完全二叉树的数组下标运算是老生常谈的题目，必须熟练掌握。
3. 指针与链表：双向链表的插入需要极度注重顺序逻辑防“断链”（第 11 题）。
4. 基础数据：各种排序稳定性及进制小数转换不可丢分。

预祝各位考生在备考中夯实基础，稳中求胜！

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

GESP 学习专题站：GESP WIKI

"luogu-"系列题目可在洛谷题库进行在线评测。

"bcqm-"系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助