信息学奥赛一本通关

图书标准信息

• 作者 蔡荣啸
• 出版社 清华大学出版社
• 出版时间 2023-01
• 版次 1
• ISBN 9787302607281
• 定价 128.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸
• 页数 708页
• 字数 779千字

【内容简介】

《信息学奥赛一本通关》共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