¥97.90 128.00

　　编辑推荐

　　《信息学奥赛一本通关》既可以作为由图形化编程转向C++ 代码编程的教材，又可以作为信息学奥赛辅导教材，还可以作为大学生计算机竞赛入门学习的教材，供信息学爱好者参考使用。

　　内容简介

　　《信息学奥赛一本通关》共30 章分7 部分。其中前6 部分内容分别为编程平台介绍、计算机基础知识、从图形化编程到C++ 入门、数学知识基础、数据结构和算法补充与归纳。第七部分给出2019—202年CSP-J/S 真题及参考答案。本书基于图形化编程学习，详细介绍由图形化编程向C++ 代码编程过渡的系统知识，最终帮助读者提高参与信息学奥赛的水平。

　　作者简介

　　蔡荣啸,中国教育技术协会人工智能专业委员会理事，中国教育学会会员，青岛市人工智能教材编委会成员，创新科技项目优秀指导教师。辅导学生多人获得信息学奥赛一二三等奖，并有多人获得信息技术创新类一二三等奖。拥有软件著作权两项。出版专著三套：《scratch+小学数学》《python玩转人工智能》《人形机器人编程实践》，主持中央电化教育馆重点课题一项，主持青岛市教育学会课题一项，参与山东省十三五规划课题两项。在CSSCI与国内核心期刊发表论文多篇。Mathmatics and Computer Science邀请作者。

　　目录

　　第一部分

　　编程平台介绍

　　第1 章 图形化编程模块简介 2

　　1.1 变量 2

　　1.2 运算符 4

　　1.3 顺序语句 6

　　1.4 分支语句 6

　　1.5 循环语句 8

　　1.6 函数运算 9

　　第2 章 Dev-C++ 简介 10

　　2.1 Dev-C++ 界面 10

　　2.2 快捷键 11

　　2.3 调试配置 11

　　2.4 设置断点并查看 12

　　2.5 编译器与编译日志 13

　　第二部分

　　计算机基础知识

　　第3 章 信息学奥赛简介 16

　　3.1 NOIP 16

　　3.2 CSP-J/S 16

　　3.3 NOI 17

　　3.4 APIO 和IOI 17

　　第4 章 计算机硬件基础 18

　　4.1 计算机发展史 18

　　4.2 计算机硬件 19

　　4.2.1 运算器 20

　　4.2.2 控制器 20

　　4.2.3 存储器 21

　　4.2.4 输入设备 21

　　4.2.5 输出设备 22

　　4.3 数制与编码 22

　　4.3.1 二进制与十进制 24

　　4.3.2 二进制与八进制 25

　　4.3.3 二进制与十六进制 26

　　4.3.4 ASCII 编码 27

　　4.3.5 汉字编码 27

　　4.3.6 原码、反码、补码 27

　　4.3.7 位运算 28

　　4.3.8 多媒体文件的数字化 30

　　第5 章 操作系统与应用软件 32

　　5.1 DOS 操作系统 32

　　5.2 Windows 操作系统及软件 34

　　5.3 Linux 操作系统 34

　　第6 章 计算机网络基础 35

　　6.1 计算机网络组成 35

　　6.2 计算机网络类型 37

　　6.3 IP 地址 38

　　6.4 网络安全 39

　　第三部分

　　从图形化编程到C++ 入门

　　第7 章 C++ 基础 42

　　7.1 数据类型 42

　　7.2 语法 46

　　7.2.1 程序入口 46

　　7.2.2 注释 47

　　7.2.3 变量定义及使用 47

　　7.2.4 语句结束符 48

　　7.2.5 语句块与缩进 48

　　7.2.6 作用域 48

　　7.2.7 常量与转义字符 49

　　7.3 运算符 51

　　7.3.1 算术运算符 51

　　7.3.2 关系运算符 53

　　7.3.3 逻辑运算符 53

　　7.3.4 赋值运算符 53

　　7.3.5 三目运算符 54

　　7.4 输入、输出 54

　　7.4.1 输入、输出流 55

　　7.4.2 格式化输入、输出 55

　　7.4.3 文件输入、输出 57

