软考初级
设有二叉排序树如下图所示，根据关键码序列（ ）构造出该二叉排序树。A.30 20 10 40B.30 40 20 10C.30 20 40 10D.30 40 10 20
题目
设有二叉排序树如下图所示，根据关键码序列（ ）构造出该二叉排序树。
A.30 20 10 40B.30 40 20 10C.30 20 40 10D.30 40 10 20
相似问题和答案
第1题：
从供选择的答案中选出应填入下列叙述中()内的正确答案：
在二叉排序树中，每个结点的关键码值(A)，(B)一棵二叉排序树，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称做最佳二叉排序树，最佳二叉排序树在结构上的特点是(C)。
供选择的答案
A：①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小
②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大
③比左右子树的所有结点的关键码值大
④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系
B：①前序遍历 ②中序(对称)遍历
③后序遍历 ④层次遍历
C：①除最下二层可以不满外，其余都是充满的
②除最下一层可以不满外，其余都是充满的
③每个结点的左右子树的高度之差的绝对值不大于1
④最下层的叶子必须在左边
A：① B：② C：②
第2题：
有关键码值为10, 20. 30的三个结点，按所有可能的插入顺序去构造二叉排序树。能构造出多少棵不同的二叉排序树？
A．4
B．5
C．6
D．7
第3题：
（4）有关键码值为 10，20，30，的三个结点，接所有可能的插入顺序去构造二叉排序树，能构造出
【4】 棵不同的二叉排序树。
（4）【答案】5
【解析】3个节点可以构造以下5种二叉树：
第4题：
设有关键码序列( 10，40，30，20)，根据该序列构建的二叉排序树是（ ）。
A.
B.
C.
D.
第5题：
● 用关键字序列10、20、30、40、50构造的二叉排序树（二叉查找树）为 （63） 。
第6题：
下列问题基于如下描述：现有关键码值分别为10、20、30、40的4个节点，按所有可能的插入顺序去构造二叉排序树。
能构造出多少棵不同的二叉排序树?______。
A．24
B．14
C．10
D．8
第7题：
用关键字序列10、20、30、40、50构造的二叉排序树(二叉查找树)为(63)。
A．
B．
C．
D．
解析：二叉排序树又称二叉查找树，它可以是一棵空树，若非空时具有下述性质：
1．若根结点的左子树非空，则左子树上所有结点的关键字值均小于等于根结点的关键字值。
2．若根结点的右子树非空，则右子树上所有结点的关键字值均大于等于根结点的关键字值。
3．根结点的左、右子树也分别为二叉排序树。
构造二叉排序树过程如下：
首先与根结点比较，如果小于等于则进入左边子树，再与左边子树的根节点比较，直到找到它要放的位置，否则进入右子树，进行上述操作。
第8题：
● 关于二叉排序树的说法，错误的是 （27） 。
（27）
A. 对二叉排序树进行中序遍历，必定得到结点关键字的有序序列
B. 依据关键字无序的序列建立二叉排序树，也可能构造出单支树
C. 若构造二叉排序树时进行平衡化处理，则根结点的左子树结点数与右子树结点数的差值一定不超过1
D. 若构造二叉排序树时进行平衡化处理，则根结点的左子树高度与右子树高度的差值一定不超过1
第9题：
设有二叉排序树(或二叉查找树)如下图所示，建立该二叉树的关键码序列不可能是()。
A.23 31 17 19 11 27 13 90 61
B.23 17 19 31 27 90 61 11 13
C.23 17 27 19 31 13 11 90 61
D.23 31 90 61 27 17 19 11 13
第10题：
●非空二叉排序树的定义是：若根结点具有左子树，则左子树中所有结点的关键码均小于根结点的关键码；若根结点具有右子树，则右子树中所有结点的关键码均大于根结点的关键码；左、右子树也是二叉排序树。由此可知，在一个二叉排序树中,(40)。
(40)
A．从根结点到任何一个叶子结点的路径上，结点的关键码序列呈递增排列
B．从根结点到任何一个叶子结点的路径上，结点的关键码序列呈递减排列
C．同层次结点从左向右排列，结点的关键码序列呈递增排列
D．同层次结点从左向右排列，结点的关键码序列呈递减排列