华文慕课-数据结构二叉树题库

大家好，欢迎来到IT知识分享网。

1、一棵有512个结点的完全二叉树的高度为多少？（独根树高度为1）

解析：

​​

答案： 10

2、请写出下面这棵二叉树的中序遍历

解析：

左-根-右 left-root-right

答案： LXMECKPBQHDA

3、下列关于二叉树性质的说法正确的有：

A、非空满二叉树的结点个数一定为奇数个。

解析：非空满二叉树只有度为0或者度为2两种结点，而这两种结点的个数差为1，所以加起来必为奇数。

n0=5个 n2=4个 n0=n2+1

B、非完全二叉树也可以用像完全二叉树那样使用顺序存储结构进行存储。

解析：非完全二叉树无法知道每一层哪些位置缺了结点，不能像完全二叉树那样直接计算出两个儿子的编号，所以不能用顺序存储结构存储。

C、当一棵完全二叉树是满二叉树时，叶子结点不一定集中在最下面一层。

解析：只要倒数第二层的度都为0或者2，此棵完全二叉树即为满二叉树，最下面一层不一定要全满

D、完全二叉树最多只有最下面的一层结点度数可以小于2。

解析：倒数第二层也可以有度数为0的结点。

E、一棵非空二叉树的为空的外部结点数等于其结点数加1。

解析：

F、满二叉树的所有结点的度均为2

解析：结点度数还可以为0。

4、已知一棵树的前序遍历为ABDEGCF，中序遍历为DBGEACF，求这棵树的后序遍历。

解析​

答案： DGEBFCA

5、下列关于二叉树遍历的说法正确的有:

A、只有空二叉树和一个根结点的二叉树这两种二叉树的前序和中序遍历的顺序恰好一样。

解析：前序为中左右，而中序为左中右，所有结点都没有左子树后，两者恰好一样。所以所有结点左子树为空的二叉树也满足要求。

B、所有结点左子树为空的二叉树的前序和中序遍历顺序恰好一样。

解析：前序为中左右，而中序为左中右，所有结点都没有左子树后，两者恰好一样。

C、所有结点右子树为空的二叉树的前序和中序遍历顺序恰好一样。

解析： 前序为中左右，而中序为左中右，所有结点都没有右子树后，前序为中左，而中序为左中，两者不同。

D、只有空二叉树和一个根结点的二叉树这两种二叉树的前序和后序遍历的顺序恰好一样。

解析：前序为中左右，而后序为左右中，缺失左子树，前序为中右，而后序为右中；

缺失右子树，前序为中左，而后序为左中，都不一样。（下面的选项同理）

E、所有结点左子树为空的二叉树的前序和后序遍历顺序恰好一样。

解析：前序为中左右，而后序为左右中，所以缺失左子树或者右子树都不能让两者一样。

F、所有结点右子树为空的二叉树的前序和后序遍历顺序恰好一样。

解析：前序为中左右，而后序为左右中，所以缺失左子树或者右子树都不能让两者一样。

G、只有空二叉树和一个根结点的二叉树这两种二叉树的中序和后序遍历的顺序恰好一样。

解析：中序为左中右，而后序为左右中，所有结点都没有右子树后，两者恰好一样。所以所有结点右子树为空的二叉树也满足要求。

H、所有结点左子树为空的二叉树的中序和后序遍历顺序恰好一样。

解析：中序为左中右，而后序为左右中，所有结点都没有右子树后，两者恰好一样。所以所有结点右子树为空的二叉树才满足要求。

I、所有结点右子树为空的二叉树的中序和后序遍历顺序恰好一样。

解析： 中序为左中右，而后序为左右中，所有结点都没有右子树后，两者恰好一样。

J、存在一棵非空二叉树，它的前序、中序和后序遍历都是一样的。

解析：只有一个根结点的二叉树满足要求。

6、下列关于二叉搜索树的说法正确的有

A、二叉搜索树按照中序遍历将各结点打印出将各结点打印出来，将得到按照由小到大的排列。

解析：

