2. 考研
  3. 下列关于二叉排序树的说法正确的是( )。 Ⅰ．向二叉排序树中插入一个结点，所需要比较的次数可能大于此二叉排序树的高度 Ⅱ．二叉排序树一定是平衡二叉树 Ⅲ．删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树 Ⅳ．平衡二叉树是指左、右子树

下列关于二叉排序树的说法正确的是( )。 Ⅰ．向二叉排序树中插入一个结点，所需要比较的次数可能大于此二叉排序树的高度 Ⅱ．二叉排序树一定是平衡二叉树 Ⅲ．删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树 Ⅳ．平衡二叉树是指左、右子树

admin2019-12-10  46
问题 下列关于二叉排序树的说法正确的是(    )。
Ⅰ．向二叉排序树中插入一个结点，所需要比较的次数可能大于此二叉排序树的高度
Ⅱ．二叉排序树一定是平衡二叉树
Ⅲ．删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树
Ⅳ．平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树
选项 A、Ⅰ、Ⅱ、Ⅳ
B、Ⅱ、Ⅲ、Ⅳ
C、Ⅰ、Ⅳ
D、全错
答案D
解析 Ⅰ:根据二叉排序树插入操作的步骤可知，比较次数最坏情况下等于树的高度，所以I错误。
Ⅱ：二叉排序树不一定是平衡二叉树。例如，降序的一个序列组建二叉排序树时，会出现没有右子树的二叉树，此时明显不是平衡二叉树，所以Ⅱ错误。
Ⅲ：不一定可以得到以前的排序二叉树。例如，给出一个二叉排序树，如图3—8所示。此时删除结点3，二叉排序树变为图3—8b，再插入结点3，变为图3—8c。显然图3—8a和图3—8c不是同一个二叉排序树，所以Ⅲ错误。

Ⅳ：根据平衡二叉树的概念可知，该说法是错误的，应该改为：平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉排序树（出此选项的目的是让大家深刻记住平衡二叉树默认是二叉排序树），所以Ⅳ错误。
转载请注明原文地址:https://www.kaotiyun.com/show/on3i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)