　　第8 章 程序三大基本结构 60

　　8.1 顺序结构 60

　　8.2 分支结构 64

　　8.2.1 if-else 结构 65

　　8.2.2 switch-case 结构 69

　　8.3 循环结构 72

　　8.3.1 for 循环 73

　　8.3.2 while 循环 76

　　8.3.3 do-while 循环 79

　　第9 章 数组 81

　　9.1 一维数组 81

　　9.2 二维数组 88

　　第10 章 自定义函数与指针 95

　　10.1 自定义函数 95

　　10.2 内联函数 96

　　10.3 指针 96

　　10.4 函数的参数传递 97

　　10.4.1 按值传递 97

　　10.4.2 地址传递 99

　　10.4.3 指针传递 100

　　10.5 递归 101

　　10.6 数组传递参数 105

　　10.6.1 一维数组传递参数 105

　　10.6.2 二维数组传递参数 107

　　第11 章 结构体 110

　　11.1 结构体的定义与初始化 110

　　11.2 结构体的调用 111

　　11.3 运算符重载 113

　　第四部分

　　数学知识基础

　　第12 章 数论 118

　　12.1 整除理论（CSP-J） 118

　　12.1.1 定义及性质 118

　　12.1.2 奇数与偶数 119

　　12.2 同余理论（CSP-S） 120

　　12.3 素数（CSP-J/S） 122

　　12.4 最大公约数（CSP-S） 128

　　12.4.1 辗转相除法 128

　　12.4.2 二进制算法 130

　　12.5 最小公倍数（CSP-S） 131

　　12.6 扩展欧几里得法（CSP-S） 133

　　12.7 快速幂算法（CSP-J/S） 135

　　12.8 逆元（CSP-S） 136

　　12.8.1 扩展欧几里得法求逆元 137

　　12.8.2 费马小定理求逆元 138

　　12.8.3 线性算法/ 递归求逆元 140

　　12.9 中国剩余定理（CSP-S） 142

　　12.10 斐波那契数列（CSP-S） 144

　　12.11 卡特兰数（CSP-S） 147

　　第13 章 组合数学 151

　　13.1 排列（CSP-J/S） 151

　　13.1.1 选排列 151

　　13.1.2 全排列 154

　　13.1.3 错位排列 154

　　13.1.4 循环排列 157

　　13.2 组合（CSP-J/S） 157

　　13.2.1 重复组合 158

　　13.2.2 不相邻组合 159

　　13.3 计数原理（CSP-J） 161

　　13.3.1 加法原理（分类加法计数原理） 161

　　13.3.2 乘法原理（分步乘法计数原理） 162

　　13.4 抽屉原理/ 鸽巢原理（CSP-J） 163

　　13.5 容斥原理（CSP-J） 165

　　13.6 母函数（CSP-S） 166

　　13.6.1 普通型母函数 167

　　13.6.2 指数型母函数 172

　　第14 章 概率论（CSP-S） 176

　　14.1 基础知识 176

　　14.1.1 样本空间与随机事件 176

　　14.1.2 事件的概率 179

　　14.2 随机变量 180

　　14.3 期望 182

　　第15 章 计算几何（CSP-S） 185

　　15.1 基础知识 185

　　15.1.1 平面直角坐标系 185

　　15.1.2 点、直线、线段 186

　　15.1.3 圆与多边形 186

　　15.1.4 矢量 188

　　15.2 计算几何C++ 模型 190

　　15.2.1 计算点、点关系 190

　　15.2.2 计算点、线关系 193

　　15.2.3 计算线、线（矢量）关系 198

　　15.2.4 圆与多边形 202

　　15.3 平面凸包 211

　　15.3.1 判断凸多边形 211

　　15.3.2 凸多边形重心 213

　　15.3.3 寻找凸包—Graham算法 216

　　15.4 旋转卡壳 220

　　15.4.1 基础概念 220

　　15.4.2 凸多边形直径 221

　　15.4.3 凸多边形宽度 226

　　15.4.4 凸多边形间最大距离 227

　　15.4.5 凸多边形间最小距离 232

