本报告从NOI大纲出发，对CSP-S 2023的全部四道机试题目进行了分析。报告详细分析了每道题目考察的主要知识点及其难度系数设置，以及题目设计对选手的能力要求等，最后对题目的知识构成做出总体性评价。

2023年度CCF非专业级软件能力认证(CSP-J/S)第二轮提高级于2023年10月21日下午顺利举行。本次活动提高级一等全国认证基准线为135分，提高级二等全国认证基准线为80分，提高级三等全国认证基准线为55分。本报告将从《全国青少年信息学奥林匹克系列竞赛大纲》（NOI大纲） 出发，对CSP-S 2023的全部四道机试题目进行分析。对每道题目，报告将详细分析题目考察的主要知识点及其难度系数设置，以及题目设计对选手的能力要求等，最后对题目的知识构成做出总体性评价。CSP-S 2023包括4道题目。分别为：

密码锁(lock)；消消乐(game)；结构体(struct)；种树(tree)。

全部题目所涉及的主要知识点统计如下：

表1 CSP-S 2023题目所涉及的主要知识点

序号

知识点

级别

板块

编号

难度

1

基本数据类型

入门

C++程序设计

2.1.2.2

1

2

cin 语句、scanf 语句、cout 语句、printf 语句、赋值语句、复合语句

入门

C++程序设计

2.1.2.3-1

2

3

for 语句、while 语句、do while 语句

入门

C++程序设计

2.1.2.3-3

2

4

多层循环语句

入门

C++程序设计

2.1.2.3-4

3

5

二维数组与多维数组

入门

C++程序设计

2.1.2.7-3

3

6

结构体

入门

C++程序设计

2.1.2.10-1

3

7

链表：单链表、双向链表、循环链表

入门

数据结构

2.1.3.1-1

3

8

栈

入门

数据结构

2.1.3.1-2

3

9

树的表示与存储

入门

数据结构

2.1.3.2-2

4

10

字符串哈希函数构造

提高

数据结构

2.2.2.5-3

6

11

字典树（trie树）

提高

数据结构

2.2.3.3-2

6

12

枚举法

入门

算法

2.1.4.2-1

1

13

模拟法

入门

算法

2.1.4.2-1

1

14

贪心法

入门

算法

2.1.4.3-1

3

15

二分法

入门

算法

2.1.4.3-4

4

16

深度优先搜索

入门

算法

2.1.4.6-1

5

17

简单一维动态规划

入门

算法

2.1.4.8-2

4

18

状态压缩动态规划

提高

算法

2.2.4.8-2

7

19

代数（初中部分）

入门

数学与其他

2.1.5.2-1

1

主要知识点的学习难度系数分布统计如下：

图1 知识点难度系数统计图

主要知识点的板块分布统计如下：

图2 知识点板块统计图

总体上看，CSP-S 2023所考察的主要知识点在“难度”上以3级知识点最多，而在“板块”上则以“算法”知识点最多。主要知识点的学习难度系数，范围为从1到8，与大纲的建议考察范围基本一致。

1 密码锁

1.1 知识构成

本题所考察的知识点主要包括程序语法的多层循环语句和多维数组，以及算法中的枚举算法等。其中，“枚举”属于“入门级”的“入门算法”，大纲标注学习难度系数为1；“多层循环语句”属于“入门级”的“程序基本语句”，大纲标注学习难度系数为3；“多维数组”属于“入门级”的“二维数组与多维数组”，大纲标注学习难度系数为3。所涉及知识点难度均不超过大纲规定提高级考试所要求的难度。

1.2 难度梯度

本题的部分分所考察的知识点具体包括：

部分分描述

分值

涉及知识点

1~3

30

2.1.2.3-1【2】cin 语句、scanf 语句、cout 语句、printf 语句、赋值语句、复合语句

4~10

70

2.1.4.2-1【1】枚举法

2.1.2.3-4【3】多层循环语句

