“中国计算机学会信息学奥林匹克系列丛书”由中国计算机学会信息学奥林匹克科学委员会主编，由全国著名专家学者精心编著而成。

本书是本套丛书普及本中培训教程的第二册，它在第一册的基础上，针对联赛考核的知识点，讲解了程序测试、效率分析和程序设计中数据结构和算法等内容，并提供了提高算法效率的具体策略，不仅能帮助刚刚迈进信息学奥林匹克竞赛大门的参赛选手掌握程序设计的基本知识，更从启迪思维的角度引导他们如何分析问题和解决问题。本书带提供了大量的例题及解题算法，以帮助读者更深刻的理解和掌握解题思路，并在实战中灵活运用。

本书深入浅出、思路清晰，既可作为全国信息学奥林匹克联赛的培训教材、联赛辅导教师的参考用书、参赛选手的自学用书，也可作为大中专院校相关专业以及电脑爱好者的参考书。

全国信息学奥林匹克联赛主要是上机编程。所谓程序设计，有一句至理名言回答了这个问题：“程序设计=数据结构+算法”。编程一般分三步走：

第一步是宏观设计，定义数据模型级上的运算步骤。在这一步中不需要明确变量的数据结构，算法带有抽象性质，不含具体细节。宏观设计的效果取决于选手的算法知识和数学思维能力。

第二步是微观设计，为每一个变量定义数据结构，为每一个抽象运算编写程序。微观设计是宏观设计的具体实现，它依赖于宏观设计中定义的那些抽象运算。同样只有通过微观设计选择合适的语句形式和数据类型，才能最终实现宏观设计中定义的抽象运算并确定其效率。微观设计的效果取决于选手的数据结构知识和编程技术。

第三步是测试和效率分析。计算机的内存空间是有限的，联赛对每一个程序运行的时间也作了限定。对于一个刚编好的程序，运行时是否会发生内存溢出，能否在有限的时间内出解，该解是不是与试题要求的目标相符，这些问题必须由相应的测试和效率分析来回答。只有通过测试验证其正确性，且效率满足要求的程序，才算得上是一个成功的程序。测试和效率分析的效果反映了选手的综合能力（包括测试和效率优化技术在内）。

由此可见，程序采用的计算模型、变量的数据类型与定义在该类型上的运算、程序的测试和效率分析是彼此依赖、互相制约、融为一体的，它是编程实现的基础。本书将“程序的测试和效率分析”、“数据结构”和“算法设计”融合在一起，正是体现了它们之间密不可分的关系。 

本教程按照竞赛大纲的要求安排章节，讲思想，讲方法，注重基础训练。不仅每个重要的知识点给出了程序范例，而且每个章节后提供了可供读者练习的大量习题，这些题目既新颖，难度又与联赛相当。我们这样做的目的，旨在使读者今后接触到联赛试题时，不致于感到陌生和难于理解。

这里，要说明的是，本教程在分析程序时不提供可直接上机运行的源代码，而是采用贴近自然语言的类Pascal来描述算法的基本思想和步骤。我们之所以这样做是因为：

（1）为了节省篇幅；

（2）读者通过全国信息学奥林匹克联赛培训教程（一）的学习，已经具备了Pascal的语法基础，并初步学会了编程；

（3）由于联赛的编程语言可在QBasic，C，Pascal和Java中任选，因此关键是提供一个能清晰表达算法的伪代码；

（4）给读者留下一个上机实践的空间，避免“依葫芦画瓢”。

“纸上得来终觉浅，绝知此事要躬行”。建议读者在基本理解这些知识的基础上，不妨亲手做一做书中的试题，通过上机获得再认识和再提高。从长远来看，无论是中学阶段的联赛，还是大学相关专业的学习，或者是将来从事编程工作，所面临的实际问题千奇百怪，数据模型千姿百态，问题求解的算法千变万化。究竟采用哪一种算法，设计哪一类数据结构，选择哪一种语句形式，确定哪一种测试手段或提高效率的方法，都要求读者从实际出发，因地因时制宜，自己想方设法解决。只有通过不断实践，才能渐入本书的程序分析所描述的那种佳境，并有所发现、发明和创造。“阵而后战，兵法之常，运用之妙，存乎一心”。

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

第1章  测试程序 3

1.1  系统的测试工具 3

1.1.1  调试初始化 6

1.1.2  单步跟踪 7

1.1.3  执行到光标所在行 7

1.1.4  断点 7