​

B、如果结点χ的左子树有右子树，则存在某个结点的值介于结点χ的值和χ左儿子的值之间，并且这个结点在x的左子树之中。

解析：这样的结点就位于χ的左子树的右子树中。

​C、当根结点没有左儿子时，根结点一定是值最小的结点。

解析：右子树中的结点的值都大于根结点，所以根结点的值是最小的。

D、二叉搜索树一定是满二叉树。

解析：不一定。如果对于一个结点存在值比它大的结点，但不存在比它小的，这时它可能就只有一个儿子。

E、二叉搜索树一定是完全二叉树。

解析：不一定。按照从小到大的顺序依次插入一些值（数量超过1个），就可以让二叉搜索树变成一条链，这样显然不是完全二叉树。

F、从根结点一直沿右儿子向下找不一定能找到树中值最大的结点。

解析：右子树中的结点的值都大于根结点，所以根结点的值是最小的。

7、

从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码构造出一棵二叉搜索树，以怎样的顺序插入关键码集合{14,32,47,6,9,12,78,63,29,81}可以使得树的深度最小？请依次写出插入到树中的元素，每两个元素之间用一个空格隔开。

解析

8、下列关于堆的说法正确的有:

A、堆一定是满二叉树。

解析：堆采用完全二叉树实现。

B、最小堆中，最下面一层最靠右的结点一定是权值最大的结点。

解析：不一定。最小堆只保证了每个结点都比它的两个儿子都小，所以它左儿子的值可能比右儿子的大，所以最大的结点不一定靠右。

C、堆是实现优先队列的惟一方法。

解析：堆只是实现优先队列的一种方法。用普通的队列也可以实现优先队列，只是效率比较低。

D、堆一定是完全二叉树。

E、最小堆中，某个结点左子树中最大的结点可能比右子树中最小的结点小。

解析：堆中一个结点的左儿子和右儿子并没有严格的大小关系，所以存在这种情况。

F、使用筛选法建堆要比将元素一个一个插入堆来建堆效率高。

解析：筛选法建堆的时间复杂度为O(n)，而一个一个插入建堆时间复杂度为O(nlogn)。其中，n为堆中元素个数。

9、下列关于Huffman树和Huffman编码的说法正确的有:

A、Huffman树一定是满二叉树。

解析：在建立的过程中，每次都选取两棵子树进行合并，所以所有结点要么有两个儿子，要么没有儿子。

B、Huffman编码是一种前缀编码。

解析：Huffman树中，所有需要编码的内容都在叶结点中，所以任何内容的编码都不会是其它内容编码的前缀。

C、Huffman树一定是完全二叉树。

解析：取一棵是完全二叉树的Huffman树翻转过来，这棵树依然是Huffman树，但是已经不再是完全二叉树了。

D、Huffman编码中所有编码都是等长的。

解析：Huffman树的叶结点并不一定在同一层，所以Huffman编码不等长。

E、对于同样的一组权值两两不同的内容可以得到不同的Huffman编码方案。

解析：把某一个结点往左子树编码0，往右子树编码1反过来就可以得到另外一组编码方案。

F、使用频率越高的字母，Huffman编码越长。

解析：频率越高，Huffman编码应该越短，这样才能提高编码效率。

10、请阅读下面一段代码

若此段代码的作用是用来进行前序遍历，那么应该在几号访问点进行访问？（只需要填写数字）

解析

使用深搜算法进行前序遍历，根左右，每达到一个结点就应该进行访问。

答案： 1

11、小库科技笔试题

给予一个二叉树的根节点，验证该树是否是二叉搜索树，在O(n)时间内，用熟悉的语言写出算法。

答案：https://blog.csdn.net/wydyd110/article/details/83000194

12 对于如下图所示的最大堆，删除掉最大的元素后，堆的后序遍历结果是​​

答案： 12 23 24 28 5 37 43 48 3 57 59

参考：https://blog.csdn.net/wydyd110/article/details/82994739#5%20%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97%E4%B8%8E%E5%A0%86​