2.1.2.7-3【3】二维数组与多维数组

本题的“知识点难度系数—可得分数”关系见下图（横轴为知识点难度系数，纵轴为不超过该难度的可得分数）：

图3 题目“密码锁”的难度设置曲线

1.3 总体评价

本题所考察的知识点的最高难度系数为3级，与大纲关于竞赛题目的命题建议相符。所涉及的知识点均为入门级知识点，作为提高组的第一题较为简单。

2 消消乐

2.1 知识构成

本题正解所考察的主要知识点包括：字典树（trie树）、字符串哈希函数构造。其中，“字典树（trie树）”属于“提高级”的“特殊树”，大纲标注学习难度系数为6；“字符串哈希函数构造”属于“提高级”的“哈希表”，大纲标注学习难度系数为6。所涉知识点难度均不超过大纲规定CSP-S考试所要求的难度（提高级）。

2.2 难度梯度

本题的部分分所考察的知识点具体包括：

部分分描述

分值

涉及知识点

1~5

25

2.1.2.3-4【3】多层循环语句

或

2.1.4.6-1【4】深度优先搜索

6~7

10

2.1.2.3-4【3】多层循环语句

2.1.3.1-2【3】栈

8~10

15

2.1.2.3-4【3】多层循环语句

2.1.3.1-2【3】栈

或

2.1.4.8-2【4】简单一维动态规划

11~12

10

2.1.2.3-4【3】多层循环语句

2.1.3.1-2【3】栈

13~14

10

2.2.2.3-2【6】字典树（trie树）

15~17

15

2.2.2.3-2【6】字典树（trie树）

或

2.1.3.1-2【3】栈

2.2.2.5-3【6】字符串哈希函数构造

18~20

15

2.2.2.3-2【6】字典树（trie树）

或

2.1.3.1-2【3】栈

2.2.2.5-3【6】字符串哈希函数构造

本题的“知识点难度系数—可得分数”关系见下图（横轴为知识点难度系数，纵轴为不超过该难度的可得分数）：

图4 题目“消消乐”的难度设置曲线

2.3 总体评价

本题正解所考察知识点的最高难度系数为6级，与大纲关于竞赛题目的命题建议相符。从考察知识点难度来看，本题的最后一步优化有多种解法，选手可自行选择哈希、trie树、动态规划等多种算法通过，涉及知识点广泛。

本题也着重考察了选手观察性质并分析的能力，根据分析性质的深浅程度设计了不同档次的部分分，部分分设计合理。

3 结构体

3.1知识构成

本题涉及的知识点包括基本数据类型、结构体和模拟算法。其中，基本数据类型和结构体均属于入门级C++程序设计，基本数据类型的大纲标注学习难度系数为1，结构体的学习难度系数为3。模拟算法属于入门级算法，大纲标注学习难度系数为1。本题要求模拟一种类似C++的高级语言的结构体定义方式，并计算出相应的内存占用等信息。本题思维难度不高，代码实现较复杂，综合难度为3，所涉知识点难度均不超过大纲规定CSP-S级认证所要求的难度。

3.2 难度梯度

分数描述

分值

涉及知识点

1～20

100

2.1.2.2【1】基本数据类型

2.1.2.10-1【3】结构体

2.1.4.2-1【1】模拟法

本题的“知识点难度系数—可得分数”关系见下图（横轴为知识点难度系数，纵轴为不超过该难度的可得分数）：

图5 题目“结构体”的难度设置曲线

3.3总体评价

本题作为模拟算法题，所考察的知识点在大纲中不超过3级。题意简明扼要，描述清晰，整体难度合理，考察选手对于规模较大的模拟算法试题的驾驭能力，设置了一定梯度的部分分。本题符合大纲对于CSP-S级别试题难度的预设。

4 种树

4.1 知识构成

