CCF CSP第一轮认证一本通

针对历年真题和典型习题进行详细解析，针对考试大纲提供大量练习题，针对考试内容提供详尽分析；配套4套真题和2套模拟题供读者实战！

《CCF CSP轮认证一本通》根据CSPJ1/S1考试题型，并综合了近两年CSPJ1/S1考试真题和近10年信息学奥赛初赛考试真题编写而成。在编写过程中，所有题目都完全模拟CSPJ1/S1考试的题型，在对题目进行分析的同时，也对考试知识点进行了梳理，能够更好地帮助考生理清考试思路和把握重难点。 《CCF CSP轮认证一本通》共8章，前4章对选择题的知识点进行了梳理，后4章对阅读程序题和完善程序题的知识点进行了梳理。针对每章知识，首先介绍这一章的知识点，让考生有大体把握，然后对该知识点的题目进行详细分析，后提供有针对性的习题供考生复习巩固。通过知识、分析、练习等多种形式让考生轻松掌握CSPJ1/S1考试的知识内容，帮助考生更好地通过考试。 《CCF CSP轮认证一本通》主要供广大考生作为CSPJ1/S1轮认证考试之用，也可作为相关人士学习信息学的辅导书。

丁向民：男，河南郏县人，毕业于南京航空航天大学，现在盐城师范学院工作，一直从事青少年信息学奥赛的指导和学生培养，著有《信息学奥赛真题分类解析初赛篇》（半年销量3000余册）等多部图书，另外，近年来指导了近百名中小学学生参加NOIP、CSP-J/S认证考试。

第1章计算机基础知识1
1.1基本常识1
1.1.1基本知识介绍1
1.1.2典型习题解析6
1.1.3知识点巩固9
1.2系统结构9
1.2.1基本知识介绍9
1.2.2典型习题解析11
1.2.3知识点巩固16
1.3软件系统17
1.3.1基本知识介绍17
1.3.2典型习题解析18
1.3.3知识点巩固20
1.4数据表示与计算21
1.4.1基本知识介绍21
1.4.2典型习题解析24
1.4.3知识点巩固29
1.5信息编码30
1.5.1基本知识介绍30
1.5.2典型习题解析33
1.5.3知识点巩固36
1.6网络基础37
1.6.1基本知识介绍37
1.6.2典型习题解析45
1.6.3知识点巩固50
第2章程序设计基础52
2.1计算机语言与算法52
2.1.1基本知识介绍52
2.1.2典型习题解析56
2.1.3知识点巩固62
2.2C 语言基础62
2.2.1基本知识介绍62
2.2.2典型习题解析64
2.2.3知识点巩固68
第3章基本数据结构70
3.1线性表70
3.1.1基本知识介绍70
3.1.2典型习题解析71
3.1.3知识点巩固73
3.2栈和队列74
3.2.1基本知识介绍74
3.2.2典型习题解析75
3.2.3知识点巩固80
3.3树81
3.3.1基本知识介绍81
3.3.2典型习题解析82
3.3.3知识点巩固86
3.4图87
3.4.1基本知识介绍87
3.4.2典型习题解析88
3.4.3知识点巩固91
3.5排序92
3.5.1基本知识介绍92
3.5.2典型习题解析97
3.5.3知识点巩固99
第4章算法与数学101
4.1应用数学101
4.1.1基本知识介绍101
4.1.2典型习题解析104
4.1.3知识点巩固109
4.2组合学110
4.2.1基本知识介绍111
4.2.2典型习题解析112
4.2.3知识点巩固117
第5章阅读程序和完善程序119
5.1阅读程序和完善程序概述119
5.2常用解题方法119
5.2.1模拟法119
5.2.2先猜测、后验证122
第6章C 基础语法127
6.1基本知识介绍127
6.1.1常量与变量127
6.1.2C 的3种基本控制结构128
6.1.3数组131
6.1.4函数132
6.2典型习题解析134
6.3知识点巩固163
第7章数据结构173
7.1基本知识介绍173
7.1.1数组173
7.1.2栈174
7.1.3队列175
7.1.4树和二叉树177
7.1.5图179
7.2典型习题解析181
7.3知识点巩固188
第8章算法193
8.1基本知识介绍193
8.1.1查找算法193
8.1.2排序算法194
8.1.3贪心算法197
8.1.4分治算法200
8.1.5回溯算法201
8.1.6动态规划204
8.2典型习题解析206
8.3知识点巩固221
附录A2019—2020年CSPJ/S轮认证真题试卷227
附录BCSPJ/S轮认证模拟试卷(2份)267
附录C部分习题参考答案290

随着国家对青少年编程教育重视程度的不断增强，越来越多的中小学生开始学习编程。经过一段时间的学习，随之而来的问题就是如何评价学生的学习效果。编程教育的评价标准相对较难制定，一方面，基层的高水平编程教育人员相对较少，出一份高质量的检测试卷比较困难；另一方面，编程的灵活性很强，对于阅卷人的要求也很高。针对这种情况，CSPJ/S无疑是一种较好的评价方式，它是由CCF创办的针对青少年的非专业级软件能力认证，于2019年开设，分为CSPJ(Junior，入门级)和CSPS(Senior，提高级)两组，分别进行两轮认证。
CSPJ/S为什么是一种好的评价模式呢？一方面，试卷由CCF专家组出题，试卷题目的质量很高；另一方面，认证试题全部采用客观题，降低了阅卷人的门槛，也减少了人工阅卷的失误，所以其认可度非常高。另外，该认证对于学生报名没有门槛，不设年龄、性别限制，在校生和在职人员均可参加，所以其影响面很广。
盐城胜伴教育科技是一家致力于青少年编程教育的机构，由于CSPJ/S认证考试刚刚改革不久，目前市面上很少有专门的辅导资料，为了能够更好地服务广大考生，公司将平时的辅导资料进行了整理，以供广大考生一起学习，通过增加练习和辅导资料提高通过认证的概率。
CSPJ/S轮认证的形式为笔试，侧重考查学生的计算机基础知识和基本编程能力，并对知识面的广度进行测试。题型由三部分组成: 一是选择题，共15题，每题2分，共30分；二是阅读程序题，共3大题，一般由18道判断题和选择题组成，共40分；三是完善程序题，共2大题，由10道选择题组成，共30分。本书分为两部分，第1～4章主要分析大题，第5～8章分析第二、三大题。每章的内容主要分为三部分: 一是本章的知识点，让考生对本章有大体把握；二是针对知识点进行试题分析；三是针对性的练习。
在近几年的考试辅导过程中作者发现: 虽然每年的考试题目千差万别，但每年考查的知识点都变化不大。所以，本书的撰写主要围绕知识点展开，一是将真题划分到各个章节，二是将每道题目归类到各个知识点。通过分析，能够把握历年的考试情况，让考生对历年考查的知识点一目了然，以帮助考生复结。在撰写过程中，作者尽量利用图表说明知识点情况，既可以让考生进行数据对照，也可以浏览概况。在试题解析过程中，作者也尽量利用各类图表解释题目，让考生能够尽量形象地理解题目。
本书主要由盐城胜伴教育校长丁向民负责撰写，多名老师和同学参与了试题的出题和校正，主要包括尤文、王成成、王子苏、朱峰、丁昱岑、李兆亮、陈相斌、贲依婷等。在本书的撰写过程中，编者还引用了一些文献和网络中的解题思路，在此对各位参与者和原创者一并表示感谢。
由于时间仓促，本书难免有错误和不足之处，请广大读者批评指正。

编者2021年3月