数据结构: C++语言版 第三版

✍ Scribed by 邓俊辉

• Publisher: 清华大学出版社
• Year: 2013
• Tongue: Chinese
• Leaves: 514
• Series: 清华大学计算机系列教材
• Edition: 3
• Category: Library

✦ Synopsis

《清华大学计算机系列教材:数据结构(C++语言版)(第3版)》按照面向对象程序设计的思想，根据作者多年的教学积累，系统地介绍各类数据结构的功能、表示和实现，对比各类数据结构适用的应用环境；结合实际问题展示算法设计的一般性模式与方法、算法实现的主流技巧，以及算法效率的评判依据和分析方法；以高度概括的体例为线索贯穿全书，并通过对比和类比揭示数据结构与算法的内在联系，帮助读者形成整体性认识。

✦ Table of Contents

数据结构（C++语言版）
第1章 绪论
§1.1 计算机与算法
1.1.1 古埃及人的绳索
1.1.2 欧几里得的尺规
1.1.3 起泡排序
 局部有序与整体有序
 扫描交换
 起泡排序
 实现
1.1.4 算法
 输入与输出
 基本操作、确定性与可行性
 有穷性与正确性
 起泡排序
 退化与鲁棒性
 重用性
1.1.5 算法效率
 可计算性
 难解性
 计算效率
 数据结构
