信息学奥赛导学

\\\"本书是为了帮助考生全面备战信息学奥赛初赛而精心编写的。全书共三部分 7章，第一部分包括第 1~5章，是信息学奥赛初赛考核的知识点讲解及专题练习；第二部分为第 6章，包括 CSP-J和 CSP-S两个级别的模拟卷、答案及思路解析；第三部分为第 7章，包含近几年信息学奥赛初赛真题、答案及思路解析。本书旨在引导考生从基础知识学习出发，经过模拟题的实战演练，直至深入掌握真题考点，系统地逐步提升自己在竞赛中的实力。 本书是一本针对性强、实用性高的信息学奥赛初赛辅导书，适合准备参加信息学奥赛初赛或有一定基础的考生学习使用，也适合教师教学参考使用。\\\"

马强，2007年开始从事信息学奥赛教学工作，具有多年教学、教研经验。曾就职于北京市十一学校、中国人民大学附属中学朝阳学校、首都师范大学附属中学，现就职于北京童程童美科技有限公司，担任信息学教研总负责人。辅导近百名学生获得NOI金、银、铜牌及省一等奖。参与设计中国计算机学会主办的GESP考试大纲，并多次面向全国考生进行真题讲解。

第 1章　计算机的基础知识 1.1 　计算机的发展历程 ............................2 1.1.1 　基础知识介绍.............................. 2 1.1.2 　专题练习...................................... 2 1.2 　关于计算机的著名人物及成就 ........3 1.2.1 　计算机相关科学家介绍.............. 3 1.2.2 　专题练习...................................... 4 1.3 　计算机类常见奖项 ............................5 1.3.1 　基础奖项知识介绍...................... 5 1.3.2 　拓展知识：其他奖项.................. 6 1.3.3 　专题练习...................................... 7 1.4 计算机的应用方向 ............................7 基础知识介绍.......................................... 7 1.5 计算机的基本结构 ............................8 1.5.1 计算机的组成.............................. 8 1.5.2 计算机的硬件系统...................... 9 1.5.3 计算机的软件系统.................... 14 1.5.4 专题练习.................................... 16 1.6 　计算机网络 ......................................16 1.6.1 　计算机网络的基本概念............ 16 1.6.2 　计算机网络的主要功能............ 17 1.6.3 　计算机网络的分类.................... 17 1.6.4 　网络体系结构............................ 20 1.6.5 　IP地址与域名 ........................... 22 1.6.6 　专题练习.................................... 24 1.7 　计算机安全 ......................................25 1.7.1 　自然环境的防护........................ 25 1.7.2 　计算机病毒................................ 25 1.7.3 　防火墙........................................ 26 1.7.4 　专题练习.................................... 26 1.8 　原码、补码和反码 ..........................27 1.8.1 　机器数........................................ 27 1.8.2 　真值............................................ 27 1.8.3 　原码、反码和补码.................... 28 1.8.4 　专题练习.................................... 29 1.9 　数制转换与编码 ..............................29 1.9.1 　进制转换.................................... 30 1.9.2 　二进制转十进制 ....................... 30 1.9.3 　十进制整数转二进制 ............... 30 1.9.4 　十进制小数转二进制................ 31 1.9.5 　八进制与二进制的相互转换 ... 31 1.9.6 十六进制与二进制的相互转换... 32 1.9.7 专题练习.................................... 32 1.10 计算机的存储 ................................33 1.10.1 计算机的存储单位.................. 33 1.10.2 关于图像大小的计算.............. 34 1.10.3 关于视频容量的计算.............. 34 -VII - 1.10.4 专题练习.................................. 35 1.11　综合练习.........................................35 第 2章　C ++基础知识 2.1 基本概念 ..........................................37 2.1.1　常量............................................ 37 2.1.2　变量............................................ 37 2.1.3　基本数据类型............................ 38 2.1.4　编辑、编译、调试.................... 38 2.1.5　逗号表达式................................ 39 2.1.6　专题练习.................................... 39 2.2　常见函数 ..........................................40 2.2.1　输入函数（scanf）..................... 40 2.2.2　输出函数（printf）..................... 41 2.2.3　绝对值函数（abs）..................... 42 2.2.4　平方根函数（sqrt）.................... 42 2.2.5　专题练习.................................... 43 2.3　数组 ..................................................43 2.3.1　数组基础知识............................ 44 2.3.2　字符数组.................................... 44 string........................................... 45 2.3.3 2.3.4　二维数组.................................... 48 2.3.5　指针............................................ 49 2.3.6　专题练习.................................... 51 2.4　结构体和联合体 ..............................52 2.4.1　结构体........................................ 52 2.4.2　联合体........................................ 53 2.4.3　专题练习.................................... 54 第 3章　数据结构 3.1　基础知识 ..........................................56 3.2　链表 ..................................................57 3.2.1　链表的定义................................ 57 3.2.2　单向链表.................................... 58 3.2.3　双向链表.................................... 62 3.2.4　循环链表.................................... 63 3.2.5　专题练习.................................... 63 3.3　栈 ......................................................64 3.3.1　栈的定义.................................... 64 3.3.2　栈的基本操作............................ 65 3.3.3　出栈序列.................................... 66 3.3.4　专题练习.................................... 67 3.4　队列 ..................................................68 3.4.1　队列的定义................................ 68 3.4.2　队列的基本操作........................ 69 3.4.3　循环队列.................................... 70 3.4.4　专题练习.................................... 72 3.5　树和二叉树 ......................................73 3.5.1　树................................................ 73 3.5.2　二叉树........................................ 77 3.5.3　二叉树的三个主要性质............ 78 3.5.4　二叉树的两种特殊形态............ 79 3.5.5　二叉树的遍历............................ 81 3.5.6　序列构造二叉树........................ 83 3.5.7　表达式........................................ 84 3.5.8　树和二叉树以及森林的转换.... 85 3.5.9　哈夫曼树和哈夫曼编码............ 88 3.5.10　二叉排序树.............................. 91 3.5.11　专题练习 .................................. 92 3.6　图论基础 ..........................................92 3.6.1　欧拉与图论................................ 92 3.6.2　图论的基本概念........................ 93 3.6.3　图的存储.................................... 96 3.6.4　欧拉路径和欧拉回路................ 97 3.6.5　哈密顿回路................................ 98 3.6.6　图的搜索.................................... 99 3.7　专题练习 ..........................................99 第 4章　算法 4.1 基本概念 ........................................102 4.1.1　算法.......................................... 102 4.1.2　专题练习.................................. 102 目.录 4.2 　枚举算法 ........................................104 4.9　排序算法 ........................................127 4.2.1 　枚举算法.................................. 104 4.9.1　常见排序算法.......................... 127 4.2.2 　专题练习.................................. 106 4.9.2　各种排序算法的比较.............. 130 4.3 　模拟算法 ........................................107 4.9.3　专题练习.................................. 131 4.3.1 　模拟算法.................................. 107 4.10　深度优先搜索算法 ......................133 4.3.2 　专题练习.................................. 108 4.10.1　深度优先搜索算法................ 133 4.4 　贪心算法 ........................................109 4.10.2　专题练习................................ 134 4.4.1 　贪心算法.................................. 109 4.11　广度优先搜索算法.......................134 4.4.2 　专题练习...................................110 4.11.1　广度优先搜索算法 ................ 134 4.5 　递推算法 ........................................ 112 4.11.2　专题练习 ................................ 136 4.5.1 　递推算法...................................112 4.12　动态规划 ......................................138 4.5.2 　专题练习...................................114 4.12.1　动态规划................................ 138 4.6 　递归算法 ........................................ 115 4.12.2　常见动态规划类型................ 139 4.6.1 　递归算法...................................115 4.12.3　专题练习................................ 140 4.6.2 　专题练习...................................118 第 5章　数学知识 4.7 　二分算法 ........................................121 4.7.1 　二分算法.................................. 121 5.1 素数筛法 ........................................143 4.7.2 　专题练习.................................. 122 5.1.1　埃拉托色尼筛法...................... 143 4.8 　倍增算法 ........................................124 5.1.2　线性筛法.................................. 144 4.8.1 　倍增算法.................................. 124 5.2　排列组合相关知识 ........................145 4.8.2 　专题练习.................................. 125 5.2.1　基础概念.................................. 145 5.2.2　专题训练.................................. 149 第二部分.CSP-J模拟卷、CSP -S模拟卷、答案及思路解析 CSP-J模拟卷（一）........................................ 152 CSP-J模拟卷（一）答案及思路解析.......... 228 CSP-J模拟卷（二）........................................ 159 CSP-J模拟卷（二）答案及思路解析.......... 232 CSP-J模拟卷（三）........................................ 167 CSP-J模拟卷（三）答案及思路解析.......... 235 CSP-J模拟卷（四）........................................ 174 CSP-J模拟卷（四）答案及思路解析.......... 239 CSP-S模拟卷（一）....................................... 183 CSP-S模拟卷（一）答案及思路解析......... 243 CSP-S模拟卷（二）....................................... 194 CSP-S模拟卷（二）答案及思路解析......... 246 CSP-S模拟卷（三）....................................... 204 CSP-S模拟卷（三）答案及思路解析......... 249 CSP-S模拟卷（四）....................................... 216 CSP-S模拟卷（四）答案及思路解析......... 252 2024 CSP-J CCF 非专业级别软件能力认证第一轮............................................................. 256 2023 CSP-J CCF 非专业级别软件能力认证第一轮............................................................. 263 2022 CSP-J CCF 非专业级别软件能力认证第一轮............................................................. 271 2021 CSP-J CCF 非专业级别软件能力认证第一轮............................................................. 280 2020 CSP-J CCF 非专业级别软件能力认证第一轮............................................................. 290 2019 CSP-J CCF 非专业级别软件能力认证第一轮............................................................. 299 2024 CSP-S CCF 非专业级别软件能力认证第一轮............................................................. 307 2023 CSP-S CCF 非专业级别软件能力认证第一轮............................................................. 319 2022 CSP-S CCF 非专业级别软件能力认证第一轮............................................................. 329 2021 CSP-S CCF 非专业级别软件能力认证第一轮............................................................. 339 2024 CSP-J CCF 非专业级别软件能力认证第一轮答案及思路解析................................. 353 2023 CSP-J CCF 非专业级别软件能力认证第一轮答案及思路解析................................. 356 2022 CSP-J CCF 非专业级别软件能力认证第一轮答案及思路解析................................. 360 2021 CSP-J CCF 非专业级别软件能力认证第一轮答案及思路解析................................. 363 2020 CSP-J CCF 非专业级别软件能力认证第一轮答案及思路解析................................. 366 2019 CSP-J CCF 非专业级别软件能力认证第一轮答案及思路解析................................. 369 2024 CSP-S CCF 非专业级别软件能力认证第一轮答案及思路解析................................. 372 2023 CSP-S CCF 非专业级别软件能力认证第一轮答案及思路解析................................. 376 2022 CSP-S CCF 非专业级别软件能力认证第一轮答案及思路解析................................. 379 2021 CSP-S CCF 非专业级别软件能力认证第一轮答案及思路解析................................. 382