本题正解所考察的主要知识点包括：树的表示与存储、二分法、贪心法。其中“树的表示与存储”属于“入门级”的“简单树”，大纲标注学习难度系数为4；“二分法”属于“入门级”的“基础算法”，大纲标注学习难度系数为4；“贪心法”属于“入门级”的“基础算法”，大纲标注学习难度系数为3。

本题所涉知识点难度均不超过大纲规定CSP-S考试所要求的难度。

4.2 难度梯度

本题的部分分所考察的知识点具体包括：

部分分描述

分值

涉及知识点

1

5

2.1.3.2-2【4】树的表示与存储

2.1.4.3-4【4】二分法

2.1.4.3-1【3】贪心法

或

2.1.3.2-2【4】树的表示与存储

2.2.4.8-2【7】状态压缩动态规划

2~4

15

2.1.3.2-2【4】树的表示与存储

2.1.4.3-4【4】二分法

2.1.4.3-1【3】贪心法

或

2.1.3.2-2【4】树的表示与存储

2.2.4.8-2【7】状态压缩动态规划

5~6

10

2.1.3.2-2【4】树的表示与存储

2.1.4.3-4【4】二分法

2.1.4.3-1【3】贪心法

7~8

10

2.1.3.2-2【4】树的表示与存储

2.1.4.3-4【4】二分法

2.1.4.3-1【3】贪心法

9~10

10

2.1.5.2-1【1】代数（初中部分）

2.1.2.3-3【2】for 语句、while 语句、do while 语句

或

2.1.4.3-4【4】二分法

2.1.2.3-3【2】for 语句、while 语句、do while 语句

11~13

15

2.1.5.2-1【1】代数（初中部分）

2.1.3.1-1【3】链表：单链表、双向链表、循环链表

或

2.1.4.3-4【4】二分法

2.1.3.1-1【3】链表：单链表、双向链表、循环链表

14~16

15

2.1.5.2-1【1】代数（初中部分）

2.1.4.3-1【3】贪心法

17~20

20

2.1.3.2-2【4】树的表示与存储

2.1.4.3-4【4】二分法

2.1.4.3-1【3】贪心法

本题的“知识点难度系数—可得分数”关系见下图（横轴为知识点难度系数，纵轴为不超过该难度的可得分数）：

图6 题目“种树”的难度设置曲线

4.3 总体评价

本题的正解的知识点最高难度系数为4级，设置了一定梯度的部分分，主要考察选手思维能力，对多种基础算法的灵活运用，符合大纲对于CSP-S级别试题难度的预设。

结论

通过对CSP-S 2023全部4道机试题目的深入分析，可以明确看到，板块知识点的分布较广，包括了C++程序设计、数据结构、算法、数学与其他等多个板块。各道题目在主要知识点及其难度系数设置上均符合《NOI大纲》的建议，且题目设计更侧重于对选手思维能力的考察，而非单纯的知识性考核，有利于激发和培养学生的创造性思维以及解决问题的综合能力。

报告执笔人：

汪星明 北京十一学校

李 建 浙江省杭州第二中学

金 靖 华东师范大学第二附属中学

胡伟栋 北京师范大学附属实验中学

叶金毅 中国人民大学附属中学

杨耀良 清华大学

赵启阳 北京航空航天大学

韩文弢 清华大学

CCF

严正声明

NOI为CCF品牌项目，其对外宣传平台仅有三个，分别是：

1.中国计算机学会(CCF)官网

()

2.全国青少年信息学奥林匹克(NOI)官网

()

3.“中国计算机学会”微信公众号

(ccfvoice)

以上三个平台的NOI相关新闻如需转载，必须事先征得CCF NOI竞赛办公室书面同意，未经书面授权的任何形式的转载都是非法侵权行为，我学会将依法追究相关法律责任。对于机构或组织冒用我学会的商标标识混淆视听以达到欺骗选手及家长进行多次消费的行为，我学会一经发现必当严肃追究，此类行为将受到法律制裁。