　　15.4.6 凸多边形外接矩形最小面积 238

　　15.4.7 凸多边形外接矩形最小周长 244

　　第16 章 线性代数（CSP-J/S） 245

　　16.1 行列式 245

　　16.2 矩阵 246

　　16.2.1 矩阵的加法 248

　　16.2.2 数与矩阵的乘法 248

　　16.2.3 矩阵与矩阵的乘法 249

　　16.2.4 逆矩阵 249

　　16.2.5 分块矩阵 250

　　16.3 矩阵的初等变换 252

　　16.4 求解线性方程组 253

　　16.4.1 高斯消元法 253

　　16.4.2 LU 分解法 259

　　第17 章 函数（CSP-J/S） 267

　　17.1 定义 267

　　17.2 基本性质 267

　　17.2.1 有界性 267

　　17.2.2 单调性 267

　　17.2.3 奇偶性 268

　　17.2.4 周期性 268

　　17.3 初等函数 268

　　第五部分

　　数据结构

　　第18 章 时间、空间复杂度 274

　　18.1 时间复杂度 274

　　18.1.1 常数阶O(1) 274

　　18.1.2 线性阶O(n) 275

　　18.1.3 对数阶O(log2n) 275

　　18.1.4 线性对数阶O(n log2n) 276

　　18.1.5 幂指数阶O(na) 276

　　18.1.6 时间复杂度曲线对比 276

　　18.2 空间复杂度 277

　　第19 章 STL 简介 278

　　19.1 迭代器 278

　　19.2 容器 279

　　19.2.1 序列容器 279

　　19.2.2 关联容器 287

　　19.3 容器适配器 292

　　19.3.1 queue 适配器 292

　　19.3.2 stack 适配器 294

　　19.3.3 priority_queue适配器 295

　　19.4 算法 297

　　19.4.1 非可变序列算法 298

　　19.4.2 可变序列算法 300

　　19.4.3 排序及相关算法 303

　　19.4.4 数值算法 307

　　第20 章 线性数据结构 310

　　20.1 顺序存储线性表 310

　　20.2 链表 312

　　20.2.1 单链表 312

　　20.2.2 静态链表 318

　　20.2.3 循环链表 318

　　20.2.4 双链表 319

　　20.3 队列 322

　　20.4 栈 329

　　第21 章 树 333

　　21.1 树的一般概念 333

　　21.1.1 结点关系 333

　　21.1.2 度与深度 334

　　21.1.3 树的遍历 335

　　21.2 二叉树 339

　　21.2.1 二叉树性质 340

　　21.2.2 二叉树结构与操作 340

　　21.2.3 遍历二叉树 345

　　21.2.4 二叉排序树 350

　　21.2.5 平衡二叉树 357

　　21.3 树状数组 363

　　21.3.1 前缀和 363

　　21.3.2 树状数组思想 364

　　21.3.3 lowbit 算法 365

　　21.3.4 单点更新 366

　　21.3.5 区间求和 366

　　21.4 线段树 369

　　21.4.1 线段树基本结构 369

　　21.4.2 建立线段树 371

　　21.4.3 单点更新 372

　　21.4.4 区间查询与修改 373

　　21.5 并查集 382

　　21.5.1 基本操作 382

　　21.5.2 算法优化 383

　　21.6 哈夫曼树 387

　　21.6.1 构建哈夫曼树 387

　　21.6.2 哈夫曼树的实现 388

　　21.6.3 哈夫曼编码 391

　　第22 章 图论 392

　　22.1 图的重要概念 392

　　22.2 欧拉路与欧拉回路 393

　　22.3 连通图 401

　　22.3.1 广度优先算法 402

　　22.3.2 强连通图 406

　　22.3.3 割点与桥 411

　　22.4 哈密尔顿图 415

　　22.5 最短路径 420

　　22.5.1 Floyed 算法 422

　　22.5.2 Dijkstra 算法 426

　　22.5.3 Bellman-Ford 算法 431

　　22.5.4 SPFA 算法 433

　　22.6 最小生成树 437

　　22.6.1 Prim 算法 437

