信息学奥赛高分训练秘笈（基础篇）

全国青少年信息学奥林匹克联赛(以下简称NOIP)是每年众多信息学竞赛中最权威的比赛，NOIP是同一时间在全国各个省份同时开展的比赛。只有在省赛中表现十分突出的NOIP选手才有机会代表其所在省份参加全国青少年信息学奥林匹克竞赛(NOI)，在NOI中表现极其优秀的选手，还有机会代表国家参加国际信息学奥林匹克竞赛(IOI)，为国争光。

省级联赛分普及组(NOIPJ或CSPJ)和提高组(NOIPS或CSPS)，两个组别都有初赛和复赛两个阶段，只有在初赛中成绩优异的学生才有资格参加复赛。为了能够为广大信息学爱好者提供帮助，普及信息学知识，提高信息学竞赛技能和水平，编写组组织了浙江省内一批有丰富信息学竞赛及ACM国际大学生程序设计竞赛指导经验的金牌教练、教练员编写了这套《信息学奥赛高分秘笈》辅导资料，期望能为广大读者提供切实有效的帮助。

各学科的奥赛一般都是针对学有余力的同学，会有一定的深度及难度，许多知识体系已超越中学阶段的知识体系范畴。《信息学奥赛高分秘笈》以NOIP相关知识点及算法设计技巧为切入点，以NOIP历年竞赛题例为抓手，按竞赛形式(初/复赛篇)组织辅导资料的结构。全书紧扣竞赛相关知识体系，同时兼顾对大学阶段学习的引导作用来组织本书内容。全套辅导材料分基础篇、算法篇和实战篇三册，以渐进式方式引导学生分阶段学习。读者可根据基础篇的学习情况来判断自己是否真有兴趣并适合参加该竞赛。另一方面，即便暂时搁置后再继续学习该内容，前期所学知识也有助于大学阶段学习的。本分册为《信息学奥赛高分秘笈》（基础篇），主要包括计算机基础、C/C  程序设计基础、数学基础、数据结构基础、算法设计基础等内容。本书第1、2章由浙江科技学院孙奕鸣老师、杭州科技职业技术学院陆亚文老师编写，第3章由浙江传媒学院王鸣老师和浙江广厦建设职业技术大学瞿有甜老师编写，第4章由宁波市鄞州中学金波老师编写，第5章由瞿有甜老师编写，第6章由余姚中学诸一行老师编写。

本书部分资料来源于网络或曾经的信息学竞赛大咖的个人博客、解题报告等，由于时间跨度较长，有些资料难以找到原创作者，在此向这些作者表示衷心的感谢。尽管编者希望努力做到最好，但限于时间仓促及作者的水平等因素，书中不足之处在所难免，恳请读者批评指正。

编者
2024年1月

本书是NOIP算法竞赛的入门教材，重点介绍算法设计竞赛的相关知识体系，将C/C  语言、算法和解题有机地结合在一起，注重理论与实践相结合，着重培养学生的计算思维能力。

本书内容涵盖了NOIP竞赛普及组和提高组所需掌握的绝大部分知识点、常见的算法分析设计及实现技巧和方法，主要内容包括计算机的基础知识，算法描述、设计工具，C/C  程序设计语言，数据结构及其相关基础算法，算法设计技术基础，数论、概率论及组合数学基础等。本书以历年相关竞赛常见考试题型及题例作为例题解析和习题。书中的绝大部分代码规范、简洁、易懂，不仅能帮助读者理解信息技术中的算法原理，在掌握各类经典算法的同时还能学会很多实用的编程技巧，提高分析解决实际问题的能力。

本书可作为全国青少年信息学奥林匹克联赛(NOIP)初/复赛、全国青少年信息学奥林匹克竞赛(NOI)的教材和指导用书，也可作为有意参加ACM国际大学生程序设计竞赛及相关同类算法竞赛的读者的教材和参考用书。

下载源码

第1章概述

1.1全国青少年信息学奥赛概述

1.2CCF非专业级软件能力认证考试概述

1.3全国青少年信息学奥赛考试大纲

练习题

第2章计算机基础

2.1计算机的发展史

2.2计算机系统的组成

2.2.1冯·诺依曼体系结构

2.2.2计算机系统架构与工作原理

2.2.3范例分析

2.3数制的概念及相互转换

2.3.1数制的术语

