第一篇 基础知识篇 3
第1章 全国青少年信息学奥林匹克联赛大纲 3
1.1竞赛形式和成绩评定 3
1.2试题形式 3
1.3.试题的知识范围 4
1.3.1初赛内容与要求 4
1.3.2复赛内容与要求 5
第2章 计算机相关理论知识 6
2.1计算机和信息技术的发展 6
2.2计算机硬件知识 9
2.3计算机软件知识 16
2.4计算机中的信息表示 20
2.5多媒体技术 23
2.5.1多媒体的基本概念 23
2.5.2多媒体数据压缩 24
2.5.3图形与图像 24
2.5.4动态图像 26
2.5.5数字化音频 28
2.5.6多媒体创作 29
2.6计算机网络知识 30
2.6.1网络发展概述 30
2.6.2网络的基本概念 30
2.6.3网络的分类、组成与功能 32
2.6.4网络的标准和协议 32
2.6.5网络操作系统 34
2.6.6局域网和广域网 36
2.6.7 Internet简介 38
2.6.8网络安全性概述 38
2.7信息技术的新名词、新发展、新特点、新应用 39
2.7.1 Web 2.0和博客、微博 39
2.7.2 J2EE 41
2.7.3.NET平台 41
2.7.4 Web Service 41
2.7.5数据仓库 42
2.7.6数据挖掘 42
2.7.7设计模式 43
2.7.8 XML——可扩展标记语言 43
2.7.9 UML 43
2.7.10 P2P技术 43
2.7.11 AOP 43
2.7.12网格计算与普适计算 44
2.7.13云计算与SaaS 44
2.7.14多核技术 44
第3章 数据结构 45
3.1存储结构 45
3.1.1数组 45
3.1.2链表 45
3.2散列表、栈、队列 46
3.2.1散列表 46
3.2.2栈 47
3.2.3队列 47
3.3树和图 47
3.3.1树 47
3.3.2二叉树 48
3.3.3堆 50
3.3.4图 50
第4章 算法介绍 53
4.1算法的基本概念 53
4.1.1算法的特征 53
4.1.2算法的表示方法 53
4.1.3算法分析——算法的复杂性 54
4.2递归 56
4.2.1递归的概念 56
4.2.2如何设计递归算法 57
4.3分治 57
4.3.1分治策略的定义 57
4.3.2分治算法的特征 58
4.3.3分治法解题的步骤 58
4.4排序 62
4.4.1简单排序 62
4.4.2快速排序 64
4.4.3希尔排序 65
4.4.4堆排序与二叉树排序 67
4.4.5归并排序 69
4.4.6线性排序 69
4.4.7 各种排序算法的比较 72
4.5穷举算法 72
4.5.1穷举策略的概念 72
4.5.2典型例题 72
4.6贪心算法 74
4.6.1贪心策略的定义 74
4.6.2贪心策略的特点 75
4.6.3典型例题——合并果子 75
4.7动态规划 76
4.7.1动态规划介绍 76
4.7.2用动态规划解题 78
4.7.3典型问题分析 83
第5章 数学基础 87
5.1代数和几何知识介绍 87
5.1.1对数函数及其应用 87
5.1.2从平面向量到空间向量 88
5.1.3时间复杂度分析与最优排序 90
5.2组合数学初步 92
5.2.1排列与组合 92
5.2.2几个特殊的数列 95
5.2.3容斥原理与错位排列问题 97
5.2.4鸽巢原理 99
5.2.5 Nim取石子游戏 100
5.2.6图论浅谈——二分图理论与Ramsey理论 103
5.2.7从两个形似的问题看数学模型的构建 106
第二篇 真题解析篇 111
第6章 普及组试题与解析 111
6.1第十二届全国青少年信息学奥林匹克联赛初赛试题及解析 111
6.1.1第十二届全国青少年信息学奥林匹克联赛初赛试题 111
6.1.2第十二届全国信息学奥林匹克联赛初赛普及试题解析 121
6.2第十三届全国青少年信息学奥林匹克联赛初赛试题及解析 123
6.2.1第十三届全国青少年信息学奥林匹克联赛初赛试题 123
6.2.2第十三届全国信息学奥林匹克联赛初赛普及试题解析 137
6.3第十四届全国青少年信息学奥林匹克联赛初赛试题及解析 139
6.3.1第十四届全国青少年信息学奥林匹克联赛初赛试题 139
6.3.2第十四届全国信息学奥林匹克联赛初赛普及试题解析 152
6.4第十五届全国青少年信息学奥林匹克联赛初赛试题及解析 154
6.4.1第十五届全国青少年信息学奥林匹克联赛初赛试题 154
6.4.2第十五届全国信息学奥林匹克联赛初赛普及试题解析 167
6.5第十六届全国青少年信息学奥林匹克联赛初赛试题及解析 169
6.5.1第十六届全国青少年信息学奥林匹克联赛初赛试题 169
6.5.2十六届全国信息学奥林匹克联赛初赛普及试题解析 184
第7章 提高组试题与解析 187
7.1第十二届全国青少年信息学奥林匹克联赛初赛试题及解析 187
7.1.1第十二届全国青少年信息学奥林匹克联赛初赛试题 187
7.1.2第十二届全国信息学奥林匹克联赛初赛提高组试题解析 201
7.2第十三届全国青少年信息学奥林匹克联赛初赛试题及解析 204
7.2.1第十三届全国青少年信息学奥林匹克联赛初赛试题 204
7.2.2第十三届全国信息学奥林匹克联赛初赛提高组试题解析 217
7.3第十四届全国青少年信息学奥林匹克联赛初赛试题及解析 220
7.3.1第十四届全国青少年信息学奥林匹克联赛初赛试题 220
7.3.2第十四届全国信息学奥林匹克联赛初赛提高组试题解析 232
7.4第十五届全国青少年信息学奥林匹克联赛初赛试题及解析 235
7.4.1第十五届全国青少年信息学奥林匹克联赛初赛试题 235
7.4.2第十五届全国信息学奥林匹克联赛初赛提高组试题解析 249
7.5第十六届全国青少年信息学奥林匹克联赛初赛试题及解析 252
7.5.1第十六届全国青少年信息学奥林匹克联赛初赛试题 252
7.5.2第十六届全国信息学奥林匹克联赛初赛提高组试题解析 271
第三篇模拟试题篇 277
第8章 模拟试题一 277
8.1模拟试题（一）普及组（C++） 277
8.2模拟试题（一）普及组（ Pascal） 284
8.3模拟试题（一）提高组（C++） 291
8.4模拟试题（一）提高组（Pascal） 299
第9章 模拟试题二 307
9.1模拟试题（二）普及组（C++） 307
9.2模拟试题（二）普及组（Pascal） 316
9.3模拟试题（二）提高组（C++） 324
9.4模拟试题（二）提高组（Pascal） 333
第10章 模拟试题三 342
10.1模拟试题（三）普及组（C++） 342
10.2模拟试题（三）普及组（Pascal） 349
10.3模拟试题（三）提高组（C++ ） 355
10.4模拟试题（三）提高组（Pascal） 362
第四篇 试题解答篇 371
第11章 模拟试题（一）解答 371
11.1模拟试题（一）普及组解答 371
11.1.1普及组解析 371
11.1.2普及组参考答案 376
11.2模拟试题（一）提高组解答 377
11.2.1提高组解析 377
11.2.2提高组参考答案 378
第12章 模拟试题（二）解答 380
12.1模拟试题（二）普及组解答 380
12.1.1普及组解析 380
12.1.2普及组参考答案 383
12.2模拟试题（二）提高组解答 384
12.2.1提高组解析 384
12.2.2提高组参考答案 384
第13章 模拟试题（三）解答 386
13.1模拟试题（三）普及组解答 386
13.1.1普及组解析 386
13.1.2普及组参考答案 388
13.2模拟试题（三）提高组解答 389
13.2.1提高组解析 389
13.2.2提高组参考答案 390