§1.2 复杂度度量
1.2.1 时间复杂度
1.2.2 渐进复杂度
 大O记号
 环境差异
 基本操作
 起泡排序
 最坏、最好与平均情况
 大(记号
 大(记号
1.2.3 空间复杂度
§1.3 复杂度分析
1.3.1 常数O(1)
 问题与算法
 复杂度
1.3.2 对数O(logn)
 问题与算法
 复杂度
 对数多项式复杂度
1.3.3 线性O(n)
 问题与算法
 复杂度
1.3.4 多项式O(polynomial(n))
1.3.5 指数O(2n)
 问题与算法
 复杂度
 从多项式到指数
1.3.6 复杂度层次
1.3.7 输入规模
§1.4 递归
1.4.1 线性递归
 数组求和
 线性递归
 减而治之
1.4.2 递归分析
 递归跟踪
 递推方程
1.4.3 递归模式
 多递归基
 实现递归
 多向递归
1.4.4 递归消除
 空间成本
 尾递归及其消除
1.4.5 二分递归
 分而治之
 数组求和
 效率
 Fibonacci数：二分递归
 优化策略
 Fibonacci数：线性递归
 Fibonacci数：迭代
§1.5 抽象数据类型
第2章 向量
§2.1 从数组到向量
2.1.1 数组
2.1.2 向量
§2.2 接口
2.2.1 ADT接口
2.2.2 操作实例
2.2.3 Vector模板类
§2.3 构造与析构
2.3.1 默认构造方法
2.3.2 基于复制的构造方法
2.3.3 析构方法
§2.4 动态空间管理
2.4.1 静态空间管理
2.4.2 可扩充向量
2.4.3 扩容
2.4.4 分摊分析
 时间代价
 分摊复杂度
 O(1)分摊时间
 其它扩容策略
2.4.5 缩容
§2.5 常规向量
2.5.1 直接引用元素
2.5.2 置乱器
 置乱算法
 区间置乱接口
2.5.3 判等器与比较器
2.5.4 无序查找
 判等器
 顺序查找
 实现
 复杂度
2.5.5 插入
 实现
 复杂度
2.5.6 删除
 区间删除：remove(lo, hi)
 单元素删除remove(r)
 复杂度
 错误及意外处理
2.5.7 唯一化
 实现
 正确性
 复杂度
2.5.8 遍历
 功能
 实现
 实例
 复杂度
§2.6 有序向量
2.6.1 比较器
2.6.2 有序性甄别
2.6.3 唯一化
 低效版
 改进思路
 高效版
 复杂度
2.6.4 查找
2.6.5 二分查找（版本A）
 减而治之
 实现
 实例
 复杂度
 查找长度
 成功查找长度
 失败查找长度
 不足
2.6.6 Fibonacci查找
 递推方程
 黄金分割
 实现
 定性比较
 定量分析
2.6.7 二分查找（版本B）
 从三分支到两分支
 实现
 性能
 进一步的要求
2.6.8 二分查找（版本C）
 实现
 正确性
§2.7 排序与下界
2.7.1 有序性
2.7.2 排序及其分类
2.7.3 下界
 苹果鉴别
 复杂度下界
2.7.4 比较树
 基于比较的分支
 比较树
2.7.5 估计下界
 最小树高
 苹果鉴别
 排序
§2.8 排序器
2.8.1 统一入口
2.8.2 起泡排序
 起泡排序
 扫描交换
 重复元素与稳定性
2.8.3 归并排序
 历史与发展
 有序向量的二路归并
 分治策略
 实例
 二路归并接口的实现
 归并时间
 推广
 排序时间
第3章 列表
§3.1 从向量到列表
3.1.1 从静态到动态
3.1.2 由秩到位置
3.1.3 列表
§3.2 接口
3.2.1 列表节点
 ADT接口
 ListNode模板类
3.2.2 列表
 ADT接口
 List模板类
§3.3 列表
3.3.1 头、尾节点
3.3.2 默认构造方法
3.3.3 由秩到位置的转换
3.3.4 查找
 实现
 复杂度
3.3.5 插入
 接口
 前插入
 后插入
 复杂度
3.3.6 基于复制的构造
 copyNodes()
 基于复制的构造
3.3.7 删除
 实现
 复杂度
3.3.8 析构
 释放资源及清除节点
 复杂度
3.3.9 唯一化
 实现
 正确性
 复杂度
3.3.10 遍历
§3.4 有序列表
3.4.1 唯一化
3.4.2 查找
 实现
 顺序查找
 复杂度
§3.5 排序器
3.5.1 统一入口
3.5.2 插入排序
 构思
 实例
 实现
 复杂度
3.5.3 选择排序
 构思
 实例
 实现
 复杂度
3.5.4 归并排序
 二路归并算法的实现
 归并时间
 特例
 分治策略
 排序时间
第4章 栈与队列
§4.1 栈
4.1.1 ADT接口
 入栈与出栈
 后进先出
4.1.2 操作实例
4.1.3 Stack模板类
§4.2 栈与递归
4.2.1 函数调用栈
 函数调用
 递归
4.2.2 避免递归
§4.3 栈的典型应用
4.3.1 逆序输出
 进制转换
 递归实现
 迭代实现
4.3.2 递归嵌套
 栈混洗
 括号匹配
 递归实现
 迭代实现
4.3.3 延迟缓冲
 表达式求值
 优先级表
 求值算法
 不同优先级的处置
 语法检查及鲁棒性
4.3.4 逆波兰表达式
 RPN
 求值算法
 手工转换
 自动转换
§4.4 试探回溯法
4.4.1 试探与回溯
 忒修斯的法宝
 剪枝
 线绳与粉笔
4.4.2 八皇后
 皇后
 算法实现
 实例
4.4.3 迷宫寻径
 问题描述
 迷宫格点
 邻格查询
 邻格转入
 算法实现
 实例
 正确性
 复杂度
§4.5 队列
4.5.1 概述
 入队与出队
 先进先出
4.5.2 ADT接口
4.5.3 操作实例
4.5.4 Queue模板类
§4.6 队列应用
4.6.1 循环分配器
4.6.2 银行服务模拟
第5章 二叉树
§5.1 二叉树及其表示
5.1.1 树
 有根树
 深度与层次
 祖先、后代与子树
 高度
5.1.2 二叉树
5.1.3 多叉树
 父节点
 孩子节点
 父节点 + 孩子节点
 有序多叉树 = 二叉树
 长子 + 兄弟
§5.2 编码树
5.2.1 二进制编码
 生成编码表
 二进制解码
 解码歧义
 前缀无歧义编码
5.2.2 二叉编码树
 根通路与节点编码
 PFC编码树
 基于PFC编码树的解码
 PFC编码树的构造
§5.3 二叉树的实现
5.3.1 二叉树节点
 BinNode模板类
 快捷方式
5.3.2 二叉树节点操作接口
 插入孩子节点
 定位直接后继
 遍历
5.3.3 二叉树
 BinTree模板类
 高度更新
 节点插入
 子树接入
 子树删除
 子树分离
 复杂度
§5.4 遍历
5.4.1 递归式遍历
 先序遍历
 后序遍历
 中序遍历
5.4.2 迭代版先序遍历
 版本1
 版本2
5.4.3 迭代版中序遍历
 版本1
 直接后继及其定位
 版本2
 版本3
5.4.4 迭代版后序遍历
5.4.5 层次遍历
 算法实现
 完全二叉树
 满二叉树
§5.5 Huffman编码
5.5.1 PFC编码及解码
 总体框架
 数据结构的选取与设计
 初始化PFC森林
 构造PFC编码树
 生成PFC编码表
 编码
 解码
 优化
5.5.2 最优编码树
 平均编码长度与叶节点平均深度
 最优编码树
 双子性
 层次性
 最优编码树的构造
5.5.3 Huffman编码树
 字符出现概率
 带权平均编码长度与叶节点带权平均深度
 完全二叉编码树 ( wald()最短
 最优带权编码树
 层次性
5.5.4 Huffman编码算法
 原理与构思
 策略与算法
 实例
 总体框架
 （超）字符
 数据结构的选取与设计
 字符出现频率的样本统计
 初始化Huffman森林
 构造Huffman编码树
 生成Huffman编码表
 编码
 解码
第6章 图
§6.1 概述
 图
 无向图、有向图及混合图
 度
 简单图
 通路与环路
 带权网络
 复杂度
§6.2 抽象数据类型
6.2.1 操作接口
6.2.2 Graph模板类
§6.3 邻接矩阵
6.3.1 原理
6.3.2 实现
6.3.3 时间性能
6.3.4 空间性能
§6.4 邻接表
6.4.1 原理
6.4.2 复杂度
§6.5 图遍历算法概述
§6.6 广度优先搜索
6.6.1 策略
6.6.2 实现
6.6.3 实例
6.6.4 复杂度
6.6.5 应用
§6.7 深度优先搜索
6.7.1 策略
6.7.2 实现
6.7.3 实例
6.7.4 复杂度
6.7.5 应用
§6.8 拓扑排序
6.8.1 应用
6.8.2 有向无环图
6.8.3 算法
6.8.4 实现
6.8.5 实例
6.8.6 复杂度
§6.9 双连通域分解
6.9.1 关节点与双连通域
6.9.2 蛮力算法
6.9.3 可行算法
6.9.4 实现
6.9.5 实例
6.9.6 复杂度
§6.10 优先级搜索
6.10.1 优先级与优先级数
6.10.2 基本框架
6.10.3 复杂度
§6.11 最小支撑树
6.11.1 支撑树
6.11.2 最小支撑树
6.11.3 歧义性
6.11.4 蛮力算法
6.11.5 Prim算法
 割与极短跨越边
 贪心迭代
 实例
 实现
 复杂度
§6.12 最短路径
6.12.1 最短路径树
 歧义性
 无环性
6.12.2 Dijkstra 算法
 最短路径子树序列
 贪心迭代
 实现
 实例
 复杂度
第7章 搜索树
§7.1 查找
7.1.1 循关键码访问
7.1.2 词条
7.1.3 序与比较器
§7.2 二叉搜索树
7.2.1 顺序性
7.2.2 中序遍历序列
7.2.3 BST模板类
7.2.4 查找算法及其实现
 算法
 searchIn()算法与search()接口
 语义约定
 效率
7.2.5 插入算法及其实现
 算法
 insert()接口的实现
 效率
7.2.6 删除算法及其实现
 单分支情况
 双分支情况
 remove()
 removeAt()
 效率
§7.3 平衡二叉搜索树
7.3.1 树高与性能
 随机生成
 随机组成
 比较
 树高与平均树高
7.3.2 理想平衡与适度平衡
 理想平衡
 适度平衡
7.3.3 等价变换
 等价二叉搜索树
 局部性
7.3.4 旋转调整
 效率与效果
§7.4 AVL树
7.4.1 定义及性质
 平衡因子
 接口定义
 平衡性
 失衡与重平衡
7.4.2 节点插入
 失衡节点集
 重平衡
 单旋
 双旋
 高度复原
 实现
 效率
7.4.3 节点删除
 失衡节点集
 重平衡
 单旋
 双旋
 失衡传播
 实现
 效率
7.4.4 统一重平衡算法
第8章 高级搜索树
§8.1 伸展树
8.1.1 局部性
8.1.2 逐层伸展
 简易伸展树
 最坏情况
8.1.3 双层伸展
 zig/zag
 效果与效率
8.1.4 伸展树的实现
 伸展树接口定义
 伸展算法的实现
 查找算法的实现
 插入算法的实现
 删除算法的实现
§8.2 B-树
8.2.1 多路平衡查找
 分级存储
 多路搜索树
 多路平衡搜索树
8.2.2 ADT接口及其实现
 节点
 B-树
8.2.3 关键码查找
 算法
 实现
8.2.4 性能分析
 树高
 复杂度
8.2.5 关键码插入
8.2.6 上溢与分裂
 算法
 可能的情况
 实现
 实例
 复杂度
8.2.7 关键码删除
8.2.8 下溢与合并
 V的左兄弟L存在，且至少包含(m/2(个关键码
 V的右兄弟R存在，且至少包含(m/2(个关键码
 V的左、右兄弟L和R或者不存在，或者其包含的关键码均不足(m/2(个
 实现
 实例
 复杂度
§8.3 红黑树
8.3.1 概述
 定义与条件
 (2,4)-树
 平衡性
8.3.2 红黑树接口定义
8.3.3 节点插入算法
 节点插入与双红现象
 双红修正（RR-1）
 双红修正（RR-2）
 双红修正的复杂度
 双红修正算法的实现
8.3.4 节点删除算法
 节点删除与双黑现象
 双黑修正（BB-1）
 双黑修正（BB-2-R）
 双黑修正（BB-2-B）
 双黑修正的复杂度
 双黑修正算法的实现
§8.4 kd-树
8.4.1 范围查询
 一维范围查询
 蛮力算法
 预处理
 有序向量
 二维范围查询
 平衡二叉搜索树
 查询算法
 正确性
 效率
8.4.2 kd-树
 节点及其矩形区域
 构造算法
 实例
8.4.3 基于2d-树的范围查询
 过程
 算法
 复杂度
第9章 词典
§9.1 词典ADT
9.1.1 操作接口
9.1.2 操作实例
9.1.3 接口定义
9.1.4 实现方法
§9.2 跳转表
9.2.1 Skiplist模板类
9.2.2 总体逻辑结构
9.2.3 四联表
 Quadlist模板类
 四联表节点
 初始化与构造
9.2.4 查找
 get()
 skipSearch()
 实例
9.2.5 空间复杂度
 “生长概率逐层减半”条件
 节点总数的期望值
9.2.6 时间复杂度
 期望高度与纵向跳转次数
 横向跳转
 其它
9.2.7 插入
 put()
 实例
 insertAfterAbove()
 insertAsSuccAbove()
 时间复杂度
9.2.8 删除
 Skiplist::remove()
 Quadlist::remove()
 时间复杂度
§9.3 散列表
9.3.1 完美散列
 散列表
 散列函数
 实例
9.3.2 装填因子与空间利用率
 电话查询系统
 IP节点查询
 兼顾空间利用率与速度
9.3.3 散列函数
 设计原则
 除余法（division method）
 MAD法（multiply-add-divide method）
 更多的散列函数
 （伪）随机数法
9.3.4 散列表
 Hashtable模板类
 散列表构造
 散列表析构
9.3.5 冲突及其排解
 冲突的普遍性
 多槽位（multiple slots）法
 独立链（separate chaining）法
 公共溢出区法
9.3.6 闭散列策略
 线性试探（linear probing）法
 查找链
 局部性
 懒惰删除
 两类查找
9.3.7 查找与删除
 get()
 probe4Hit()
 remove()
9.3.8 插入
 put()
 probe4Free()
 装填因子
 重散列（rehashing）
9.3.9 更多闭散列策略
 聚集现象
 平方试探（quadratic probing）法
 局部性
 确保试探必然终止
 （伪）随机试探（pseudo-random probing）法
 再散列（double hashing）法
9.3.10 散列码转换
 强制转换为整数
 对成员对象求和
 多项式散列码
 hashCode()的实现
§9.4 散列应用
9.4.1 桶排序
 简单情况
 一般情况
9.4.2 最大间隙
 平凡算法
 散列
 正确性
 复杂度
9.4.3 基数排序
 字典序
 低位优先的多趟桶排序
 实例
 正确性与稳定性
 复杂度
第10章 优先级队列
§10.1 优先级队列ADT
10.1.1 优先级与优先级队列
10.1.2 关键码、比较器与偏序关系
10.1.3 操作接口
10.1.4 操作实例：选择排序
10.1.5 接口定义
10.1.6 应用实例：Huffman编码树
 数据结构
 比较器
 编码算法
 效率分析
§10.2 堆
10.2.1 完全二叉堆
 结构性与堆序性
 大顶堆与小顶堆
 高度
 基于向量的紧凑表示
 宏
 PQ_ComplHeap模板类
 getMax()
10.2.2 元素插入
 算法
 上滤
 实例
 实现
 改进
10.2.3 元素删除
 算法
 下滤
 实例
 实现
10.2.4 建堆
 蛮力算法
 自上而下的上滤
 Floyd算法
 实现
 实例
 复杂度
10.2.5 就地堆排序
 原理
 复杂度
 实例
 实现
§10.3 左式堆
10.3.1 堆合并
10.3.2 单侧倾斜
10.3.3 PQ_LeftHeap模板类
10.3.4 空节点路径长度
10.3.5 左倾性与左式堆
10.3.6 最右侧通路
10.3.7 合并算法
10.3.8 实例
10.3.9 合并操作merge()的实现
10.3.10 复杂度
10.3.11 基于合并的插入和删除
 delMax()
 insert()
第11章 串
§11.1 串及串匹配
11.1.1 串
 字符串
 子串
 判等
 ADT
11.1.2 串匹配
 应用与问题
 问题分类
11.1.3 测评标准与策略
§11.2 蛮力算法
11.2.1 算法描述
11.2.2 算法实现
11.2.3 时间复杂度
§11.3 KMP算法
11.3.1 构思
 简单示例
 记忆 = 经验 = 预知力
 一般实例
11.3.2 next表
11.3.3 KMP算法
11.3.4 next[0] = -1
11.3.5 next[j + 1]
11.3.6 构造next表
11.3.7 性能分析
 O(nm)？
 O(n)！
 总体复杂度
11.3.8 继续改进
 反例
 记忆 = 教训 = 预知力
 改进
§11.4 BM算法
11.4.1 思路与框架
 构思
 主体框架
11.4.2 坏字符策略
 坏字符
 BC[]表
 特殊情况
 BC[]表实例
 BC[]表构造算法
 匹配实例
 复杂度
11.4.3 好后缀策略
 构思
 好后缀
 GS[]表
 匹配实例
 复杂度
11.4.4 GS[]表构造算法
 蛮力算法
 MS[]串与SS[]表
 实例
 由SS[]表构造GS[]表
 SS[]表的构造
 算法实现
11.4.5 算法纵览
 时间效率的变化范围
 单次比对成功概率
 字符表长度
§11.5 Karp-Rabin算法
11.5.1 构思
 凡物皆数
 串亦为数
11.5.2 算法与实现
 算法
 数位与字长
 散列压缩
 散列冲突
 快速指纹更新
第12章 排序
§12.1 快速排序
12.1.1 分治策略
12.1.2 轴点
12.1.3 快速排序算法
12.1.4 快速划分算法
 反例
 思路
 实现
 过程
 实例
12.1.5 复杂度
 最坏情况
 降低最坏情况概率
 平均运行时间
12.1.6 应对退化
 改进
 效果及性能
§12.2 选取与中位数
12.2.1 概述
 k-选取
 中位数
 蛮力算法
12.2.2 众数
 问题
 必要性与充分性
 减而治之
 实现
12.2.3 归并向量的中位数
 问题
 蛮力算法
 减而治之
 实现
 一般情况
12.2.4 基于优先级队列的选取
 信息量与计算成本
 堆
12.2.5 基于快速划分的选取
 秩、轴点与快速划分
 逐步逼近
 实现
12.2.6 k-选取算法
 算法
 正确性
 复杂度
 综合评价
§12.3 希尔排序
12.3.1 递减增量策略
 增量
 算法框架
 增量序列
 底层算法
12.3.2 增量序列
 Shell序列
 邮资问题
 线性组合
 h-有序与h-排序
 有序性的保持与加强
 (g, h)-有序与排序成本
 Papernov-Stasevic序列
 Pratt序列
 Sedgewick序列
附录
参考文献
插图索引
表格索引
算法索引
代码索引
关键词索引
内容简介
丛书序
序
第3版说明
第2版说明
第1版前言
背景
原则
 兼顾基础不同、目标不同的多样化读者群体
 注重整体认识，着眼系统思维
 尊重认知规律，放眼拓展提升
说明
教学计划编排方案建议
致 谢
简要目录
详细目录
数据结构习题解析（C++语言版）
第1章 绪论
[1-1] 试借助基本的几何作图操作描述一个算法过程，实现“过直线外一点作其平行线”的功能。
[1-2] 《海岛算经》讨论了如下遥测海岛高度的问题：
[1-3] 试分别举出实例说明，在对包含n个元素的序列做起泡排序的过程中，可能发生以下情况：
[1-4] 对n个整数的排序，能否保证在最坏情况下仍可在少于O(n)的时间内完成？为什么？
[1-5] 随着问题输入规模的不断扩大，同一算法所需的计算时间通常都呈单调递增趋势，但情况亦并非总是如此。试举实例说明，随着输入规模的扩大，同一算法所需的计算时间可能上下波动。
[1-6] 在一台速度为1G flops的电脑上使用教材中代码1.1中的bubblesort1A()算法，大致需要多长时间才能完成对全国人口记录的排序？
[1-7] 试用C++语言描述一个包含循环、分支、子函数调用，甚至递归结构的算法，要求具有常数的总体时间复杂度。
[1-8] 试证明，在用对数函数界定渐进复杂度时，常底数的具体取值无所谓。
[1-9] 试证明，对于任何( > 0，都有logn = O(n()。
[1-10] 试证明，在大O记号的意义下
[1-11] 若f(n) = O(n2)且g(n) = O(n)，则以下结论是否正确：
[1-12] 改进教材13页代码1.2中countOnes()算法，使得时间复杂度降至
[1-13] 实现教材14页代码1.4中power2BF_I()算法的递归版，要求时间复杂度保持为O(n) = O(2r)。
[1-14] 实现教材21页代码1.8中power2()算法的迭代版，要求时间复杂度保持为O(logn) = O(r)。
[1-15] 考查最大元素问题：从n个整数中找出最大者。
[1-16] 考查如下问题：设S为一组共n个正整数，其总和为2m，判断是否可将S划分为两个不相交的子集，且各自总和均为m？美国总统选举即是该问题的一个具体实例：
[1-17] 试证明，若每个递归实例仅需使用常数规模的空间，则递归算法所需的空间总量将线性正比于最大的递归深度。
[1-18] 试采用递推方程法，分析教材17页代码1.5中线性递归版sum()算法的空间复杂度。
[1-19] 考查如教材24页代码1.12所示的二分递归版fib(n)算法，试证明：
[1-20] 考查Fibonacci数的计算。
[1-21] 考查fib()算法的二分递归版、线性递归版和迭代版。
[1-22] 参照教材26页代码1.14中迭代版fibI()算法，实现支持如下接口的Fib类。
[1-23] 法国数学家Edouard Lucas于1883提出的Hanoi塔问题，可形象地描述如下：
[1-24] 如图x1.4所示，考查缺失右上角（面积为4n - 1）的2n ( 2n棋盘，n ( 1。
[1-25] 《九章算术》记载的“中华更相减损术”可快速地计算正整数a和b的最大公约数，其过程如下：
[1-26] 试设计并实现一个就地的算法shift(int A[], int n, int k)，在O(n)时间内将任一数组A[0, n)中的元素整体循环左移k位。例如，数组A[] = { 1, 2, 3, 4, 5, 6 }经shift(A, 6, 2)之后，有A[] = { 3, 4, 5, 6, 1, 2 }。（提示：利用教材20页代码1.7中reverse()算法）
[1-27] 试实现一个递归算法，对任意非负整数m和n，计算以下Ackermann函数值：
[1-28] 考查所谓咖啡罐游戏（Coffee Can Game）：在咖啡罐中放有n颗黑豆与m颗白豆，每次取出两颗：若同色，则扔掉它们，然后放入一颗黑豆；若异色，则扔掉黑豆，放回白豆。
[1-29] 序列Hailstone(n)是从n开始，按照以下规则依次生成的一组自然数：
[1-30] 在分析并界定其渐进复杂度时，迭代式算法往往体现为级数求和的形式，递归式算法则更多地体现为递推方程的形式。针对这两类主要的分析技巧，参考文献[7]做了精辟的讲解和归纳。试研读其中的相关章节。
[1-31] 试针对教材20页代码1.7中的reverse()算法和21页代码1.8中的power2()算法，运用递归跟踪法分析其时间复杂度。
[1-32] 若假定机器字长无限，移位操作只需单位时间，递归不会溢出，且rand()为理想的随机数发生器。 试分析以下函数F(n)，并以大O记号的形式确定其渐进复杂度的紧上界。
第2章 向量
[2-1] 关于某个算法，甲证明“其平均时间复杂度为O(n)”，乙证明“其分摊时间复杂度为O(n)”。 若他们的结论均正确无误，则是甲的结论蕴含乙的结论，乙的结论蕴含甲的结论，还是互不蕴含？
[2-2] 教材32页代码2.2的copyFrom()算法中，目标数组_elem[]是通过new操作由系统另行分配的，故可保证在物理上与来源数组A[]相互独立。若不能保证这种独立性，该算法需要做哪些调整？
[2-3] 假设将教材34页代码2.4中expand()算法的扩容策略改为“每次追加固定数目的单元”。
[2-4] 试证明，教材36页代码2.5中shrink()算法具有分摊的常数时间复杂度。
[2-5] 设某算法中设有一个无符号32位整型变量count = b31b30...b1b0，其功能是作为计数器，不断地递增（count++，溢出后循环）。每经一次递增，count的某些比特位都会在0和1之间翻转。
[2-6] 考查教材37页代码2.7中的permute()算法，假设rand()为理想的随机数发生器，试证明：
[2-7] 在C语言标准库中，Brian W. Kernighan和Dennis M. Ritchie设计的随机数发生器如下：
[2-8] 考查教材39页代码2.10中的无序向量查找算法find(e, lo, hi)。
[2-9] 考查教材40页代码2.11中的无序向量插入算法insert(r, e)。
[2-10] 考查教材41页代码2.12中的无序向量删除算法remove(lo, hi)。
[2-11] Vector::deduplicate()算法的如下实现是否正确？为什么？
[2-12] 考查教材42页代码2.14中的无序向量唯一化算法deduplicate()。
[2-13] 试参照函数对象Increase（教材44页代码2.16）重载运算符“()”的方式，基于无序向量的遍历接口traverse()，实现以下操作（假定向量元素类型支持算术运算）：
[2-14] 字符串、复数、矢量等类型没有提供自然的比较规则，但仍能人为地对其强制定义某种大小关系（即次序关系）。试分别为这三种类型的对象定义“人工的”次序。
[2-15] 考查采用CBA式算法对4个整数的排序。
[2-16] search(e, lo, hi)算法版本C（教材56页代码2.24）所返回的秩，均符合接口规范。试针对以下情况，分别验证这一结论：
[2-17] 考虑用向量存放一组字符串。
[2-18] 设采用实现如教材48页代码2.21所示的二分查找binSearch()算法版本A，针对独立均匀分布于[0, 2n]内的整数目标，在固定的有序向量{ 1, 3, 5, ..., 2n - 1 }中查找。
[2-19] 为做Fibonacci查找，未必非要严格地将向量整理为fib(n) - 1形式的长度。 比如，可考虑以下策略：
[2-20] 试分别针对二分查找算法版本A（代码2.21）及Fibonacci算法（代码2.22），推导其失败查找长度的显式公式，并就此方面的性能对二者做一对比。
[2-21] 设A[0, n)为一个非降的正整数向量。
[2-22] 设A[0, n)[0, n)为整数矩阵（即二维向量），A[0][0] = 0且任何一行（列）都严格递增。
[2-23] 教材2.6节针对有序向量介绍的各种查找算法，落实减而治之策略的形式均大同小异：反复地“猜测”某一元素S[mi]，并通过将目标元素与之比较的结果，确定查找范围收缩的方向。然而在某些特殊的场合，沿前、后两个方向深入的代价并不对称，甚至其中之一只允许常数次。
[2-24] 在实际应用中，有序向量内的元素不仅单调排列，而且往往还服从某种概率分布。若能利用这一性质，则可以更快地完成查询。
[2-25] 对于几乎有序的向量，如教材代码2.26（60页）和代码2.27（60页）所示的起泡排序算法，都显得效率不足。
[2-26] 根据教材2.8.3节所给递推关系以及边界条件试证明，如教材62页代码2.28所示mergeSort()算法的运行时间T(n) = O(nlogn)。
[2-27] 如教材62页代码2.28所示mergeSort()算法，即便在最好情况下依然需要((nlogn)时间。
[2-28] 教材63页代码2.29中的二路归并算法merge()，反复地通过new和delete操作申请和释放辅助空间。然而实验统计表明，这类操作的实际时间成本，大约是常规运算的100倍，故往往成为制约效率提高的瓶颈。
[2-29] 二路归并算法merge()（教材63页代码2.29）中的循环体内，两条并列语句的判断逻辑，并非完全对称。
[2-30] 二路归并算法merge()（教材63页代码2.29）中的循环体，虽然形式上简洁，但流程控制逻辑却较为复杂。
[2-31] 找到（v2.4之前版本）Python的bisect模块，阅读其中bisect_right()接口的实现代码。
[2-32] 自学C++ STL中vector容器的使用方法，阅读对应的源代码。
[2-33] 自学Java语言中的Java.util.ArrayList和java.util.Vector类，并阅读对应的源代码。
[2-34] 位图（Bitmap）是一种特殊的序列结构，可用以动态地表示由一组（无符号）整数构成的集合。其长度无限，且其中每个元素的取值均为布尔型（初始均为false），支持的操作接口主要包括：
[2-35] 利用Bitmap类设计算法，在O(n)时间内剔除n个ASCII字符中的重复字符，各字符仅保留一份。
[2-36] 利用Bitmap类设计算法，快速地计算不大于10^8的所有素数。（提示：Eratosthenes筛法）
[2-37] 教材12页算法1.3中，在选出三个数之后还需对它们做排序。试证明：
[2-38] 代数判定树（algebraic decision tree, ADT）是比较树的推广，其中的节点分别对应于根据某一代数表达式做出的判断。例如，比较树中各节点所对应的“a == b”式判等以及“a < b”式比较，均可统一为根据一次代数表达式“a - b”取值符号的判断。
[2-39] 任给12个互异的整数，其中10个已组织为一个有序序列，现需要插入剩余的两个以完成整体排序。若采用CBA式算法，最坏情况下至少需做几次比较？为什么？
[2-40] 经过至多(n - 1) + (n - 2) = 2n - 3次比较，不难从任何存有n个整数的向量中找出最大者和次大者。试改进这一算法，使所需的比较次数（即便在最坏情况下）也不超过(3n/2( - 2。
[2-41] 试证明，对于任一n(m的整数矩阵M，若首先对每一列分别排序，则继续对每一行分别排序后，其中的各列将依然有序（一个实例如图x2.18所示）。（提示：只需考查n = 2的情况）
第3章 列表
[3-1] 考查列表结构的查找操作。
[3-2] 考查如教材73页代码3.7和74页代码3.8所示的列表节点插入算法LisrNode::insertAsPred()和ListNode::insertAsSucc()。
[3-3] 考查如教材75页代码3.11所示的List::remove()算法。
[3-4] 考查如教材76页代码3.14所示的List::deduplicate()算法。
[3-5] 试基于列表的遍历接口traverse()实现以下操作（假定数据对象类型支持算术运算）：
[3-6] 对数据结构的操作，往往都集中于数据元素的一个较小子集。因此对列表而言，若能将每次被访问的节点及时转移至查找长度更短的前端，则整体效率必将大为提高。这种能够自适应调整的列表，即所谓的自调整列表（self-adjusting list）。
[3-7] 自学C++ STL中list容器的使用方法，阅读对应的源代码。
[3-8] 考查插入排序算法。
[3-9] 考查选择排序算法。
[3-10] 假定序列中n个元素的数值为独立均匀地随机分布，试证明：
[3-11] 序列中元素A[i]和A[j]若满足i < j且A[i] > A[j]，则称之为一个逆序对（inversion）。 考查如教材80页代码3.19所示的插入排序算法List::insertionSort(），试证明：
[3-12] 如教材80页代码3.19所示，考查插入排序算法List::insertionSort()。
[3-13] 教材81页代码3.20中的List::selectionSort()算法，通过selectMax()在前端子序列中定位最大元素max之后，将其对应的节点整体取出，再后移并归至后端子序列之首。
[3-14] 教材81页代码3.20中的List::selectionSort()算法，通过selectMax()在前缀子序列中定位的最大元素max，有可能恰好就是tail的前驱((自然，此时“二者”无需交换。针对这一“问题”，你可能会考虑做些“优化”，以期避免上述不必要的交换，比如将
[3-15] 在如教材82页代码3.21所示的List::selectMax()算法中，若将判断条件由
[3-16] 考查如教材83页代码3.23所示的List::mergeSort()算法，试证明：
[3-17] 考查基于List::merge()算法（教材82页代码3.22）实现的List::mergeSort()算法（教材83页代码3.23）。
[3-18] 试仿照教材22页代码1.10中向量的倒置算法，实现List::reverse()接口，将列表中元素的次序前后倒置。
[3-19] Josephus环游戏的规则如下：
第4章 栈与队列
[4-1] a） 试基于3.2.2节的列表模板类List，实现栈结构；
[4-2] a） 试基于2.2.3节的向量模板类Vector，实现队列结构；
[4-3] 设B为A = { 1, 2, 3, ..., n }的任一排列。
[4-4] 设S = { 1, 2, 3, ..., n }，试证明：
[4-5] Internet超文本HTML文档，由成对出现的标志（tag）划分为不同的部分与层次。
[4-6] 教材95页代码4.7中的evaluate()算法，需借助readNumber()函数，根据当前字符及其后续的若干字符，解析出当前的操作数。试实现该函数。
[4-7] 教材95页代码4.7中的evaluate()算法，需借助orderBetween(op1, op2)函数，判定操作符op1和op2之间的优先级关系。试利用如代码4.6（教材94页）所示的优先级表，实现该函数。
[4-8] 教材95页代码4.7中的evaluate()算法，为将常规表达式转换为RPN表达式，需借助append()函数将操作数或运算符追加至字符串rpn的末尾。
[4-9] 试以表达式"(0!+1)2^(3!+4)-(5!-67-(8+9))"为例，给出evaluate()算法的完整执行过程。
[4-10] 教材95页代码4.7中的evaluate()算法，对乘方运算符"^"的求值采用了向左优先结合律，比如表达式“2^3^5”将被理解为“(2^3)^5”。
[4-11] 教材95页代码4.7中evaluate()算法执行过程中的某一时刻，设操作符栈共存有502个括号。
[4-12] 对异常输入的处置能力是衡量算法性能的重要方面，即教材1.1.4节所谓的鲁棒性。为考查教材95页代码4.7中evaluate()算法的这一性能，现以非正常的表达式"(12)3+!4+5"作为其输入。
[4-13] RPN表达式无需括号即可确定运算优先级，这是否意味着其所占空间必少于常规表达式？为什么？
[4-14] PostScript是一种典型的栈式语言，请学习该语言的基本语法，并编写简单的绘图程序。
[4-15] 为判断包含多种括号的表达式是否匹配，可否采用如下策略：
[4-16] 在N皇后搜索算法（教材101页代码4.9）中，“忒修斯的线绳”与“粉笔”各是通过什么机制实现的？
[4-17] 考查如教材103页代码4.13所示的迷宫寻径算法。
[4-18] Fermat-Lagrange定理指出，任何一个自然数都可以表示为4个整数的平方和，这种表示形式称作费马-拉格朗日分解，比如：30 = 12 + 22 + 32 + 42。
[4-19] 暂且约定按照自然优先级，并且不使用括号，考查在数字'0'~'9'间加入加号'+'、乘号'*'后所构成的合法算术表达式。
[4-20] 试从以下方面改进4.6.2节的银行服务模拟程序，使之更加符合真实情况：
[4-21] 自学C++ STL中stack容器和queue容器的使用方法，阅读对应的源代码。
[4-22] 双端队列（deque ）是常规队列的扩展。顾名思义，该结构允许在其逻辑上的两端实施数据操作。具体地，与队头（front）端和队尾（rear）端相对应地，插入和删除操作各设有两个接口：
[4-23] 从队列的角度回顾二路归并算法的两个版本，不难发现，无论Vector::merge()（教材63页代码2.29）还是List::merge()（教材82页代码3.22），所用到的操作无非两类：
[4-24] 基于向量模板类Vector实现栈结构时，为了进一步提高空间的利用率，可以考虑在一个向量内同时维护两个栈。它们分别以向量的首、末元素为栈底，并相向生长。
[4-25] 试设计并实现Stack::reverse()接口，将栈中元素的次序前后倒置。
[4-26] 试设计并实现Queue::reverse()接口，将队列中元素的次序前后倒置。
第5章 二叉树
[5-1] 考查任何一棵二叉树T。
[5-2] 考查任何一棵高度为h的二叉树T，设其中深度为k的叶节点有nk个，0 ( k ( h。
[5-3] 试证明，在二叉树中接入（attachAsLC()或attachAsRC()）或摘除（remove()或secede()）一棵非空子树之后
[5-4] 考查如教材121页代码5.6所示的BinTree::updateHeightAbove(x)算法。
[5-5] 教材123页代码5.9中的removeAt()算法，时间复杂度是多少？空间呢？
[5-6] 试证明，若采用PFC编码，则无论二进制编码串的长度与内容如何，解码过程总能持续进行((只有最后一个字符的解码可能无法完成。
[5-7] 因其解码过程不必回溯，PFC编码算法十分高效。然而反过来，这一优点并非没有代价。
[5-8] 在2.7.5节我们已经看到，CBA式排序算法在最坏情况下均至少需要((nlogn)时间，但这并不足以衡量此类算法的总体性能。比如，我们尚不确定，是否在很多甚至绝大多数其它情况下有可能做到运行时间足够少，从而能够使得平均复杂度更低。试证明：若不同序列作为输入的概率均等，则任何CBA式排序算法的平均运行时间依然为((nlogn)。（提示：PFC编码）
[5-9] 考查5.4.1节所介绍的各种递归式二叉树遍历算法。若将其渐进时间复杂度记作T(n)，试证明：
[5-10] 试按照消除尾递归的一般性方法，将二叉树先序遍历算法的递归版（教材124页代码5.11）改写为迭代形式。
[5-11] 考查教材5.4.2、5.4.3、5.4.4和5.4.5节所介绍的各种迭代式二叉树遍历算法。
[5-12] 对比教材中图5.15与图5.16不难发现，先序遍历与后序遍历在宏观次序上具有极强的对称性。 利用这种对称性，试仿照5.4.2节所给先序遍历算法的迭代版，实现后序遍历算法更多的迭代版。
[5-13] 试针对代码5.16中BinNode::succ()算法的两种情况，分别绘出一幅插图以说明其原理及过程。
[5-14] 仿照BinNode::succ()（教材130页代码5.16），实现二叉树节点直接前驱的定位接口BinNode::pred()。
[5-15] 按照本章实现的迭代式算法（代码x5.1、代码5.14、代码5.15、代码5.17和代码5.19）对规模为n的二叉树做遍历，辅助栈的容量各应取作多大，才不致出现中途溢出？
[5-16] 中序遍历迭代式算法的第三个版本（教材131页代码5.18），需反复地调用succ()接口以定位直接后继，从而会相应地增加计算成本。 试问，该算法的渐进时间复杂度是否依然保持为O(n)？若是，请给出证明；否则试举一例。
[5-17] 考查中序遍历迭代式算法的第三个版本（教材131页代码5.18）。
[5-18] 考查实现如134页代码5.20所示的层次遍历算法，设二叉树共含n个节点。
[5-19] 参考图5.26（教材135页）和图5.27（教材135页）中的实例，考查对规模为n的完全二叉树（含满二叉树）的层次遍历。
[5-20] 在完全二叉树的层次遍历过程中，按入队（亦即出队）次序从0起将各节点X编号为r(X)。
[5-21] 采用“父节点 + 孩子节点”方式表示和实现有根的有序多叉树，隶属于同一节点的孩子节点互为兄弟，且此处的有序性可以理解为“左幼右长”((位置偏左者为弟，偏右者为兄。实际上，这只是现代意义上对“弟”和“兄”的理解，具体到学源上师生关系，可对应于师弟、师兄。
[5-22] 考查借助二叉树，表示（有根有序）多叉树的长子-兄弟表示法：分别以左/右孩子作为长子/兄弟。
[5-23] 试在BinTree模板类（教材121页代码5.5）的基础上，扩展BinTree::swap()接口，在O(n)时间将二叉树中每一个节点的左、右孩子（其中之一可能为空）互换，其中n为树中的节点总数。
[5-24] 设二叉树共含n个节点，且各节点数据项的类型支持大小比较和线性累加（类似于整数或浮点数）。
[5-25] 设二叉树共含n个节点，且各节点数据项的类型支持大小比较（类似于整数或浮点数）。
[5-26] 设二叉树共含n个节点，且各节点数据项的类型支持线性累加（类似于整数或浮点数）。
[5-27] 试证明，在考虑字符的出现频率之后，最优编码树依然具有双子性。
[5-28] 试证明，5.5.4节所述Huffman编码算法的原理，对任意字符集均成立。
[5-29] 5.5.4节针对Huffman树构造算法的讲解中，暂时忽略了歧义情况。比如，有些字符的出现频率可能恰好相等；或者虽然最初的字符权重互异，但经过若干次合并之后，森林F也可能会出现权重相等的子树。另外，每次选出的一对（超）字符在合并时的左右次序也没有明确说明。
[5-30] 设字符表为(（|(| = r）。任一字符串集S都可如图x5.7所示，表示为一棵键树（trie） 。
第6章 图
[6-1] 关联矩阵（incidence matrix）是描述和实现图算法的另一重要方式。对于含有n个顶点、e条边的图，对应的关联矩阵I[][]共有n行e列。在无向图中，对于任意的0 ( i < n和0 ( j < e，若第i个顶点与第j条边彼此关联，则定义I[i][j] = 1；否则，定义I[i][j] = 0。
[6-2] 试说明，即便计入向量扩容所需的时间，就分摊意义而言，GraphMatrix::insert(v)算法的时间复杂度依然不超过O(n)。
[6-3] 所谓平面图，即可以将n个顶点映射为平面上的n个点，并且顶点之间的所有联边只相交于其公共端点，而不相交于边的内部。
[6-4] a） 试通过将无向图的二维邻接矩阵映射至一维向量，提高空间利用率。
[6-5] a） 试按照158页6.4节的思路，以邻接表的形式实现图ADT的各操作接口；
[6-6] 试基于BFS搜索设计并实现一个算法，在O(n + e)时间内将任一无向图分解为一组极大连通域。
[6-7] 若在图G中存在从顶点s通往顶点v的道路，则其中最短道路的长度称作s到v的（最小）距离，记作((v)；不存在通路时，取((v) = +(。试证明，在起始于s的广度优先搜索过程中：
[6-8] 若无向图中所有边的权重均相等，试基于广度优先搜索的框架设计并实现一个算法，在O(n + e)时间内计算出某一起始顶点到其余顶点的（最小）距离和一条（最短）通路。
[6-9] 在无向连通图中，最长的通路称作其直径（diameter）。试基于广度优先搜索的框架，设计并实现一个查找直径的算法，要求时间复杂度为O(n + e)。
[6-10] 试基于深度优先搜索的框架设计并实现一个算法，在O(n + e)时间判定任一无向图是否存在欧拉环路；并且在存在时，构造出一条欧拉环路。
[6-11] BFS算法（教材160页代码6.3）的边分类，采用了简化的策略：
[6-12] 考查采用DFS算法（教材162页代码6.4）遍历而生成的DFS树。试证明：
[6-13] 在起始于顶点s的DFS搜索过程中的某时刻，设当前顶点为v。试证明，任一顶点u处于DISCOVERED状态，当且仅当u来自s通往v的路径沿途((或者等效地，在DFS树中u必为v的祖先。
[6-14] 通过显式地维护一个栈结构，将DFS算法（教材162页代码6.4）改写为迭代版本。
[6-15] 为将顶点及边的状态标志复位，本章所给的Graph::reset()需要耗费O(v + e)时间。 试设计一种方法，将这部分时间降低至O(v)。
[6-16] a）试说明，对于整数权重的网络，可通过足够小的扰动，在不影响Prim算法正确性、计算过程及复杂度的前提下，消除由（同为某一割的极短跨越边的）重复边引起的歧义。
[6-17] 在教材176页图6.20中，出于简洁的考虑，将通路us和vt分别画在构成割的两个子图中。然而这样有可能造成误解，比如读者或许会认为，组成这两条通路的边也必然分别归属于这两个子图。
[6-18] 利用“有向无环图中极大顶点入度必为零”的性质，实现一个拓扑排序算法，若输入为有向无环图则给出拓扑排序，否则报告“非有向无环图”。该算法时间、空间复杂度各是多少？
[6-19] a） 试从教材167页代码6.5中，删除与拓扑排序无关的操作，以精简其实现；
[6-20] a） 试从教材170页代码6.6中，删除与双连通分量分解无关的操作，以精简其实现；
[6-21] 试按照PFS搜索的统一框架（教材173页代码6.7），通过设计并实现对应的prioUpdater函数对象，分别实现BFS和DFS算法。
[6-22] 所谓旅行商问题，要求在任意n个城市的所有哈密尔顿环路中，找出总交通成本最低者。该问题属于经典的NPC问题，多数学者相信不存在多项式算法。
[6-23] 合成数（composite number）法，是消除图算法歧义性的一种通用方法。
[6-24] 考查某些边的权重不是正数的带权网络。试证明：
[6-25] 各边权重未必互异时，带权网络的“最小生成树”未必唯一，故应相应地，将其改称作“极小支撑树”更为妥当。对于任一此类的带权网络G，试证明：
[6-26] 试举例说明，在允许多边等权的图G中，即便某棵支撑树T的每一条边都是G某一割的极短跨越边，T也未必是G的极小支撑树。
[6-27] 试证明，尽管在允许多边等权时，同一割可能同时拥有多条最短跨越边，6.11.5节中Prim算法所采用的贪心迭代策略依然行之有效。（提示：只需证明，只要Tk是某棵极小支撑树的子树，则Tk+1也必是（尽管可能与前一棵不同的）某棵极小支撑树的子树）
[6-28] Joseph Kruskal于1956年[31]提出了构造极小支撑树的另一算法：
[6-29] 试举例说明，在最坏情况下，Kruskal算法的确可能需要检查((n2)条边。
[6-30] 若将森林中的每棵树视作一个等价类，则Kruskal算法迭代过程所涉及的计算不外乎两类：
[6-31] 试举例说明，即便带权网络中不含权重相等的边，其最短路径树依然可能不唯一。
[6-32] 若图G的顶点取自平面上的点，各顶点间均有联边且权重就是其间的欧氏距离，则G的最小支撑树亦称作欧氏最小支撑树（ Euclidean Minimum Spanning Tree, EMST)，记作EMST(G)。
第7章 搜索树
[7-1] 试证明，一棵二叉树是二叉搜索树，当且仅当其中序遍历序列单调非降。
[7-2] 试证明，由一组共n个互异节点组成的二叉搜索树，总共有(2n)!/n!/(n + 1)!棵。
[7-3] 试证明，含n个节点的二叉树的最小高度为(log2n(((这也是由n个节点组成的完全二叉树高。
[7-4] 与其它算法类似，searchIn()算法的递归版（教材186页代码7.3）也存在效率低下的问题。
[7-5] 试证明，采用BST::insert()算法（教材188页代码7.5），在二叉搜索树中插入节点v之后
[7-6] 试证明，采用BST::remove()算法（教材190页代码7.6）从二叉搜索树中删除节点，若实际被删除的节点为x，则此后：
[7-7] 利用以上事实，进一步改进updateHeightAbove()方法，提高效率。
[7-8] a） 试按照随机生成和随机组成两种方式，分别进行实际测试，并统计出二叉搜索树的平均高度；
[7-9] BinTree::removeAt()算法（教材190页代码7.7）的执行过程中，当目标节点同时拥有左、右孩子时，总是固定地选取直接后继与之交换。于是，从二叉搜索树的整个生命期来看，左子树将越来越倾向于高于右子树，从而加剧整体的不平衡性。
[7-10] 为使二叉搜索树结构支持多个相等数据项的并存，需要增加一个BST::searchAll(e)接口，以查找出与指定目标e相等的所有节点（如果的确存在）。
[7-11] 考查包含n个互异节点的二叉搜索树。
[7-12] 试证明，在高度为h的AVL树中，任一叶节点的深度均不小于(h/2(。
[7-13] 试证明：
[7-14] 按照教材第7.3.4节的定义和描述，实现节点旋转调整算法zig()和zag()。
[7-15] 试证明：
[7-16] 为使AVL树结构支持多个相等数据项的并存，需要增加一个AVL::searchAll(e)接口，以查找出与指定目标e相等的所有节点（如果的确存在）。
[7-17] 试证明，对于任意大的正整数n，都存在一棵规模为n的AVL树，从中删除某一特定节点之后，的确需要做((logn)次旋转，方能使全树恢复平衡。
[7-18] D. E. Knuth[3]曾指出，AVL::remove()操作尽管在最坏情况下需做((logn)次旋转，但平均而言仅需做0.21次。试通过实验统计，验证这一结论。
[7-19] 设在从AVL树中摘除一个节点之后，刚刚通过调整使g(x)重新恢复了平衡。此时，若发现g(x)原先的父节点依然平衡，则是否可以不必继续检查其更高层的祖先，并随即停止上溯？
[7-20] 试证明，按递增次序将2h+1 - 1个关键码插入初始为空的AVL树中，必然得到高度为h的满树。
第8章 高级搜索树
[8-1] 试扩充Splay模板类（教材208页代码8.1），使之支持多个相等数据项的并存。
[8-2] 试证明，伸展树所有基本操作接口的分摊时间复杂度，均为O(logn)。
[8-3] 试扩充RedBlack模板类（教材230页代码8.13），使之支持多个相等数据项的并存。
[8-4] 试对于任何指定的m和N，构造一棵存有N个关键码的m阶B树，使得在其中插入某个特定关键码之后，需要进行((logmN)次分裂。
[8-5] 现拟将一组共n个互异的关键码，插入至一棵初始为空的m阶B-树中，设m << n。
[8-6] 考查任意阶的B-树T。
[8-7] 设m ( 3为奇数。试对任意的h > 0，构造一棵高度为h的m节B-树，使得若反复地对该树交替地执行插入、删除操作，则每次插入或删除操作都会引发h次分裂或合并。
[8-8] 对比本章所介绍的B-树插入与删除算法后不难发现，二者并不完全对称。
[8-9] 极端情况下，B-树中根以外所有节点只有(m/2(个分支，空间使用率大致仅有50%。而若按照教材8.2节介绍的方法，简单地将上溢节点一分为二，则有较大的概率会出现或接近这种极端情况。
[8-10] Java语言所提供的java.util.TreeMap类是用红黑树实现的。 试阅读相关的Java源代码，并就其实现方式与本章的C++实现做一比较。
[8-11] H. Olivie于1982年提出的半平衡二叉搜索树（half-balanced binary search trees）[47]，非常类似于红黑树。这里所谓的半平衡（half-balanced），是指此树的什么性质？
[8-12] 人类所拥有的数字化数据的总量，在2010年已经达到ZB（2^70 = 10^21）量级。 假定其中每个字节自成一个关键码，若用一棵m = 256阶的B-树来存放它们，则
[8-13] 考查含有2012个内部节点的红黑树。
[8-14] 就最坏情况而言，红黑树在其重平衡过程中可能需要对多达((logn)个节点做重染色。然而，这并不足以代表红黑树在一般情况下的性能。
[8-15] 试证明，若中位点能够在线性时间内确定，则kd-树构造算法buildKdTree()（242页算法8.1）的总体执行时间可改进至O(nlogn)，其中n = |P|为输入点集的规模。
[8-16] 关于kd-树查找算法kdSearch()（教材244页算法8.2），试证明以下结论：
[8-17] 不难理解，kd-树中节点v所对应的矩形区域即便与查询范围R相交，其中所含的输入点也不见得会落在R之内。比如在极端的情况下，v中可能包含大量的输入点，但却没有一个落在R之内。当然，kdSearch()（教材244页算法8.2）在这类情况下所做的递归，都是不必进行的。
[8-18] 若仅需报告落在指定范围内点的数目，而不必给出它们的具体信息，则借助kd-树需要多少时间？
[8-19] 四叉树[51]（quadtree）是2d-树的简化形式，其简化策略包括：
[8-20] 范围查询的另一解法需要借助范围树（range tree）[48]。
第9章 词典
[9-1] 阅读教材代码9.7（253页）、代码9.8（255页）和代码9.11（258页）。 试验证：本章所实现的跳转表结构，可保证雷同的词条在内部按插入次序排列，同时对外先进先出。
[9-2] 本章所实现的跳转表结构中，每个词条都在所属的塔内同时保留了多个副本。尽管这样可以简化代码描述，但毕竟浪费了大量的空间，在词条本身较为复杂时由其如此。 试在本章相关代码的基础上就此做一改进，使得每座塔仅需保留一份对应的词条。
[9-3] W. Pugh曾经通过实验统计，将skiplist（A）与非递归版AVL树（C）、伸展树（B）、递归版(2, 3)-树（D）等数据结构做过对比，并发现了以下规律：
[9-4] 为便于客户记忆，许多商家都将其产品销售咨询电话号码与公司或产品的名称直接关联。其中最流行的一种做法可以理解为，在电话键盘的拨号键与数字之间建立一个散列映射：
[9-5] 实际上早在上世纪70年代，Bell实验室就已采用上题中的散列映射法，根据员工的姓名分配办公电话，且可轻松地将发生冲突的概率降至0.2%以下。
[9-6] 假定散列表长度为M，采用模余法。若从空开始将间隔为T的M个关键码插入其中。
[9-7] 我们已经看到，散列表长度M是影响散列效果的重要因素之一。
[9-8] 试证明，23人中存在生日巧合的概率大于50%。
[9-9] 在本章示例代码的基础上进行扩充，实现线性试探以外的其它冲突排解策略。
[9-10] 若允许关键码雷同的词条并存，本章实现散列表结构的示例代码应该如何修改？
[9-11] 创建散列表结构时，通常首先需要初始化所有的桶单元。尽管如265页代码9.14所示，这可以借助系统调用memset()实现，但所需的时间将线性正比于散列表的长度。
[9-12] a） 在平方试探法、（伪）随机试探法等方法中，查找链如何构成？
[9-13] 在实现平方试探法时，可否只使用加法而避免乘法（平方）运算？如果可以，试给出具体方法。
[9-14] 考查单向平方试探法，设散列表长度取作素数M > 2。试证明：
[9-15] a） 试举例说明，散列表长度M为合数时，即便装填因子低于50%，平方试探仍有可能无法终止；
[9-16] 懒惰删除法尽管具有实现简明的优点，但随着装填因子的增大，查找操作的成本却将急剧上升。 为克服这一缺陷，有人考虑在本章所给示例代码的基础上，做如下调整：
[9-17] 所谓双向平方试探法，是平方试探法的一种拓展变型。
[9-18] 设散列表H容量为11且初始为空，采用除余法确定散列地址，采用单向平方试探法排解冲突，采用懒惰策略实现删除操作。
[9-19] a） 试在图结构的邻接表实现方式中，将每一列表替换为散列表；
[9-20] a） 了解C#所提供GetHashCode()方法的原理，并尝试利用该方法转换散列码；
[9-21] 考查教材9.4.1节介绍的基本桶排序算法。
[9-22] 任给来自于[0, nd)范围内的n个整数，其中常数d > 1。
[9-23] 若将任一有序序列等效地视作有序向量，则其中每个元素的秩，应恰好就等于序列中不大于该元素的元素总数。例如，其中最小、最大元素的秩分别为0、n - 1，可以解释为：分别有0和n - 1个元素不大于它们。根据这一原理，只需统计出各元素所对应的这一指标，也就确定了它们在有序向量中各自所对应的秩。
[9-24] 习题[4-18]（100页）曾指出，同一整数可能同时存在多个费马-拉格朗日（Fermat-Lagrange）分解，其中，四个整数之和最小者称作最小分解。比如： 101 = 02 + 02 + 12 + 102 = (0, 0, 1, 10) = 02 + 12 + 62 + 82 = (0, 1, 6, 8) = 02 + 22 + 42 + 92 = (0, 2, 4, 9) = 02 + 42 + 62 + 72 = (0, 4, 6, 7) = 22 + 52 ɡ
[9-25] 散列技术在信息加密领域有着广泛应用，比如数字指纹的提取与验证。试通过查阅资料和编程实践：
[9-26] 当元素类型为字符串时，为避免复杂的散列码转换，可以改用键树（trie）结构来实现词典ADT。
第10章 优先级队列
[10-1] a） 试按照代码10.1中的ADT接口，分别基于无序、有序列表和无序、有序向量实现优先级队列；
[10-2] 基于向量实现完全二叉堆时，也可在向量中将各节点顺次后移一个单元，并在腾出的首单元中置入对应元素类型的最大值作为哨兵（比如，对于整型可取INT_MAX）。如此，虽然多使用了一个单元，但在上滤过程中只需比较父子节点的大小，而无需核对是否已经越界。
[10-3] 如教材代码10.7、代码10.9实现的percolateUp、percolateDown算法中，若实际上升或下降k = O(logn)层，则k次swap()操作共需3k次赋值。
[10-4] a） 试证明，在从堆顶通往任一叶节点的沿途上，各节点对应的关键码必然单调变化；
[10-5] 在摘除原堆顶元素后，为恢复堆的结构性，为何采用如教材292页代码10.9所示的percolateDown()算法，而不是自上而下地，依次以更大的孩子节点顶替空缺的父节点？
[10-6] 针对如教材第290页代码10.7所示的percolateUp()上滤算法，10.2.2节曾指出其执行时间为O(logn)。然而，这只是对其最坏情况的估计；在通常的情况下，实际的效率要远高于此。
[10-7] Floyd建堆算法中，同层内部节点下滤的次序
[10-8] 借助优先级队列高效的标准接口，教材285页代码10.2中的generateTree()算法即可简明地在O(nlogn)时间内构造出n个字符的Huffman编码树。然而，这还不足以说明这一实现已属最优。
[10-9] 在附加某些特定条件之后，问题的难度往往会有实质的下降。比如，若待编码字符集已按出现频率排序，则Huffman编码可以更快完成。在编码过程中，始终将森林F中的树分为两类：单节点（尚未参与合并）和多节点（已合并过）。每经过一次迭代，后者虽不见得增多，但必然有一个新成员。
[10-10] 试利用本章所介绍的各种堆结构，与如代码10.2（教材285页）所示的Huffman树统一构造算法generateTree()一起编译、链接、执行，并就其性能做一统计、对比和分析。
[10-11] 与AVL树需要借助bf记录类似，左式堆也需要设置npl记录。然而在实际应用中，这一点既不自然，也影响代码开发与转换的效率。实际上，仿照由AVL树引出伸展树的思路，可以在保留左式堆优点的前提下消除npl记录，新的结构称作斜堆（skew heap）。
[10-12] 某些应用可能要求堆结构提供更多接口，比如提升或降低堆中任一指定词条的优先级。尽管此类调整并不影响堆的结构性，但往往会破坏堆序性，故也需要及时调整并使之恢复为合法的堆结构。
[10-13] 在本章所给的左式堆模板类中（教材298页代码10.12），建堆操作仅实现了蛮力的O(nlogn)算法。试采用Floyd建堆算法，将这一操作的效率改进至O(n)。
[10-14] 教材10.2.5节实现的就地堆排序是稳定的吗？若是，请给出证明；否则，试举一实例。
[10-15] 如教材302页代码10.13所示的左式堆合并算法，采用了递归模式。尽管如此已足以保证合并操作的渐进时间复杂度为O(logn)，但为进一步提高实际运行效率，试将该算法改写为迭代模式。
[10-16] 若能注意到教材6.11.5节Prim算法中定义的“优先级数”恰好对应于优先级队列中元素的优先级，即可利用本章介绍的优先级队列，改进如教材177页代码6.8所示的O(n2)版本。
[10-17] 在多叉堆（d-heap）中，每个节点至多可拥有d ( 3个孩子，且其优先级不低于任一孩子。
[10-18] 所谓半无穷范围查询（semi-infinite range query），是教材8.4节中所介绍一般性范围查询的特例。具体地，这里的查询区域是某一侧无界的广义矩形区域，比如R = [-1, +1] ( [0, +()，即是对称地包含正半y坐标轴、宽度为2的一个广义矩形区域。当然，对查询的语义功能要求依然不变((从某一相对固定的点集中，找出落在任意指定区域R内部的所有点。
[10-19] 试为第4章栈结构增加Stack::getMax()接口，以在O(1)时间内定位并读取栈中的最大元素。
[10-20] 试为第4章的队列结构增加Queue::getMax()接口，在O(1)时间内定位并读取其中最大元素。
[10-21] 任给高度分别为g和h的两棵AVL树S和T，且S中的节点均不大于T中的节点。
[10-22] 任给高度为h的一棵AVL树A，以及一个关键码e。
第11章 串
[11-1] 在微软Office套件中，Excel针对字符串操作提供了一系列的函数。
[11-2] 考查教材309页代码11.1和310页代码11.2中，match()算法的两个版本。
[11-3] 考查由26个大写英文字母组成的字母表。
[11-4] 为评估KMP算法的效率，11.3.7节引入一个随迭代过程严格单调递增的观察量k = 2i - j，从而简捷地证明了迭代的次数不可能超过O(n)。这一初等的证明虽无可辩驳，但毕竟未能直观地展示出其与计算成本之间的本质联系。
[11-5] 针对坏字符在模式串P中位置太靠右，以至位移量为负的情况，11.4.2节建议的处理方法是直接将P右移一个字符。然而如图11.10(f)所示，此后并不能保证原坏字符位置能够恢复匹配。为此，或许你会想到：可在P[j]的左侧找到最靠右的字符'X'，并将其与原坏字符对齐。
[11-6] 考查GS[]表构造算法（教材326页代码11.8），记模式串的长度|P| = m。试证明：
[11-7] 在模式枚举（pattern enumeration）类应用中，需要从主串T中找出所有的模式串P（|T| = n，|P| = m），而且有时允许模式串的两次出现位置之间相距不足m个字符。
[11-8] 在讲解GS[]表的构造算法时，为简洁起见，教材图11.14、图11.15和图11.16中所绘出MS[j]均与其所对应的最长匹配后缀没有任何重叠。然而，这种表示方法并不足以代表一般性的情况。
[11-9] 教材309页代码11.1、310页代码11.2所实现的两个蛮力算法，在通常情况下的效率并不算低。 现假定所有字符出现的概率均等，试证明：
[11-10] BM算法与KMP算法分别擅长于处理何种类型的字符串？为什么？
第12章 排序
[12-1] 构造轴点的另一更为快捷的策略，思路如图x12.1所示：
[12-2] 考查majEleCandidate()算法（教材343页代码12.6）的返回值maj。
[12-3] 按照教材12.2.2节的定义，众数应严格地多于其它元素。若将“多于”改为“不少于”，则
[12-4] 在微软Office套件中，Excel提供了一系列的统计查询函数。
[12-5] 实际上，trivialMedian()算法（教材343页代码12.7）只需迭代(n1 + n2)/2步即可终止。
[12-6] 如教材344页代码12.8所示的median()算法属于尾递归形式，试将其改写为迭代形式。
[12-7] 如教材346页代码12.9所示的median()算法，针对两个向量长度相差悬殊的情况做了优化处理。
[12-8] 若输入的有序序列S1和S2以列表（而非向量）的方式实现，则：
[12-9] 若输入的有序序列S1和S2以平衡二叉搜索树（而非序列）的方式给出，则：
[12-10] a） 基于教材346页代码12.9中的median()算法，添加整型输入参数k，实现在S1(S2中选取第k个元素的功能；
[12-11] 考查如教材348页代码12.10所示的quickSelect()算法。
[12-12] 如图x12.2所示，设有向量X[0, m + r)和Y[0, r + n)，且满足： 对于任何0 ( j < r，都有Y[j] ( X[m + j]
[12-13] 试证明，g-有序的向量再经h-排序之后，依然保持g-有序。
[12-14] 设使用Pratt序列：
附录
参考文献
插图索引
表格索引
算法索引
代码索引
关键词索引
习题汇总
目录