2.3.2常用的记数制

2.3.3数制间的相互转换

2.3.4范例分析

2.4数的编码表示

2.4.1整数的表示

2.4.2实数的表示

2.4.3ASCII英文编码

2.4.4GB2312汉字编码

2.4.5范例分析

2.5多媒体技术

2.5.1多媒体的基本概念

2.5.2多媒体数据压缩

2.5.3图形与图像

2.5.4动态图形

2.5.5数字化音频

2.5.6多媒体创作

2.5.7图像与视频的编码

2.5.8范例分析

2.6计算机网络

2.6.1网络发展概述

2.6.2网络的基本概念

2.6.3网络的分类、组成与功能

2.6.4网络的标准和协议

2.6.5网络操作系统

2.6.6局域网和广域网

2.6.7Internet基础

2.6.8网络安全性概述

2.6.9范例分析

2.7信息技术的新名词、新概念、新应用

2.7.1Web 2.0和博客、微博

2.7.2J2SE/J2EE

2.7.3.NET平台

2.7.4Web Service

2.7.5数据仓库

2.7.6数据挖掘

2.7.7XML

2.7.8UML

2.7.9P2P

2.7.10AOP

2.7.11网格计算与普适计算

2.7.12云计算与SaaS

2.7.13多核技术

2.7.14大数据

2.7.15人工智能

2.7.16范例分析

2.8逻辑运算

练习题

第3章C  程序设计基础

3.1C  程序设计语言概述

3.1.1程序设计语言的发展历程

3.1.2C  语言程序的组成结构

3.1.3C  语言的编译环境

3.1.4算法和算法描述

3.2顺序结构程序设计

3.2.1赋值语句

3.2.2运算符与表达式

3.2.3常量和变量

3.2.4标准数据类型

3.2.5数据的输入输出

3.2.6C  流操纵算子

3.2.7顺序结构程序设计实例

练习题

3.3分支结构程序设计

3.3.1if语句

3.3.2switch语句

3.3.3分支结构程序设计实例

练习题

3.4循环结构程序设计

3.4.1for语句

3.4.2while与do/while语句

3.4.3循环的嵌套

3.4.4break语句和continue语句

3.4.5循环结构中应用位运算

3.4.6循环结构程序设计实例

练习题

3.5数组

3.5.1一维数组

3.5.2二维数组

3.5.3数组综合应用程序设计实例

3.5.4字符数组

练习题

3.6字符串

3.6.1字符串处理——string类型

3.6.2字符串的输入输出

3.6.3string类型的基本操作

3.6.4string类型的应用

3.6.5字符串函数

3.6.6字符串综合应用程序设计实例

练习题

3.7模块化编程——函数

3.7.1自定义函数的定义

3.7.2函数的声明和调用

3.7.3全局变量和局部变量

3.7.4函数的综合应用

练习题

3.8指针及其应用

3.8.1指针变量的定义

3.8.2指针运算

3.8.3指针与数组

3.8.4指针与函数

3.8.5指针与字符串

3.8.6堆内存管理

3.8.7指向结构体变量的指针

3.8.8指向结构体数组的指针

3.8.9指针类型综合应用程序设计实例

3.8.10指针小结

练习题

3.9结构体

3.9.1结构体的定义

3.9.2结构体变量

3.9.3结构体数组

3.9.4结构体的扩展

3.9.5链表结构

3.9.6双向链表

3.9.7循环链表

3.9.8结构体综合应用程序设计实例

练习题

3.10文件

3.10.1文件类型变量的定义和引用

3.10.2stream类的流文件的操作

3.10.3文件指针FILE的操作

3.10.4文件的重定向

3.10.5文件应用实例

练习题

3.11标准模板库的简要说明

3.11.1STL中的一些新概念

3.11.2几个常见的容器介绍

3.11.3几个常见的算法函数

练习题

第4章数学基础

4.1数论基础

4.1.1整除

4.1.2质数

4.1.3同余

4.1.4快速幂

4.1.5矩阵

4.1.6斐波那契数列

4.1.7最大公约数

4.1.8求线性同余方程

4.1.9乘法逆元

4.1.10Lucas定理

4.1.11中国剩余定理

4.1.12exLucas定理

练习题

4.2组合数学基础

4.2.1计数原理

4.2.2排列及组合

4.2.3康托展开

4.2.4逆康托展开

