【笔试题】【day19】

目录

第一题、二叉树后序遍历+中序遍历推前序遍历

第二题、二叉树的度的计算

第三题、堆的序列特征

第四题、稳定的排序算法

---

第一题、二叉树后序遍历+中序遍历推前序遍历

已知二叉树后序遍历序列是bfegcda，中序遍历序列是badefcg，它的前序遍历序列是（）

A abcdefg
B abdcefg
C adbcfeg
D abecdfg

后序遍历的最后一个元素是a，所以我们的根节点是a

然后观察a在中序遍历中的位置

a的左边是b，a的右边是defcg，也就分别是a的左子树和右子树

然后我们从后序遍历中观察到fegcd中的d是最后一个，所以我们的d就是我们a的右子树的根节点，然后按照中序遍历defcg，d是我们的第一个元素，所以我们的efcg全部都是我们d的右子树，d的左子树没有节点

 

 

然后我们再观察后序遍历的fegc，c是我们efcg的根节点

所以再看中序遍历，所以ef在c的左边是c的左子树的结点，g在c的右边，是我们c的右子树的结点

然后我们再看后序遍历中是fe，也就是说e是我们的ef的根节点，f是e的左子树，我们就可以画出我们整一棵二叉树了 

所以我们的前序遍历的结果是

a->b->d->c->e->f->g 

也就是我们的选项B

B

第二题、二叉树的度的计算

 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（）

A 不存在这样的二叉树
B 200
C 198
D 199

对于任何一棵二叉树来说，如果其终端结点数为N0，度为2的节点数为N2，则N0=N2+1

所以有199个度为2的结点，就一定有200个度为0的结点

 N0=N2+1的证明

设度为0,1,2的结点个数分别为N0,N1和N2个，总结点数N=N0+N1+N2

在看二叉树中的分树，除了根节点外，其他每一个结点都有一个分支进入，设B为分支的总数，所以N=B+1

由于这些分支是由度为1或者2的结点射出的，所以又有B=N1+2N2

于是将B消掉

N0+N1+N2=N1+2N2+1

所以N0=N2+1

也就是得出了我们的结论

B

第三题、堆的序列特征

以下序列不是堆的是（）

A (100,85,98,77,80,60,82,40,20,10,66)
B (100,98,85,82,80,77,66,60,40,20,10)
C (10,20,40,60,66,77,80,82,85,98,100)
D (100,85,40,77,80,60,66,98,82,10,20)

A

可以组成一个大根堆 

B可以组成一个大根堆

 C可以组成一个小根堆

 D

无法组成大根堆或者小根堆 

D

第四题、稳定的排序算法

以下哪种排序是不稳定排序（）

A 冒泡
B 插入排序
C 归并排序
D 快速排序

 

快速排序是不稳定的

冒泡、插入和归并都是稳定的。

希尔排序，堆排序，快速排序不稳定，因为这几个的排序效率比较好

先进排序的时间复杂度一般都是log阶的

稳定的一般都是N^2

D