912DSA 习题集 第5章 二叉树(个人理解版) 912DSA 习题集 第5章 二叉树 前言 本人为24年thu912考生，以下为我学习DSA习题解析中的理解和感悟，欢迎大家批评指正！ 5-1 题目大意总结： 考察任何一棵二叉树T a 试证明，对于其中任一结点
, 总有depth() + height() height() 分析： 感觉结论很直观，但是证明。。。 还是看一下解析中给的证明吧： 这里就不写那么多符号来表示，直接上核心思想： 简单来说，是取的树中最深的的深度 而是取的的子树中最深的的深度 显然前者包含后者 b 以上取等号的充要条件是？ 分析： 该结点在最深叶节点的那条路径上。(是最深叶结点的祖先) 5-2 题目大意总结： 考查任何一棵高度为的二叉树，设其中深度为的叶结点有个， a 试证明： 分析： 采用数学归纳法，对树高做归纳。在时，对于单结点的二叉树成立。 下面假设对于高度小于的二叉树，该不等式均成立，下面考察高度为的二叉树。 该树在最底层拥有恰好个叶结点，若将他们统一删除，则只可能在原次底层(现最底层)增加叶结点，其余更高层的叶节点不增不减。准确地说，若原次底层新增叶节点共个，则必有 这是由于可能对于上一层的结点，这一层可能有1个孩子叶子，也有可能有2个孩子叶子。 反过来， 如此，经统一删除底层叶结点后，所得到的二叉树的高度为，由归纳假设应当满足： 如此以来，对于原树有： 其实这里的证明的关键就在于，以及次底层删除之后的结点个数为个 b 以上不等式取等号的充要条件是什么 分析： 取等号意味着 也就是每个删除的叶子结点的父亲都有两个叶子孩子，即指该树为真二叉树 5-3 题目大意总结： 试证明，在二叉树中插入或摘除一棵非空子树之后 a 该子树所有祖先的后代数目必然变化 分析： 这感觉显然 b 该子树所有祖先的高度可能变化 分析： 如果说是最深叶子结点，那么就会变，否则不变。 c 对于非该子树祖先的任何结点，高度与后代数目均保持不变 分析： 由“祖先-后代”关系的相对性，显然。 5-4 题目大意总结： 考察P121页5.6所示的BinTree::updateHeightAbove(x)算法。 a 试证明，在逆行向上依次更新x各祖先高度的过程中，一旦发现某一祖先的高度没有发生变化，算法即可提前终止 分析： 记首个高度不变的结点记为C。 考察任一更高的祖先结点A。若从A通往其最深后代的通路不经过C，则A的高度自然不变；若从A通往其最深后代的通路通过C，那由于C告诉不变，A高度自然也不变。 b 试按此思路改进这一算法： 分析： 只需要加判断，当某一结点高度不变化时，即停止。 c 如此改进之后，算法的渐进复杂度是否会相应降低？ 分析： 不会，在最坏情况下依然需要更新到根部，但常系数得到了优化。 5-5 题目大意总结： 教材P123页5.9中的removeAt()算法，时间复杂度是多少？空间呢？ 分析： 对于待删除子树中的每一结点，都有一个递归实例。故时间复杂度线性正比于待删除子树的规模。 递归调用时空间复杂度正比于树的高度。 5-6 题目大意总结： 试证明，若采用PFC编码，则无论二进制编码串的长度与内容如何，解码过程总能持续进行——只有最后一个字符的解码可能无法完成。 分析： 由于PFC都是真二叉树，也就是说对于每一内部结点，都有左、右分支,那么必然能达到叶子。 但对于错误的数据，最后一个字符的解码可能无法完成。 这里列举一个室友给出的例子： 比如我现有的信息流是 , 我现有的编码是 10:”g” 110:”o”, 111:”a” 它会译出go，最后剩下一个11，没办法解码 5-7 题目大意总结： 因解码过程不必回溯，所以PFC编码算法十分高效。但这一优点并非没有代价。 试举例说明，如果因为信道干扰等影响致使某个比特位翻转错误，尽管解码依然可进行下去，但后续所有字符的解码都会出现错误。 分析： 这里的例子应该蛮容易理解，不再赘述。 5-8 题目大意总结： 在2.7.5节我们已经看到,CBA式排序算法在最坏情况下至少需要时间，但这并不足以衡量此类算法的总体性能。比如，我们尚不确定，是否在很多甚至绝大多数情况下有可能做到运行时间足够少，从而使得平均复杂度更低。试证明：若不同序列作为输入的概率均等，则任何CBA式排序算法的平均运行时间依然为 分析： 此处所需考察的是，在各种输出结果符合某种概率分布的前提下，算法的平均性能。 这实际上等效于考察比较树中各叶结点的加权平均深度，其中各叶结点的权重取作出现对应输出的概率。 特别的，在各种输出结果概率均等的前提下，对于任一固定的输入规模,完全二叉树的叶结点平均深度可达最小——然而即便如此，也至少有 5-9 题目大意总结： 考察5.4.1节所介绍的各种递归式二叉树遍历算法。若将其渐进时间复杂度记为，试证明： 分析： 这些算法都属于二分递归问题，每次递归都等效于将当前问题分解为两个子问题，那么其实就满足一种递推关系，其实可以类比Fibonacci的迭代式求法或者dfs记忆化搜索，时间复杂度都是 5-10 题目大意总结： 试按照消除尾递归的一般性方法，将二叉树先序遍历的递归版本改写为迭代形式。 分析： 这里需要用栈来保存一下孩子 核心代码： 这里先入右孩子就非常精髓，因为下次先访问的是左孩子。 5-11 题目大意总结： 考察5.4.2，5.4.3，5.4.4和5.4.5节所介绍的各种迭代式二叉树遍历算法 a 试证明，这些算法都是正确的，的确会访问每个结点一次且仅一次 分析： 发现两点事实即可：只要某个结点能被访问到，则其孩子结点必然也能每个结点都在且仅在刚刚出栈(队)后，随即被访问 b 试证明，无论递归式或迭代式，这些算法都具有线性时间复杂度 分析： 每个结点仅访问一次，自然是线性时间复杂度 c 空间复杂度呢？ 分析： 主要看辅助空间把，通常是，不需要硬记，如果考到现场推即可。 5-12 题目大意总结： 对比教材图5.15与图5.16不难发现，先序遍历与后序遍历在宏观次序上具有极强的对称性。利用这种对称性，试仿照5.4.2节所给先序遍历算法的迭代版，实现后序遍历算法更多的迭代版： 分析： 不大懂这里说的是什么，那还不如学习一遍书中的后序遍历的迭代算法： 5-13 题目大意总结： 试针对代码5.16中BinNode::succ()算法的两种情况，分别绘出一幅插图以说明其原理及过程： 分析：
感觉还是比较容易理解的：如果有右孩子，那么就是右孩子中的最左结点否则，就是包含于其左子树的最低祖先 5-14 题目大意总结： 仿照BinNode::succ()，实现BinNode::pred() 分析： 仿照succ的思想，pred应当存在两种情况：如果有左孩子，那就是左子树中的最右结点否则，应当是将当前结点包含于其右子树的最低公共祖先 5-15 题目大意总结： 按照本章实现的迭代式算法，对规模为n的二叉树做遍历，辅助栈的容量应取多大，才不至于出现中途溢出？ 分析： 最坏的情况下，树退化为链，这个时候需要的辅助空间 5-16 题目大意总结： 中序遍历迭代式算法的第三个版本(P131页代码5.18)，需要反复调用succ()接口，从而相应地增加计算成本。 试问，该算法的渐进时间复杂度是否依然为？ 分析： 首先先抄一遍代码，加深理解： 这里我们需要注意的是关于succ函数的调用时机，并不是对于每个结点都会调用succ函数，观察代码可以发现，只有在回溯状态并且无右孩子时才会调用succ函数，在这种情况下，其实就只是返回的当前结点的parent。 具体而言这里还是通过数学归纳法，可以证明渐进时间复杂度不超过 5-17 题目大意总结： 考察中序遍历迭代式算法的第三个版本，P131页代码5.18，试继续改进该算法，使之不仅无需辅助栈，而且也无需辅助标志位 分析： 这里的关键是利用了succ()的性质，结点的后继满足二者在中序遍历序列中的顺序，感觉这种方式有点思路清晰，如果有右子树，那直接转到右子树，否则，直接寻找其后继。 感觉这种方式有点快接近直接按succ()进行中序遍历。 相对前面的方式，逻辑更清晰。下面我们来分析下何时会调用succ()函数： 似乎这里我们也只会在当前结点没有右子树时才会调用succ()函数，而显然这种情况下，它的后继必然是将其作为左子树的最低祖先，看起来也不会调用很多次，时间复杂度仍渐进于线性，只是常数可能较之前略大。 5-18 题目大意总结： 考察实现如P134页代码5.20所示的层次遍历算法，设二叉树共含个结点 a 试证明，只要辅助队列Q的容量不低于，就不至于出现中途溢出问题 分析： 可以发现如果有个结点入过队，那么队中最多有个结点 具体的，每次迭代都有一个结点出队，有个结点出队。 用数学归纳法易证结论的正确性 b 在规模为的所有二叉树中，那些的确会需要如此大容量的辅助队列？ 分析： 很容易想到这个时候最好每个结点都有俩孩子，因为这样每次入队的是最多的。 那么对于这一类二叉树，我们称之为完全二叉树 c 在层次遍历过程中，若Q中结点的总数的确会达到这么多，则至多可能达到多少次？ 分析： 这里首先要满足是完全二叉树，因此我们可以计算出叶子结点数为个 显然这里只需要考虑内部结点最后一层的最后一次结点插入的情况。若最后一个结点是有一个孩子，那么情况会出现两次(这个结点在队首以及第一个叶子结点在队首)；若最后一个结点是有两个孩子，那么情况会出现一次(第一个叶子结点在队首) 前面的情况下为偶数，后者为奇数 可以这样想来方便记忆：如果是偶数，除2是整的，相当于取两侧；如果是奇数，除2不整，那只有一次。 5-19 题目大意总结： 参考P135页的图5.26和图5.27中的实例，考察对规模为的完全二叉树的层次遍历 a 试证明：在整个遍历过程中，辅助队列的规模变化是单峰对称的，即： n为奇数时： {} n为偶数时：{} 分析： 由习题[5-18]易得到该结论 b 非完全二叉树的层次遍历过程中，是否也可能具有该性质？ 分析： 对非完全二叉树遍历过程中，辅助队列规模不可能达到 这里可以定性地很容易看出来，非完全二叉树中次外层结点数必然少于完全二叉树，至少少1个，而对于完全二叉树而言，需要这个结点才可能达到 5-20 题目大意总结： 在完全二叉树的层次遍历过程中，按入队次序从0起将各结点编号为. a 试证明： 对于任一结点X及其左右孩子L和R，必然有： 分析： 该结论应该挺容易看出，用太多了。 b 试证明： 任一编号都唯一对应于某个结点 分析： 这有点没懂。感觉肯定的呀？ c 很多应用往往仅涉及完全二叉树，此时，如何利用上述性质提高对树的存储和处理效率？ 分析： 常用向量来存储二叉树，可以通过秩来快速访问完全二叉树中的结点。 d 根据以上编号规则，如何判断任何一对结点是否存在”祖先-后代“关系？ 分析： 我们使用完全二叉树时，秩常从1开始，而非0 因为采用这种方式后： 若令 如果结点A是D的祖先，当且仅当其秩是后者的前缀如果结点A是D的父亲，当且仅当 对于第二点，也很好说明，首先必然是取得的除最后一位的前缀 那么对于来讲，它的孩子无外乎右移一位，再加1或者加0，自然包含 5-21 题目大意总结： 考察按照传统惯例，将”子”改称作“弟”，将“兄弟”改作“兄“，则多叉树的”父结点+孩子结点“表示法，将恰好对应于二叉树的那种表示法？ 分析： ”长子-兄弟“表示法 5-22 题目大意总结： 这里需要借助二叉树，表示多叉树的长子兄弟表示法：分别以左右孩子作为长子/兄弟 分析： 感觉其实就是每一层是个列表就好，代码略，感觉逻辑简单，但是要实现整个模板类确实有点麻烦。有时间再补吧！ 5-23 题目大意总结： 扩展BinTree::swap()接口，在时间内将二叉树中每一个结点的左、右孩子互换，其中为树中结点总数 分析： 感觉只需要遍历一次即可，回溯的时候换一下左右孩子。 5-24 题目大意总结： 设二叉树共个结点，且各结点数据项的类型支持大小比较和线性累加。 a 设计一个递归算法，在时间内判断是否该树中所有结点的数值均不小于其真祖先的数值总和。对于没有真祖先的树根结点，可认为其值为0 分析： 感觉这里只需要先序dfs遍历一遍，然后每次往下的时候累计当前真祖先的值即可，每到一个结点就判断一次。 这里可以直接参考书中的先序遍历递归代码,核心部分为: b 试将上述算法改为迭代版 分析： 将先序遍历递归改为迭代即可。 c 迭代版需要多少空间？ 分析： 这里省去了系统隐式维护的递归调用栈，实际占用空间有所减小，但渐进意义下仍然是线性的。 5-25 题目大意总结： 设二叉树共个结点，且各结点数据项类型支持大小比较 a 试设计并实现一个递归算法，在时间内将每个结点数值都替换为其后代数值中的最大值 分析： 呃，这应该比较容易实现吧，一个简单的dfs，返回一下当前结点及其后代的最大值即可: b 试将上述算法改为迭代版 分析： 将后序遍历递归改为迭代即可。 c 迭代版需要多少空间？ 分析： 这里省去了系统隐式维护的递归调用栈，实际占用空间有所减小，但渐进意义下仍然是线性的。 5-26 题目大意总结： 设二叉树共个结点，且各结点数据项类型支持线性累加 试设计并实现一个递归算法，按照如下规则，在时间内为每个结点设置适当的数值： 树根为0，对于数值为的结点，其左孩子数值为，右孩子数值为 分析： 利用一次层序遍历即可，对于完全二叉树来说，基于向量实现，直接遍历一次向量即可。 5-27 题目大意总结： 试证明，在考虑字符的出现频率之后，最优编码树依然具有双子性。 分析： 双子性是指：内部结点的左右孩子全双，即为真二叉树。 若某最优二叉编码树T中，内部结点有唯一的孩子，如此，可直接删去用代之，那得到的新树的平均编码长度必然更短。 5-28 题目大意总结： 试证明，5.5.4节所述Huffman编码算法的原理，对任意字符集均成立： 分析： 可以证明：由Huffman算法所生成的编码树，的确是最优编码树 这里用了一个数学分析法来归纳说明，感觉记住即可。 5-29 题目大意总结： 5.5.4节针对Huffman树构造算法的讲解中，暂时忽略了歧义情况。比如，有些字符的出现频率可能恰好相等；或者虽然最初的字符权重互异，但经过若干次合并后，森林也可能会出现权重相同的子树。另外每次选出的合并字符的左右次序也未说明。 a 试证明，以上歧义并不影响所生成编码树的最优性 分析： 参考习题[5-28]的证明即可，其并未排除字符和权重相同的情况 b 参考教材所给代码，了解并总结在实现过程中处理这类歧义的一般性方法 分析： 此类歧义通常交给数据结构处理(比如这里的列表和之后的优先队列)，但实际上感觉这类歧义似乎也并不影响结果，为何要消除呢？难道是因为规定所生成的最优编码树是唯一的？ 5-30 题目大意总结： 这里需要设计实现一个字典树： 分析： 这里给出一个之前自己学习Trie树的模板： 其实字典树就是建立当前字母当下一个字母的路径即可(没路就加一条路) 这里输入是： 选项I 是插入字符串到集合中 选项Q 是查询集合中字符串出现了多少次 输出是：
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/86813.html
