数据结构习题解析（C++语言版）

    §3.1 从向量到列表
    §3.2 接口
    §3.3 列表
    §3.4 有序列表
    §3.5 排序器
第4章 栈与队列
    §4.1 栈
    §4.2 栈与递归
    §4.3 栈的典型应用
    §4.4 *试探回溯法
    §4.6 队列应用
第5章 二叉树
    §5.1 二叉树及其表示
    §5.2 编码树
    §5.3 二叉树的实现
    §5.4 遍历
    §5.5 Huffman编码
第6章 图
    §6.1 概述
    §6.2 抽象数据类型
    §6.3 邻接矩阵
    §6.5 图遍历算法概述
    §6.6 广度优先搜索
    §6.7 深度优先搜索
    §6.11 最小支撑树
    §6.12 最短路径
第7章 搜索树
    §7.1 查找
    §7.2 二叉搜索树
    §7.3 平衡二叉搜索树
    §7.4 AVL树
第8章 高级搜索树
    §8.1 伸展树
    §8.2 B-树
    §8.3 *红黑树
    §8.4 *kd-树
第9章 词典
    §9.1 词典ADT
    §9.2 *跳转表
    §9.3 散列表
    §9.4 *散列应用
第10章 优先级队列
    §10.1 优先级队列ADT
    §10.2 堆
    §10.3 *左式堆
第11章 串
    §11.1 串及串匹配
    §11.3 KMP算法
    §11.4 *BM算法
    §11.5 *Karp-Rabin算法
第12章 排序
    §12.1 快速排序
    §12.2 *选取与中位数
    §12.3 *希尔排序
附录
    参考文献
    内容简介
数据结构习题解析（C++语言版）
第1章 绪论
    [1-25] 《九章算术》记载的“中华更相减损术”可快速地计算正整数a和b的最大公约数，其过程如下：
    [1-27] 试实现一个递归算法，对任意非负整数m和n，计算以下Ackermann函数值：
    [1-28] 考查所谓咖啡罐游戏（Coffee Can Game）：在咖啡罐中放有n颗黑豆与m颗白豆，每次取出两颗：若同色，则扔掉它们，然后放入一颗黑豆；若异色，则扔掉黑豆，放回白豆。
    [1-29] 序列Hailstone(n)是从n开始，按照以下规则依次生成的一组自然数：
    [1-30] 在分析并界定其渐进复杂度时，迭代式算法往往体现为级数求和的形式，递归式算法则更多地体现为递推方程的形式。针对这两类主要的分析技巧，参考文献[7]做了精辟的讲解和归纳。试研读其中的相关章节。
第2章 向量
    [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-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式算法，最坏情况下至少需做几次比较？为什么？
第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()。
第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″作为其输入。
第5章 二叉树
    [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编码算法的原理，对任意字符集均成立。
第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-8] 若无向图中所有边的权重均相等，试基于广度优先搜索的框架设计并实现一个算法，在O(n + e)时间内计算出某一起始顶点到其余顶点的（最小）距离和一条（最短）通路。
    [6-9] 在无向连通图中，最长的通路称作其直径（diameter）。试基于广度优先搜索的框架，设计并实现一个查找直径的算法，要求时间复杂度为O(n + e)。
    [6-11] BFS算法（教材160页代码6.3）的边分类，采用了简化的策略：
    [6-12] 考查采用DFS算法（教材162页代码6.4）遍历而生成的DFS树。试证明：
    [6-14] 通过显式地维护一个栈结构，将DFS算法（教材162页代码6.4）改写为迭代版本。
    [6-15] 为将顶点及边的状态标志复位，本章所给的Graph::reset()需要耗费O(v + e)时间。 试设计一种方法，将这部分时间降低至O(v)。
    [6-16] a）试说明，对于整数权重的网络，可通过足够小的扰动，在不影响Prim算法正确性、计算过程及复杂度的前提下，消除由（同为某一割的极短跨越边的）重复边引起的歧义。
    [6-19] a） 试从教材167页代码6.5中，删除与拓扑排序无关的操作，以精简其实现；
    [6-20] a） 试从教材170页代码6.6中，删除与双连通分量分解无关的操作，以精简其实现；
    [6-21] 试按照PFS搜索的统一框架（教材173页代码6.7），通过设计并实现对应的prioUpdater函数对象，分别实现BFS和DFS算法。
第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相等的所有节点（如果的确存在）。
第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-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-树来存放它们，则
第9章 词典
    [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 + 62ɡ
    [9-25] 散列技术在信息加密领域有着广泛应用，比如数字指纹的提取与验证。试通过查阅资料和编程实践：
    [9-26] 当元素类型为字符串时，为避免复杂的散列码转换，可以改用键树（trie）结构来实现词典ADT。
第10章 优先级队列
    [10-20] 试为第4章的队列结构增加Queue::getMax()接口，在O(1)时间内定位并读取其中最大元素。
第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个字符。
第12章 排序
    [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-14] 设使用Pratt序列：
附录
    参考文献