书籍详情
全国信息学奥林匹克联赛培训教程（二）
作者：吴文虎，王建德 编著
出版社：清华大学出版社
出版时间：2004-02-01
ISBN：9787302074106
定价：¥23.80
购买这本书可以去
内容简介
“中国计算机学会信息学奥林匹克系列丛书”由中国计算机学会信息学奥林匹克科学委员会主编，由全国著名专家学者精心编著而成。本书是本套丛书普及本中培训教程的第二册，它在第一册的基础上，针对联赛考核的知识点，讲解了程序测试、效率分析和程序设计中数据结构和算法等内容，并提供了提高算法效率的具体策略，不仅能帮助刚刚迈进信息学奥林匹克竞赛大门的参赛选手掌握程序设计的基本知识，更从启迪思维的角度引导他们如何分析问题和解决问题。本书还提供了大量的例题及解题算法，以帮助读者更为深刻的理解和掌握解题思路，并在实战中灵活运用。本书深入浅出、思路清晰，既可以作为全国信息学奥林匹克联赛的培训教材、联赛辅导教师的参考用书、参赛选手的自学用书，也可作为大中专院校相关专业以及电脑爱好者的参考书。
作者简介
暂缺《全国信息学奥林匹克联赛培训教程（二）》作者简介
目录
第一篇 程序的测试和效率分析
第1章 测试程序
1.1 系统的测试工具
1.1.1 调试初始化
1.1.2 单步跟踪
1.1.3 执行到光标所在行
1.1.4 断点
1.1.5 求值和修改
1.1.6 路标
1.1.7 准备编译运行调试后的程序
1.2 测试用例的选取方法
1.2.1 白箱法
1.2.2 黑箱法
1.2.3 综合策略
习题
第2章 程序的效率分析
2.1 程序工作量的度量方法
2.1.1 基本运算
2.1.2 输入尺寸
2.1.3 输入情况
2.1.4 复杂度的阶
2.2 优化时间效率的方法
2.2.1 常数计算
2.2.2 尽可能在编译时赋值
2.2.3 算术运算
2.2.4 避免重复计算
2.2.5 应有利于编译优化
2.2.6 关于循环结构
2.2.7 关于选择语句
2.2.8 关于逻辑表达式
2.2.9 关于下标变量
2.2.10 尽量利用库模块
2.3 程序的最优性
2.4 程序的空间复杂度
2.4.1 压缩存储技术
2.4.2 原地工作
习题
第二篇 数据结构
第3章 顺序存储结构的线性表
3.1 线性表的定义
3.1.1 顺序存储结构
3.1.2 链式存储结构
3.2 栈
3.2.1 栈的定义
3.2.2 栈的基本运算
3.2.3 栈的重要应用——计算表达式值
3.3 队列
3.3.1 队列的定义
3.3.2 队列的基本运算
3.3.3 循环队列
3.3.4 队列的应用——教育处广义线性表
3.4 串
3.4.1 串的基本概念
3.4.2 串运算的库函数
3.4.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.2 图
4.2.1 图的基本概念
4.2.2 图的存储结构
4.2.3 图的遍历和图的生成树
4.2.4 图的应用
习题
第三篇 算法设计
第5章 高精度运算
5.1 高精度的十进制运算
5.1.1 数据类型
5.1.2 基本运算
5.2 改善高精度运算的效率
5.2.1 扩大进制数
5.2.2 建立因子表
习题
第6章 构造法
6.1 对应策略
6.1.1 对应经典问题
6.1.2 对应简单问题
6.1.3 对应数学问题
6.2 分治策略
6.2.1 递推的分治策略
6.2.2 递归的分治策略
6.3 归纳策略
6.3.1 递推法
6.3.2 递归法
6.3.3 制定目标
6.3.4 贪心法
6.4 模拟策略
6.4.1 直叙式模拟
6.4.2 筛选法模拟
6.4.3 构造法模拟
习题
第7章 搜索法
7.1 枚举法
7.1.1 “直译”的枚举算法
7.1.2 枚举算法的优化
7.2 回溯法
7.2.1 回溯法的基本思路
7.2.2 回溯法的应用实例
7.2.3 回溯法的优化
7.3 广度优先搜索
7.3.1 广度优先搜索的基本思路
7.3.2 求初始状态所能到达的所有状态
7.3.3 计算初始状态到目标状态的最短路径
习题
第8章 动态程序设计方法
8.1 问题的引出
8.2 动态程序设计方法的基本概念
8.2.1 阶段和状态
8.2.2 决策和策略
8.2.3 最优化原理与无后效性
8.2.4 最优指标函数和状态转移方程
8.3 动态程序设计方法的基本思维方式
8.4 动态程序设计方法的应用实例
8.4.1 计算所有方案
8.4.2 计算一些阶段性明显、但不具备最优子结构特征的问题
8.4.3 双重动态程序设计
8.4.4 多进程的最优化决策问题
习题
第1章 测试程序
1.1 系统的测试工具
1.1.1 调试初始化
1.1.2 单步跟踪
1.1.3 执行到光标所在行
1.1.4 断点
1.1.5 求值和修改
1.1.6 路标
1.1.7 准备编译运行调试后的程序
1.2 测试用例的选取方法
1.2.1 白箱法
1.2.2 黑箱法
1.2.3 综合策略
习题
第2章 程序的效率分析
2.1 程序工作量的度量方法
2.1.1 基本运算
2.1.2 输入尺寸
2.1.3 输入情况
2.1.4 复杂度的阶
2.2 优化时间效率的方法
2.2.1 常数计算
2.2.2 尽可能在编译时赋值
2.2.3 算术运算
2.2.4 避免重复计算
2.2.5 应有利于编译优化
2.2.6 关于循环结构
2.2.7 关于选择语句
2.2.8 关于逻辑表达式
2.2.9 关于下标变量
2.2.10 尽量利用库模块
2.3 程序的最优性
2.4 程序的空间复杂度
2.4.1 压缩存储技术
2.4.2 原地工作
习题
第二篇 数据结构
第3章 顺序存储结构的线性表
3.1 线性表的定义
3.1.1 顺序存储结构
3.1.2 链式存储结构
3.2 栈
3.2.1 栈的定义
3.2.2 栈的基本运算
3.2.3 栈的重要应用——计算表达式值
3.3 队列
3.3.1 队列的定义
3.3.2 队列的基本运算
3.3.3 循环队列
3.3.4 队列的应用——教育处广义线性表
3.4 串
3.4.1 串的基本概念
3.4.2 串运算的库函数
3.4.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.2 图
4.2.1 图的基本概念
4.2.2 图的存储结构
4.2.3 图的遍历和图的生成树
4.2.4 图的应用
习题
第三篇 算法设计
第5章 高精度运算
5.1 高精度的十进制运算
5.1.1 数据类型
5.1.2 基本运算
5.2 改善高精度运算的效率
5.2.1 扩大进制数
5.2.2 建立因子表
习题
第6章 构造法
6.1 对应策略
6.1.1 对应经典问题
6.1.2 对应简单问题
6.1.3 对应数学问题
6.2 分治策略
6.2.1 递推的分治策略
6.2.2 递归的分治策略
6.3 归纳策略
6.3.1 递推法
6.3.2 递归法
6.3.3 制定目标
6.3.4 贪心法
6.4 模拟策略
6.4.1 直叙式模拟
6.4.2 筛选法模拟
6.4.3 构造法模拟
习题
第7章 搜索法
7.1 枚举法
7.1.1 “直译”的枚举算法
7.1.2 枚举算法的优化
7.2 回溯法
7.2.1 回溯法的基本思路
7.2.2 回溯法的应用实例
7.2.3 回溯法的优化
7.3 广度优先搜索
7.3.1 广度优先搜索的基本思路
7.3.2 求初始状态所能到达的所有状态
7.3.3 计算初始状态到目标状态的最短路径
习题
第8章 动态程序设计方法
8.1 问题的引出
8.2 动态程序设计方法的基本概念
8.2.1 阶段和状态
8.2.2 决策和策略
8.2.3 最优化原理与无后效性
8.2.4 最优指标函数和状态转移方程
8.3 动态程序设计方法的基本思维方式
8.4 动态程序设计方法的应用实例
8.4.1 计算所有方案
8.4.2 计算一些阶段性明显、但不具备最优子结构特征的问题
8.4.3 双重动态程序设计
8.4.4 多进程的最优化决策问题
习题
猜您喜欢
