全国信息学奥林匹克联赛培训教程（二） (2008 年度畅销榜NO.407 )

“中国计算机学会信息学奥林匹克系列丛书”由中国计算机学会信息学奥林匹克科学委员会主编，由全国著名专家学者精心编著而成。
本书是本套丛书普及本中培训教程的第二册，它在第一册的基础上，针对联赛考核的知识点，讲解了程序测试、效率分析和程序设计中数据结构和算法等内容，并提供了提高算法效率的具体策略，不仅能帮助刚刚迈进信息学奥林匹克竞赛大门的参赛选手掌握程序设计的基本知识，更从启迪思维的角度引导他们如何分析问题和解决问题。本书还提供了大量的例题及解题算法，以帮助读者更为深刻的理解和掌握解题思路，并在实战中灵活运用。
本书深入浅出、思路清晰，既可以作为全国信息学奥林匹克联赛的培训教材、联赛辅导教师的参考用书、参赛选手的自学用书，也可作为大中专院校相关专业以及电脑爱好者的参考书。

第一篇 程序的测试和效率分析

第1章 测试程序
1.1 系统的测试工具
1.2 测试用例的选取方法
习题
第2章 程序的效率分析
2.1 程序工作量的度量方法
2.2 优化时间效率的方法
2.3 程序的最优性
2.4 程序的空间复杂度
习题

第二篇 数据结构

第3章 顺序存储结构的线性表
3.1 线性表的定义
3.2 栈
3.3 队列
3.4 串
习题
第4章 非线性结构—树和图
4.1 树
4.2 图
习题

第三篇 算法设计

第5章 高精度运算
5.1 高精度的十进制运算
5.2 改善高精度运算的效率
习题
第6章 构造法
6.1 对应策略
6.2 分治策略
6.3 归纳策略
6.4 模拟策略
习题
第7章 搜索法
7.1 枚举法
7.2 回溯法
7.3 广度优先搜索
习题
第8章 动态程序设计方法
8.1 问题的引出
8.2 动态程序设计方法的基本概念
8.3 动态程序设计方法的基本思维方式
8.4 动态程序设计方法的应用实例
习题

全国信息学奥林匹克联赛主要是上机编程。所谓程序设计，有一句至理名言回答了这个问题：“程序设计：数据结构+算法”。编程一般分三步走： 第一步是宏观设计，定义数据模型级上的运算步骤。在这一步中不需要明确变量的数据结构，算法带有抽象性质，不含具体细节。宏观设计的效果取决于选手的算法知识和数学思维能力。 第二步是微观设计，为每一个变量定义数据结构，为每一个抽象运算编写程序。微观设计是宏观设计的具体实现，它依赖于宏观设计中定义的那些抽象运算。同样只有通过微观设计选择合适的语句形式和数据类型，才能最终实现宏观设计中定义的抽象运算并确定其效率。微观设计的效果取决于选手的数据结构知识和编程技术。 第三步是测试和效率分析。计算机的内存空间是有限的，联赛对每一个程序运行的时间也作了限定。对于一个刚编好的程序，运行时是否会发生内存溢出，能否在有限的时间内出解，该解是不是与试题要求的目标相符，这些问题必须由相应的测试和效率分析来回答。只有通过测试验证其正确性，且效率满足要求的程序，才算得上是一个成功的程序。测试和效率分析的效果反映了选手的综合能力(包括测试和效率优化技术在内)。 由此可见，程序采用的计算模型、变量的数据类型与定义在该类型上的运算、程序的测试和效率分析是彼此依赖、互相制约、融为一体的，它是编程实现的基础。本书将“程序的测试和效率分析”、“数据结构”和“算法设计”融合在一起，正是体现了它们之间密不可分的关系。 本教程按照竞赛大纲的要求安排章节，讲思想，讲方法，注重基础训练。不仅每个重要的知识点给出了程序范例，而且每个章节后提供了可供读者练习的大量习题，这些题目既新颖，难度又与联赛相当。我们这样做的目的，旨在使读者今后接触到联赛试题时，不致于感到陌生和难于理解。 这里，要说明的是，本教程在分析程序时不提供可直接上机运行的源代码，而是采用贴近自然语言的类Pascal来描述算法的基本思想和步骤。我们之所以这样做是因为： (1)为了节省篇幅； (2)读者通过全国信息学奥林匹克联赛培训教程(一)的学习，已经具备了Pascal的语法基础，并初步学会了编程： (3)由于联赛的编程语言可在QBasic，C，Pascal和Java中任选，因此关键是提供一个能清晰表达算法的伪代码： (4)给读者留下一个上机实践的空间，避免“依葫芦画瓢”。 “纸上得来终觉浅，绝知此事要躬行”。建议读者在基本理解这些知识的基础上，不妨亲手做一做书中的试题，通过上机获得再认识和再提高。从长远来看，无论是中学阶段的联赛，还是大学相关专业的学习，或者是将来从事编程工作，所面临的实际问题千奇百怪，数据模型千姿百态，问题求解的算法千变万化。究竟采用哪一种算法，设计哪一类数据结构，选择哪一种语句形式，确定哪一种测试手段或提高效率的方法，都要求读者从实际出发，因地因时制宜，自己想方设法解决。只有通过不断实践，才能渐入本书的程序分析所描述的那种佳境，并有所发现、发明和创造。“阵而后战，兵法之常，运用之妙，存乎一心”。