本文主要是介绍Jeff的错题集(四):压死骆驼的最后一根稻草-----树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题一:
若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是( )。
正确答案: B 你的答案: C (错误)
9
11
15
不确定
解答:
若在任意一棵二叉树中,有n0个叶子节点,有n2个度为2的节点,则必有n0=n2+1。
题二:
下列各树形结构中,哪些是平衡二叉查找树:
正确答案: C 你的答案: A (错误)
4
/
3 5
/
2 8
/
1 9
7/ \2 8/ \1 4/ \3 55/ \2 8/ \ /1 4 7/37/ \2 8/ \ /1 4 6/3
解答:
二叉平衡查找树:
左子树中所有节点的值小于根的值,右子树中的所有节点的值大于根的值
左右子树的高度之差的绝对值为0或1
题三:
把一棵树转换为二叉树后,这棵二叉树的形态是( )
正确答案: A 你的答案: B (错误)
唯一的
有多种
有多种,但根节点都没有左孩子
有多种,但根节点都没有右孩子
解答:
树转换为二叉树
由于二叉树是有序的,为了避免混淆,对于无序树,我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。
将树转换成二叉树的步骤是:
(1)加线。就是在所有兄弟结点之间加一条连线;
(2)抹线。就是对树中的每个结点,只保留他与第一个孩子结点之间的连线,删除它与其它孩子结点之间的连线;
(3)旋转。就是以树的根结点为轴心,将整棵树顺时针旋转一定角度,使之结构层次分明。
题4:
下面关于二叉排序树的说法错误的是( )
正确答案: A 你的答案: C (错误)
在二叉排序树中,完全二叉树的查找效率最低
对二叉排序树进行中序遍历,必定得到节点关键字的有序序列
二叉排序树的平均查找长度是O(log2(n))
二叉排序树的查找效率与二叉树的树形有关
解答:
二叉排序树即:对任一子树都有 “左树<子树根节点<右树” 的二叉树结构,
对每一次查找,都会对当前节点的值进行比较,小于则进入左孩子,大于则进入右孩子,如此重复,直到确定结果
因此每次查找都对应着二叉树的的一条路径(分支),二叉树所有分支的平均长度决定了查找效率,越短越好
A选项:在所有二叉树中,完全二叉树的平均分支长度最短(节点数相同的情况下),查找效率最高,描述相反,故错误
B选项:因为“左树<子树根节点<右树”,而中序遍历也是左树优先输出,子树根节点次之,右树最后输出,这也正是它排序的原理,正确
C选项:以完全二叉树作为典型,n个节点的树深度为log2(n),其他树可以在增删时通过左旋和右旋调整成完全二叉树,正确
D选项:树的形状不同,分支的平均长度也会不同,树形能够综合考虑所有分支,故正确。但是要注意,除了完全二叉树外,其他树的深度并不能决定该树的查找效率,因为深度仅由最长的分支决定,只是考虑了一条路径,无法反映所有路径的平均长度。
题5:
在线索化树中,每个结点必须设置一个标志来说明它的左、右链指向的是树结构信息,还是线索化信息,若 0 标识树结构信息, 1 标识线索,对应叶结点的左右链域,应标识为 __ __ 。
正确答案: D 你的答案: B (错误)
00
01
10
11
解答:
叶子没有子树,所以其左右链域都是线索化信息,并且叶子的左右标志都是1,注意问题问的是叶节点的左右链域
所以就用1标识线索信息喽
题6:
在数据结构中,以下不适合用树来表示的有()
正确答案: A D 你的答案: A C D (错误)
元素之前无联系的数据
有序数据元素
元素之间具有分支层次关系的数据
无序数据元素
解答:
无联系、无序的数据没有必要使用指针相连接,不适合用树表示
有序数据用树表示可以从数的上下关系看出顺序
具有分支层次关系的数据用树表示可以用树的层序来表示
这篇关于Jeff的错题集(四):压死骆驼的最后一根稻草-----树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!