　　22.6.2 Kruskal 算法 445

　　22.7 关键路径 449

　　22.7.1 相关概念 450

　　22.7.2 拓扑排序 451

　　22.7.3 关键路径的应用 455

　　第六部分

　　算法补充与归纳

　　第23 章 数学公式补充 464

　　23.1 蔡勒公式 464

　　23.2 归一问题 465

　　23.3 等差数列 465

　　23.4 等比数列 467

　　第24 章 高精度四则运算 468

　　24.1 数字存储 468

　　24.2 高精度加法计算 469

　　24.3 高精度减法计算 472

　　24.4 高精度乘法计算 476

　　24.5 高精度除法计算 478

　　第25 章 字符串算法 484

　　25.1 哈希算法 484

　　25.2 KMP 算法 488

　　25.3 Trie 树 494

　　25.4 Manacher 算法 498

　　25.5 AC 自动机 502

　　第26 章 排序算法 508

　　26.1 冒泡排序算法 508

　　26.2 插入排序算法 510

　　26.3 选择排序算法 512

　　26.4 快速排序算法 513

　　26.5 归并排序算法 516

　　26.6 桶排序算法 519

　　26.7 堆排序算法 521

　　第27 章 搜索算法 522

　　27.1 A* 算法 522

　　27.2 回溯算法 531

　　27.2.1 解空间树 531

　　27.2.2 回溯算法框架 540

　　第28 章 贪心算法 543

　　28.1 区间问题 543

　　28.1.1 最多不相交区间问题 543

　　28.1.2 选点问题 546

　　28.1.3 区间覆盖问题 548

　　28.2 部分背包问题 551

　　28.3 种树问题 553

　　第29 章 分治算法 558

　　29.1 汉诺塔问题 558

　　29.2 二分查找算法 561

　　29.3 主定理 563

　　29.4 Strassen 算法 567

　　29.5 循环赛日程表问题 570

　　第30 章 动态规划算法 574

　　30.1 资源分配问题 575

　　30.2 最长递增/ 递减子序列问题 579

　　30.3 项链问题 582

　　30.4 双线动态规划问题 585

　　第七部分

　　2019—2022 年CSP-JS 真题及参考答案

　　2019 CCF 非专业级别软件能力认证

　　第一轮（CSP-J） 590

　　2019 CCF 非专业级别软件能力认证第一轮

　　（CSP-J）参考答案 600

　　2019 CCF 非专业级别软件能力认证

　　第一轮（CSP-S） 601

　　2019 CCF 非专业级别软件能力认证

　　第一轮（CSP-S）参考答案 613

　　2020 CCF 非专业级别软件能力认证

　　第一轮（CSP-J） 614

　　2020 CCF 非专业级别软件能力认证

　　第一轮（CSP-J）参考答案 625

　　2020 CCF 非专业级别软件能力认证

　　第一轮（CSP-S） 626

　　2020 CCF 非专业级别软件能力认证

　　第一轮（CSP-S）参考答案 640

　　2021 CCF 非专业级别软件能力认证

　　第一轮（CSP-J） 641

　　2021 CCF 非专业级别软件能力认证

　　第一轮（CSP-J）参考答案 653

　　2021 CCF 非专业级别软件能力认证

　　第一轮（CSP-S） 654

　　2021 CCF 非专业级别软件能力认证

　　第一轮（CSP-S）参考答案 670

　　2022 CCF 非专业级别软件能力认证

　　第一轮（CSP-J） 671

　　2022 CCF 非专业级别软件能力认证

　　第一轮（CSP-J）参考答案 683

　　2022 CCF 非专业级别软件能力认证

　　第一轮（CSP-S） 684

　　2022 CCF 非专业级别软件能力认证

　　第一轮（CSP-S）参考答案 697

　　前言/序言

　　由我们编写的《Scratch+ 小学数学》出版后，受到社会各界的关注。在此感谢大家对编程与学科学习融合的支持。曾有家长询问：怎样培养孩子的编程能力？实践证明，图形化编程与小学数学的融合能够在很大程度上提升学生学习数学的兴趣，同时也可锻炼学生的逻辑思维能力。

