CCF 信息学奥赛基础篇

本书由中国计算机学会组编，适合NOI参赛师生/信息学爱好者/程序设计竞赛爱好者。
本书特色：
关注学习过程，强调反思意识解决，
引导主动探究，建构知识体系。

本书是“CCF全国青少年信息学奥林匹克竞赛教程”丛书的第二册，旨在普及计算机科学与程序设计知识。书中遵循由浅入深、逻辑严密的编写思路，辅以丰富的实例解析，引领读者逐步提升计算思维能力。全书共四章，涉及C++程序设计进阶、数据结构及其应用、算法设计、数学运用等内容，全面覆盖NOI竞赛大纲所要求的基础知识。根据竞赛的特点，书中还对一些常见的难点和易错点进行了深入的解析。
本书可作为信息学奥林匹克竞赛的教学用书，也可作为青少年学习计算机科学知识、了解信息学奥赛的参考资料。

丛书序<br />前言第一章　C++程序设计进阶第一节　二维数组3一、情境导航3<br />二、问题抽象3<br />三、知识探究4<br />（一） 二维数组的定义4<br />（二） 二维数组的输入、输出4<br />（三） 贪吃蛇问题5<br />四、实践应用6<br />五、总结提升9第二节　多维数组11一、情境导航11<br />二、问题抽象12<br />三、知识探究12<br />（一） 三维数组的定义12<br />（二） 三维数组的输入、输出13<br />（三） 统计石头问题13<br />四、实践应用15<br />五、总结提升19第三节　常用数学函数23一、情境导航23<br />二、问题抽象23<br />三、知识探究24<br />（一） 绝对值函数24<br />（二） 四舍五入函数24<br />（三） 取下整函数（地板函数）25<br />（四） 取上整函数（天花板函数）26<br />（五） 平方根函数26<br />（六） 常用三角函数27<br />（七） 对数函数27<br />（八） 幂函数28<br />四、实践应用29<br />五、总结提升31第四节　自定义函数的参数33一、情境导航33<br />二、问题抽象33<br />三、知识探究34<br />（一） 形参和实参34<br />（二） 参数的传递方式34<br />四、实践应用36<br />五、总结提升38第五节　结构体与联合体42一、情境导航42<br />二、问题抽象43<br />三、知识探究44<br />（一） 结构体的引入44<br />（二） 结构体的定义44<br />（三） 创建结构体变量45<br />（四） 访问结构体变量的成员45<br />（五） 初始化结构体变量的成员45<br />（六） 结构体数组46<br />（七） 结构体作为函数参数46<br />（八） 图书馆里的寻书游戏46<br />四、实践应用48<br />五、总结提升51第六节　指针类型60一、情境导航60<br />二、问题抽象60<br />三、知识探究61<br />（一） 什么是指针61<br />（二） 如何声明指针61<br />（三） 指针的初始化62<br />（四） 使用指针62<br />（五） 指针和函数63<br />（六） 指针的算术运算63<br />（七） 指针与数组63<br />（八） 动态分配内存64<br />四、实践应用66<br />五、总结提升68第七节　STL（标准模板库）——算法函数72一、情境导航72<br />二、问题抽象72<br />三、知识探究73<br />（一） 什么是STL73<br />（二） 算法函数max、min、swap73<br />（三） 算法函数sort75<br />四、实践应用77<br />五、总结提升80第八节　STL（标准模板库）——线性容器85一、情境导航85<br />二、问题抽象86<br />三、知识探究87<br />（一） STL的线性容器87<br />（二） STL的向量(vector)87<br />（三） 向量的成员函数89<br />（四） STL的链表（list）90<br />（五） STL的队列（queue）92<br />（六） STL的栈（stack）93<br />（七） 线性容器相关函数总结95<br />四、实践应用96<br />五、总结提升98第二章　数据结构及其运用第一节　线性结构——链表103一、情境导航103<br />二、问题抽象103<br />三、知识探究104<br />（一） 链表的基本概念104<br />（二） 链表的分类104<br />（三） 链表的操作105<br />（四） 链表操作的STL list实现105<br />（五） 链表操作的数组模拟实现106<br />（六） 双向链表操作的数组模拟实现109<br />（七） 循环链表操作的数组模拟实现111<br />（八） 为什么学习链表操作的数组模拟实现112<br />四、实践应用112<br />五、总结提升116第二节　线性结构——队列和栈116一、情境导航116<br />二、问题抽象117<br />三、知识探究117<br />（一） 什么是队列117<br />（二） 队列的基本操作117<br />（三） 队列操作的STL queue实现118<br />（四） 队列操作的数组实现119<br />（五） 与队列类似的栈121<br />（六） 栈的基本操作121<br />（七） 栈操作的STL stack实现121<br />（八） 栈操作的数组实现122<br />四、实践应用124<br />五、总结提升130第三节　树的引入133一、情境导航133<br />二、问题抽象134<br />三、知识探究134<br />（一） 什么是树134<br />（二） 树的表示与存储135<br />（三） 树的基本操作136<br />四、实践应用137<br />五、总结提升139第四节　二叉树141一、情境导航141<br />二、问题抽象142<br />三、知识探究142<br />（一） 什么是二叉树142<br />（二） 二叉树的性质143<br />（三） 二叉树的表示与存储143<br />（四） 二叉树的基本操作144<br />四、实践应用144<br />五、总结提升146第五节　二叉搜索树150一、情境导航150<br />二、问题抽象151<br />三、知识探究151<br />（一） 什么是二叉搜索树151<br />（二） 二叉搜索树的插入操作152<br />（三） 二叉搜索树的查找操作153<br />（四） 二叉搜索树的遍历操作154<br />四、实践应用155<br />五、总结提升157第六节　哈夫曼树160一、情境导航160<br />二、问题抽象160<br />三、知识探究161<br />（一） 什么是哈夫曼树161<br />（二） 构建哈夫曼树161<br />（三） 哈夫曼树的性质162<br />（四） 哈夫曼编码162<br />（五） 哈夫曼编码的实现163<br />四、实践应用166<br />五、总结提升169第七节　完全二叉树170一、情境导航170<br />二、问题抽象170<br />三、知识探究171<br />（一） 什么是完全二叉树171<br />（二） 完全二叉树的平衡性质171<br />（三） 完全二叉树的数组实现171<br />（四） 什么是堆173<br />（五） 堆的操作173<br />四、实践应用175<br />五、总结提升177第八节　图的定义和存储181一、情境导航181<br />二、问题抽象182<br />三、知识探究183<br />（一） 什么是图183<br />（二） 图的性质183<br />（三） 什么是图的邻接矩阵184<br />（四） 图的邻接矩阵的实现185<br />（五） 图的邻接矩阵的优缺点186<br />（六） 图的邻接链表186<br />（七） 图的邻接链表的实现187<br />（八） 图的邻接链表的优缺点188<br />四、实践应用188<br />五、总结提升190第三章　算法设计第一节　算法基础195一、算法概述195<br />（一） 算法的定义195<br />（二） 算法的特性195<br />二、算法的描述195<br />（一） 自然语言描述195<br />（二） 流程图描述196<br />（三） 伪代码描述197<br />（四） 三种描述方式的比较197第二节　基础算法1——贪心法198一、情境导航198<br />二、问题抽象198<br />三、知识探究199<br />（一） 贪心法的定义与原理199<br />（二） 贪心法的适用场景199<br />（三） 分发饼干问题199<br />四、实践应用201<br />五、总结提升206第三节　基础算法2——递推法208一、情境导航208<br />二、问题抽象209<br />三、知识探究209<br />（一） 递推法的基本步骤209<br />（二） 递推法的适用场景210<br />四、实践应用210<br />五、总结提升213第四节　基础算法3——递归法214一、情境导航214<br />二、问题抽象215<br />三、知识探究216<br />（一） 什么是递归法216<br />（二） 斐波那契数列的递归法描述216<br />（三） 递归法的优点216<br />四、实践应用217<br />五、总结提升221第五节　基础算法4——二分法222一、情境导航222<br />二、问题抽象223<br />三、知识探究223<br />（一） 二分法原理223<br />（二） 二分法的基本步骤223<br />四、实践应用225<br />五、总结提升229第六节　基础算法5——倍增法233一、情境导航233<br />二、问题抽象233<br />三、知识探究234<br />四、实践应用236<br />五、总结提升238第七节　基础算法6——前缀和245一、情境导航245<br />二、问题抽象245<br />三、知识探究245<br />（一） 前缀和的定义与优势245<br />（二） 前缀和的适用场景246<br />（三） 用前缀和解决仓库统计问题246<br />四、实践应用248<br />五、总结提升250<br />（一） 注意事项250<br />（二） 算法复杂度250<br />（三） 前缀和的优缺点250第八节　数值处理算法256一、情境导航256<br />二、问题抽象257<br />三、知识探究257<br />（一） 高精度加法257<br />（二） 高精度减法259<br />（三） 高精度乘法262<br />四、实践应用264<br />五、总结提升265第九节　排序算法269一、情境导航269<br />二、问题抽象270<br />三、知识探究271<br />（一） 冒泡排序271<br />（二） 选择排序273<br />（三） 插入排序275<br />四、实践应用276<br />五、总结提升278第十节　搜索算法281一、情境导航281<br />二、问题抽象282<br />三、知识探究282<br />（一） 深度优先搜索282<br />（二） 广度优先搜索287<br />四、实践应用290<br />五、总结提升292第十一节　图论算法298一、情境导航298<br />二、问题抽象299<br />三、知识探究299<br />（一） 图的深度优先搜索299<br />（二） 图的广度优先搜索303<br />四、实践应用305<br />五、总结提升308第十二节　动态规划1——简单一维动态规划312一、情境导航312<br />二、问题抽象312<br />三、知识探究313<br />（一） 动态规划概述315<br />（二） 动态规划的原理315<br />四、实践应用317<br />五、总结提升320第十三节　动态规划2——简单背包类型动态规划321一、情境导航321<br />二、问题抽象322<br />三、知识探究329<br />四、实践应用331<br />五、总结提升334ⅩⅦⅩⅧ第十四节　动态规划3——简单区间类型动态规划335一、情境导航335<br />二、问题抽象336<br />三、知识探究337<br />四、实践应用340<br />五、总结提升344第四章　数学运用第一节　初等数论351一、情境导航351<br />二、问题抽象351<br />三、知识探究352<br />（一） 整除352<br />（二） 因数（因子）352<br />（三） 倍数352<br />（四） 指数352<br />（五） 质数与合数352<br />（六） 整数唯一分解定理352<br />四、实践应用357<br />五、总结提升363第二节　组合数学368一、情境导航368<br />二、问题抽象369<br />三、知识探究369<br />（一） 加法原理与乘法原理369<br />（二） 排列与组合370<br />四、实践应用371<br />五、总结提升374<br /><br />附录　本书内容与NOI竞赛大纲的对应关系379