二叉树习题集二

- 日理万妓 2022-05-09 10:33 352阅读 0赞

## 二叉树 习题集二 ##

> 1、B- 树的插入算法中，通过结点的向上“分裂”，代替了专门的平衡调整。 对

解析：  
B-树的插入过程是一个动态调整的过程。设B-树的度为m，则在插入时，会先找到合适的节点位置，插入到相应位置，然后判断该节点的关键字个数是否超过m-1，若超过则作“分裂”处理——将中间节点上移插入到父节点中，原来节点的左边（原来中间节点的左边）放在原来的节点中不变，而右边则放入到新节点中，然后再判断父节点的度，超过则作相同的分裂操作，每次分裂都是向上传递，因此很好的保证了B-树的平衡性。

> 2、哈夫曼树度为1的结点数等于度为2和0的结点数之差。 错

哈夫曼树只有度为2和叶子结点。

> 3、不同的求最小生成树的方法最后得到的生成树是相同的。 错

最小生成树算法：适用范围：无向图  
其是完成的就是再保证这个图是连通图的同时，又能保证这个图的所有边的权值之和是最低的。  
最小生成树的算法：包含两个一个是Kruskal（克鲁斯卡尔）算法，一个是Prim（普里姆）算法  
①K算法：  
K算法（克鲁斯卡尔），其是就是从小权重的边开始，考虑两块，一是不能产生回路，否则，该边舍弃，再选小权重的边，直至到所有顶点均构成回路为止，因为各边的权值可能相同，即可能出现边的最小权值之和的最优解不止一个。  
②P算法：  
普里姆算法：实现：P算法是按照点来实现的  
逻辑实现：其实就是先从一个顶点开始，寻找权值最小的边，找到下一个顶点，解锁与该点所有相关的边，然后剩余的边中找到权值最小的边，看是否能解锁信的节点，不解锁，此边舍弃解锁，则把新解锁的顶点的所有边解锁，依次类推，直至所有节点都解锁为止，选中的边即为所求。P算法算出的最优解也可能不止一种。

> 4、若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（C）。

A. 257
    B. 258
    C. 384
    D. 385

根据完全二叉树的性质，最后一个分支结点的序号为ën/2û = ë768/2û =384，故叶子结点的个数为768-384=384。  
【另解1】由二叉树的性质n=n0+n1+n2和n0=n2+1可知，n=2n0-1+n1，及2n0-1+n1=768，显然n1=1，2n0=768，则n0=384。  
【另解2】完全二叉树的叶子结点只可能出现在最下两层，由题可计算完全二叉树的高度为10。第10层的叶子结点数为768-(29-1)=257；  
第10层的叶子结点在第9层共有

个父结点，第9层的叶子结点数为

则叶子结点的总数为257+127=384。

> 5、对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（A）。

A. 95， 22， 91， 24， 94， 71
    B. 92， 20， 91， 34， 88， 35
    C. 21， 89， 77， 29， 36， 38
    D. 12， 25， 71， 68， 33， 34

解析：  
关键：前面的节点，或者比后面的节点都大，或者比后面的节点都小。  
例如 95， 22， 91， 24， 94， 71。  
95比 22， 91， 24， 94， 71都大  
22比91， 24， 94， 71 都小  
91 比 24， 94， 71都大 （不符合，91比94小）  
24 比 94， 71都 小  
94 比 71大

> 6、任何二叉树的后序线索树进行后序遍历时都必须用栈。 错

一般情况下，二叉树的后序线索树是需要额外用到栈的。虽然每个节点都带有前驱和后续指针，但若前驱和后续指针都被占用，那么只能用栈。注意，一种情况除外，那就是只有左半边或者右半边的二叉树是不需要用到栈的。

> 7、一棵非空的二叉树的前序序列和后序序列正好相反,则该二叉树一定满足( C )

A. 其中任意一个结点均无左孩子
    B. 其中任意一个结点均无右孩子
    C. 其中只有一个叶结点
    D. 其中度为2的结点最多为一个

一棵非空的二叉树的前序序列和后序序列正好相反,则该二叉树一定满足只有左子树或只有右子树。  
A,B 明显不对，举最简单的例子，1为根节点，2分别为1的左右孩子，都满足前序序列和后序序列正好相反。  
D 不可能出现一个度为2的节点。

> 8、将森林F转换为对应的二叉树T，F中叶结点的个数等于 （C）

A. T中叶结点的个数
    B. T中度为1的结点个数
    C. T中左孩子指针为空的结点个数
    D. T中右孩子指针为空的结点个数

解析1：  
在二叉树中，节点的左指针指向其孩子，节点的右指针指向其兄弟。所以在一颗二叉树中，如果某个节点的左指针为NULL，就说明这个节点在原来的森林中没有孩子，是叶子几点，如果某个节点的右指针为NULL，就说明这个节点在原来的森林中没有兄弟。  
所以森林中的叶子节点=二叉树中左指针为NULL的个数  
解析2：  
森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。  
将森林转换为二叉树的步骤是：  
（1）先把每棵树转换为二叉树；  
（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。

> 9、对于以下用数组存储的二叉树A B C D E采用中序和前序遍历的结果是（AC）

A. A B D E C
    B. D E B C A
    C. D B E A C
    D. C E D B A

(1)以数组存储，是按照层次序来保存的。所以A在第一层BC在第二层DE在第三层。  
(2)画出数：

> 10、基于哈希的索引和基于树的索引有什么区别? (ABCD)

A. hash索引仅满足“=”、“IN”和“<=>”查询，不能使用范围查询
    B. hash索引无法被用来进行数据的排序操作
    C. 对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用
    D. Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高

解析：  
1、hash索引仅满足“=”、“IN”和“<=>”查询，不能使用范围查询  
因为hash索引比较的是经常hash运算之后的hash值，因此只能进行等值的过滤，不能基于范围的查找，因为经过hash算法处理后的hash值的大小关系，并不能保证与处理前的hash大小关系对应。  
2、hash索引无法被用来进行数据的排序操作  
由于hash索引中存放的都是经过hash计算之后的值，而hash值的大小关系不一定与hash计算之前的值一样，所以数据库无法利用hash索引中的值进行排序操作。  
3、对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。  
4、Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。  
对于选择性比较低的索引键，如果创建 Hash 索引，那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。