　　“为人父母者，则为其计深远”，通过小学阶段图形化编程与小学数学的融合学习，学生可以在一定程度上建立基本的编程思维和提高逻辑思维能力。如果希望在更深程度上学习，并在升学考试中有所突破，那么怎样才能通过图形化编程向代码编程甚至信息学奥赛方面过渡呢？本书的知识体系将为您的学习提供参考。

　　本书的基本内容包括30 章，分7 个部分，前6 个部分知识体系架构包括编程平台介绍、

　　计算机基础知识、从图形化编程到C++ 入门、数学知识基础、数据结构和算法补充与归纳。

　　编程平台介绍主要包括图形化编程模块和C++ 编辑调试Dev-C++ 平台的介绍，读者可以初步了解图形化编程模块与C++ 代码编程的联系与区别。通过这部分的学习，读者可以了解代码编程中将来可能面对的界面与问题。

　　计算机基础知识是信息学奥赛初赛的考查内容，需要了解计算机的基本原理、信息学奥赛的基本常识、操作系统的基本知识及计算机网络的相关知识。作为计算机基础知识，也是读者更加深入学习信息学奥赛的基础，同时也是了解计算机这门学科机制的基础。

　　从图形化编程到C++ 入门部分能够使读者很好地从原有的图形化模块编程思维转向C++ 代码编程思维，由于前期很多读者有了《Scratch+ 小学数学》的学习经验，那么这部分将是进入信息学奥赛C++ 编程的重要阶梯。

　　数学基础知识部分紧接在由图形化编程向C++ 编程过渡之后，是因为参加信息学奥赛要取得更好的成绩，必须将数学知识的学习放在比较重要的位置，数学知识实质上是计算机知识的基础，同时，掌握更多的数学知识及数学原理可以帮助读者更好地解决信息学奥赛和现实中的问题。

　　数据结构是学习计算机知识的重要组成部分，也是计算机专业学习的必修课，通过抽象的数据结构可以帮助我们将现实问题抽象成一种具有可行性的问题解决结构，与此同时，数据结构也为我们解决问题提供了另一种思路。读者在初步学习的时候可能会有所困惑，这些都是正常现象，通过本部分的知识与案例学习将加深读者对数据结构的理解。

　　算法补充与归纳是在前面5 个部分学习的基础上，对没有涉及的算法进行补充，同时也将各种经典算法进行归纳。当然，在这部分并不能全部囊括所有经典案例，但本书中所涉及的案例都可以揭示相关算法的内在核心思想。

　　在学习编程方法上，没有捷径可走，但有方法可循。

　　信息学奥赛初赛以笔试为主，笔试所涉及的知识面非常广泛，需要长期学习积累，当然本书可为读者提供提纲作用。

　　本书在每一章节中都没有包含练习模块，其原因有两个：一是初赛利用真题可以很好地了解出题者思路，在本书的第七部分初赛真题中，为读者提供了2019—2022 年CSP-J/S 真题及参考答案，可供读者练习使用；二是复赛的上机练习，由于我们采用的练习平台是Dev-C++ 软件平台，而考试系统是通过黑盒测试的方式来检测程序的正确与否的，所以若想针对复赛的程序进行上机练习，读者可以通过访问http://www.xajoj.cn/index.php 进行相关题库和知识点的练习，并通过程序反馈判断程序是否正确。

　　本书的成书参考了各位网友的博客分享及案例展示，其中有TINGHAIK、大学要有梦想的博客、Alex_McAvoy、我是8 位的、Rosun_、zolalad、不止思考( 奎哥)、云水、zhipingChen、御心飞行、Ucsasuke、九日王朝、知行执行等，同时，由于部分内容在网络中无法追源，不能一一详述，在此一并感谢各位网友的分享。最后感谢张龙梅老师在本书校稿时所做的贡献。

　　最后，感谢社会各界对编程的支持与厚爱，希望编程学习为读者的生活与学习开辟一片新的天地。由于作者水平有限，难免有疏漏和不妥之处，在此诚挚欢迎读者提出意见和建议。