1.1.5  求值和修改 7

1.1.6  路标 8

1.1.7  准备编译运行调试后的程序 8

1.2  测试用例的选取方法 8

1.2.1  白箱法 8

1.2.2  黑箱法 11

1.2.3  综合策略 13

习题 15

第2章  程序的效率分析 17

2.1  程序工作量的度量方法 17

2.1.1  基本运算 17

2.1.2  输入尺寸 18

2.1.3  输入情况 18

2.1.4  复杂度的阶 20

2.2  优化时间效率的方法 21

2.2.1  常数计算 22

2.2.2  尽可能在编译时赋值 23

2.2.3  算术运算 23

2.2.4  避免重复计算 24

2.2.5  应有利于编译优化 25

2.2.6  关于循环结构 25

2.2.7  关于选择语句 28

2.2.8  关于逻辑表达式 30

2.2.9  关于下标变量 30

2.2.10  尽量利用库模块 32

2.3  程序的最优性 32

2.4  程序的空间复杂度 35

2.4.1  压缩存储技术 36

2.4.2  原地工作 37

习题 37

第二篇  数 据 结 构

第3章  顺序存储结构的线性表 41

3.1  线性表的定义 41

3.1.1  顺序存储结构 42

3.1.2  链式存储结构 43

3.2  栈 44

3.2.1  栈的定义 44

3.2.2  栈的基本运算 45

3.2.3  栈的重要应用——计算表达式值 46

3.3  队列 50

3.3.1  队列的定义 50

3.3.2  队列的基本运算 51

3.3.3  循环队列 52

3.3.4  队列的应用——计算广义线性表 54

3.4  串 58

3.4.1  串的基本概念 58

3.4.2  串运算的库函数 60

3.4.3  串运算的应用——子串模式匹配 61

习题 66

第4章  非线性结构——树和图 69

4.1  树 69

4.1.1  树的概念 70

4.1.2  树的表示方法和存储结构 72

4.1.3  二叉树的概念 74

4.1.4  树或森林转换成二叉树 76

4.1.5  二叉树的存储结构 78

4.1.6  树或森林的遍历 79

4.1.7  由二叉树的两种遍历顺序确定树结构 87

4.1.8  二叉树的重要应用 90

4.2  图 97

4.2.1  图的基本概念 97

4.2.2  图的存储结构 99

4.2.3  图的遍历和图的生成树 102

4.2.4  图的应用 106

习题 124

第三篇  算 法 设 计

第5章  高精度运算 129

5.1  高精度的十进制运算 129

5.1.1  数据类型 129

5.1.2  基本运算 130

5.2  改善高精度运算的效率 132

5.2.1  扩大进制数 132

5.2.2  建立因子表 134

习题 135

第6章  构造法 141

6.1  对应策略 142

6.1.1  对应经典问题 142

6.1.2  对应简单问题 147

6.1.3  对应数学问题 151

6.2  分治策略 159

6.2.1  递推的分治策略 160

6.2.2  递归的分治策略 162

6.3  归纳策略 166

6.3.1  递推法 166

6.3.2  递归法 174

6.3.3  制定目标 177

6.3.4  贪心法 178

6.4  模拟策略 185

6.4.1  直叙式模拟 186

6.4.2  筛选法模拟 188

6.4.3  构造法模拟 189

习题 194

第7章  搜索法 203

7.1  枚举法 203

7.1.1 “直译”的枚举算法 204

7.1.2  枚举算法的优化 207

7.2  回溯法 213

7.2.1  回溯法的基本思路 213

7.2.2  回溯法的应用实例 219

7.2.3  回溯法的优化 225

7.3  广度优先搜索 229

7.3.1  广度优先搜索的基本思路 229

7.3.2  求初始状态所能到达的所有状态 230

7.3.3  计算初始状态到目标状态的最短路径 235

习题 239

第8章  动态程序设计方法 243

8.1  问题的引出 243

8.2  动态程序设计方法的基本概念 246

8.2.1  阶段和状态 246

8.2.2  决策和策略 247

8.2.3  最优化原理与无后效性 248

8.2.4  最优指标函数和状态转移方程 248

8.3  动态程序设计方法的基本思维方式 249

8.4  动态程序设计方法的应用实例 254

8.4.1  计算所有方案 254

8.4.2  计算一些阶段性明显、但不具备最优子

                  结构特征的问题 256

8.4.3  双重动态程序设计 257

8.4.4  多进程的最优化决策问题 263

习题 266