4.2.5斯特林数

4.2.6卡特兰数

练习题

4.3概率论基础

4.3.1事件与概率

4.3.2古典概率

4.3.3数学期望

4.3.4随机算法

练习题

第5章数据结构基础

5.1算法分析

5.1.1时间复杂度

5.1.2空间复杂度

5.1.3NP问题

5.1.4范例分析

5.2数据的存储结构

5.2.1数组

5.2.2链表

5.2.3范例分析

5.3散列表

5.3.1散列函数

5.3.2散列表冲突处理办法

5.3.3范例分析

5.4栈

5.4.1栈的定义

5.4.2栈与递归

5.4.3栈与DFS

5.4.4范例分析

5.5队列

5.5.1队列的定义

5.5.2循环队列

5.5.3队列与BFS

5.5.4范例分析

5.6树及其遍历

5.6.1树的定义

5.6.2树的概念

5.6.3树的遍历

5.6.4范例分析

5.7二叉树及其遍历

5.7.1二叉树的五个基本性质

5.7.2二叉树的存储结构

5.7.3二叉树遍历

5.7.4范例分析

5.8树状排序

5.8.1二叉排序树

5.8.2堆

5.8.3树状选择排序

5.8.4范例分析

5.9二叉树应用

5.9.1表达式树

5.9.2哈夫曼树的基本概念

5.9.3哈夫曼树的构造算法

5.9.4哈夫曼编码

5.9.5范例分析

5.10图及其存储表示

5.10.1图的定义

5.10.2图的相关术语

5.10.3图的存储表示

5.10.4范例分析

5.11图的遍历和连通性

5.11.1深度优先搜索

5.11.2广度优先搜索

5.11.3欧拉路径与欧拉回路

5.11.4二分图

5.11.5图的连通性

5.11.6范例分析

5.12图论算法

5.12.1单源最短路径问题

5.12.2Dijkstra算法

5.12.3生成树问题

5.12.4范例分析

5.13拓扑排序与关键路径

5.13.1AOV网与拓扑排序

5.13.2AOE网与关键路径

5.13.3范例分析

5.14排序

5.14.1基于顺序比较的简单排序

5.14.2基于分治策略的排序

5.14.3希尔排序

5.14.4线性排序

5.14.5各种排序算法的比较

5.14.6范例分析

练习题

第6章算法设计基础

6.1递推算法

6.1.1递推策略思想

6.1.2范例分析

6.2递归算法

6.2.1递归的概念

6.2.2递归算法设计

6.2.3范例分析

6.3枚举算法

6.3.1枚举算法的概念

6.3.2范例分析

6.4贪心算法

6.4.1贪心算法的定义

6.4.2贪心算法的特点

6.4.3范例分析

6.5动态规划

6.5.1动态规划的简介

6.5.2动态规划算法的具体实现

6.5.3动态规划解题的常用技巧

练习题

参考文献

本书是NOIP算法竞赛的入门教材，重点介绍算法设计竞赛的相关知识体系，将C/C  语言、算法和解题有机地结合在一起，注重理论与实践相结合，着重培养学生的计算思维能力。

本书内容涵盖了NOIP竞赛普及组和提高组所需掌握的绝大部分知识点、常见的算法分析设计及实现技巧和方法，主要内容包括计算机的基础知识，算法描述、设计工具，C/C  程序设计语言，数据结构及其相关基础算法，算法设计技术基础，数论、概率论及组合数学基础等。本书以历年相关竞赛常见考试题型及题例作为例题解析和习题。书中的绝大部分代码规范、简洁、易懂，不仅能帮助读者理解信息技术中的算法原理，在掌握各类经典算法的同时还能学会很多实用的编程技巧，提高分析解决实际问题的能力。

本书可作为全国青少年信息学奥林匹克联赛(NOIP)初/复赛、全国青少年信息学奥林匹克竞赛(NOI)的教材和指导用书，也可作为有意参加ACM国际大学生程序设计竞赛及相关同类算法竞赛的读者的教材和参考用书。

金牌教练带学，培养学习兴趣；分析讲解真题，提高竞赛成绩；训练实战能力，锻炼计算思维。
全国青少年信息学奥林匹克联赛(NOIP)算法竞赛实战训练书籍，含近年来竞赛普及组与提高组真题详解，作者团队全部为重点中学信息奥赛教练。