北航数据结构与程序设计第五次作业选填题复习

选填题考的很多都是基础概念，对于巩固复习一些仡佬拐角的知识点是很有用的。非北航学生也可以来看看这些题，这一节主要是树方面的习题：

---

一、
我们首先需要知道一个公式

这是证明：

知道了这个公式，我们把题目中的数据带入即可：
n0=n2+2n3+3n4+1
=1+2 * 10+3 * 20+1
=82

---

二、

两个知识点：
1、二叉树的分支个数等于节点个数-1，适用于任何二叉树，则m=n-1
2、满二叉树的深度与结点个数之间的关系：n=2^h-1 , h=log(n+1)。
因此选D很明显

---

三、
这个题蛮有意思，正着想不太好想，那我们就把每个选项都试一试，看看哪个符合要求。
A.空和仅有一个节点，前序遍历和后序遍历长得一样，要说相反好像勉强也行。这个选项暂时保留，大概率肯定不是，我们往下看。

B.我们画个图实际演示一下
前序遍历：A B C D E
后序遍历：E D C B A
诶好像可以诶！！但是别高兴太早了，我们发现D选项囊括了B选项，那我们就要思考一下，这种情况会不会不全面呢？

C.其实有了上一个题的疑问，我们实际可以直接先验证D选项：

这是一个分支节点的度都为1的树，我们来验证一下他的前后序遍历：
前序遍历：A B C D E
后序遍历：E D C B A
正好相反，因此，正确答案为D

---

四、
这道题的正确答案应该是A。
二叉查找树的查找效率由平均查找长度（ASL）来决定：

查找第一层的元素，需要比较1次，查找第二层的元素，需要比较2次……查找第n层的元素，需要查找n次，那么上述树的平均查找长度就为：（1 * 1 + 2 * 2 + 3 * 4 + 4 * 2）/9=25/9

在来看时间复杂度：理想情况下，查找一个元素需要比较的最多次数为深度次，也就是从树冠比到树根，那么时间复杂度就是O(h),h=logn (我们这里只说数量级，不考虑具体是满二叉树还是完全二叉树还是普通二叉树），时间复杂度也可以表示为：O(logn）。也就是说，二叉查找树查找的时间复杂度是由深度决定的。

注意，当二叉查找树退化时，也就是说，差不多快变成一个链表的时候（左右子树深度之差过大），那么这个时候查找的时间复杂度就和在链表里查找的时间复杂度差不多了，就变成O(n)了。

---

六、

这道题的正确答案应该为D
但是我对此存疑，我再问问助教去……

---

七、

中缀转前缀的方法为：

1. 从右到左扫描表达式

2. 遇到操作数直接输出，输出顺序从右到左

3. 遇到操作符：
   1.遇到 ‘ ）’，入栈
   2.操作符栈空，入栈
   3.当前操作符优先级 >= 栈顶操作符，入栈（注意，中缀转后缀是要大于才入栈）
   4.当前操作符优先级 < 栈顶操作符，栈顶操作符出栈，然后与新的栈顶元素比较，直到栈空或优先级大于等于栈顶操作符或遇到‘ ）’ 时，入栈。

4. 遇到括号：
   1.遇到右括号，入栈
   2.遇到左括号，将栈内运算符依次弹出并从右到左输出，直到遇到左括号，左括号弹出，但左括号不输出

5. 将栈内剩余操作符从右到左依次弹出并输出

---

八、

前缀编码，任何一个编码都不能成为其他编码的前缀，但是B中，10是101的前缀。

---

九、

先来了解一下哈夫曼树的构造原理：
1.树的带权路径长度WPL：

wi为第i个叶结点被赋予的权值，li为根节点到第i个叶结点的路径长度

2.哈夫曼树的定义：
给定一组权值，构造出的具有最小带权路径长度的二叉树即哈夫曼树
3.哈夫曼树特点：

• 权值越大，离根越近，权值越小，离根越小

• 无度为1的节点

• 哈夫曼树不唯一

4.哈夫曼树的构造

• 对于给定的权值W={w1,w2,…… ,wm},构造出树林F={T1,T2,…… ,Tm}，其中Ti为左右子树为空，且根节点的权值为wi的二叉树
• 将F中根节点权值最小的两棵二叉树合并成为一棵新的二叉树，将这两棵二叉树作为新二叉树的左右子树，并将新二叉树的根结点的权值定为这两棵二叉树权值的和。将新二叉树加入F，同时从F中删除之前的两棵二叉树
• 重复上一步，直到F中只有一棵二叉树。

按照上述步骤，我们构造出了一棵哈夫曼树，那么带权路径长度就为：
2 * 3 + 3 * 3 + 5 * 2 + 6 * 2 + 9 * 2 = 55

---

二、

度为k，那么要求最多个结点，我们就让每个分支节点的度都为K，那么第一层就有k^0个结点，
第二层有k^1个，
第三层：k^2,
第四层：k^3，
以此类推，第i层最多就有k^(i-1)个节点

---

三、

满二叉树的深度和结点个数关系：n=2^h-1,则h=log(n+1),可得深度为：log(2048)=11,最后一层的节点个数，也就是叶结点个数为n=2 ^ (h-1)=2 ^ 10 = 1024。

---

四、
先恢复一下二叉树：

那么后续序列就为：

HIDJEBFGCA

---

五、

每个结点都有left和right两个指针，因此共有2n个指针域
分支节点个数等于节点个数减一，那么就意味着n-1个指针指向孩子节点，剩下的2n-(n-1)=n+1个指针域就指向空

---

六、
先恢复一下二叉树

那么后序遍历结果就是：DCBFGEA

---

七、
处在同一层，说明深度一样，
2^ (h-1) - 1 < i < 2 ^ (h) - 1
2^ (h-1) - 1 < j < 2 ^ (h) - 1

---

八、

这个注意，做减法和除法的时候，先弹出的减（除）后弹出的，和后缀表达式计算不太一样。

---

九、

建立好的二叉查找树如上图，62先和54比，再和73比，再和62比，发现找到，结束比较，工比较三次。

---

十、

则带权路径长度为：4×3+5×3+8×2+6×2+7×2=12+15+16+12+14=69