数据结构二进制搜索树

1. 在二叉搜索树中找到63. 搜索时，序列39、101、25、80、70、59、63可能是节点值比较序列.

TF

2. 在由一系列包含4、5、6等的整数节点组成的二叉搜索树中，如果节点4和6在树的同一级别上，则可以得出结论，节点5必须是的父节点. 节点4和6.

TF

3. 二进制搜索树搜索和二进制搜索的时间复杂度相同.

TF

只有平衡的二叉搜索树与二叉搜索具有相同的时间复杂度

4. 二叉搜索树的最小元素必须位于根的左子树中.

作者: DS课程组

单位: 浙江大学

1-3个答案正确（2分）

1-6

二分搜索树的最小元素必须在根的左子树中.

TF

它也可能是根节点

1. 遍历二叉搜索树可以使排序顺序从小到大？

A. 顺序遍历

B. 后遍历

C. 中阶遍历

D. 层次遍历

2. 在具有N个节点并且是完整的二叉树的二叉搜索树中找到一个键值，平均比较时间为数量级:

A.O（logN）

B.O（N）

C.O（NlogN）

D.O（N2）

3. 已知八个数据元素分别为（34、76、45、18、26、54、92、65），在通过顺序插入节点生成二分搜索树之后，最后两个级别为: 节点总数为:

A.1

B.2

C.3

D.4

4. 将{28，15，42，42，18，22，5，40}依次插入到最初为空的二进制搜索树中. 那么树的后遍历结果是:

A.5、15、18、22、40、42、28

B.5、22、15、40、18、42、28

C.28、22、18、42、40、15、5

D.5、22、18、15、40、42、28

5. 将{5，2数据结构二叉排序树，7，7，3，4，1，6}依次插入到最初为空的二进制搜索树中. 那么树的后遍历结果是:

A.1、2、3、4、6、7、5

B.1、4、2、6、3、7、5

C.1、4、3、2、6、7、5

D.5、4、3、7、6、2、1

6. 如果二叉树的顺序遍历序列为{4，2，1，3，6，5，7}，则中间顺序遍历为{1,2,3,4,5,6,7} ，以下哪一项是错误的？

A. 这是完整的二叉树

B. 所有奇数都在叶节点上

C. 这是一个二叉搜索树

D.2是5的父节点

7. 依次将{6，9，12，12，3，4，8}插入最初为空的二进制搜索树中. 那么树的后遍历结果是:

A.4、3、6、8、12、9

B.3、4、9、8、12、6

C.3、4、6、8、12、9

D.4、3、8、12、9、6

8. 如果二进制搜索树是具有N个节点的完整二进制树，则错误语句为:

A. 所有节点的平均搜索效率为O（logN）

B. 最小值必须在叶节点上

C. 最大值必须在叶节点上

D. 中值节点位于根节点或根的左子树上

9. 从1到6的6个关键字插入到最初是空的二进制搜索树中. 插入完成后，搜索树结构如图所示: 问: 可能的插入顺序是什么？

A.1 2 3 4 5 6

B.4 1 2 3 5 6

C.4 1 3 2 6 5

D.4 1 3 2 5 6

10. 在以下二叉树中，可能成为二叉搜索决策树（不包括外部节点）的是:

A.

B.

C.

D.

二进制搜索决策树是一个完整的二进制树

11. 每个二叉搜索树（）都是由同一组关键字构成的.

A. 形状相同，但平均搜索长度不一定相同

B. 形状相同，平均搜索长度也相同

C. 形状不一定相同，但平均搜索长度相同

D. 形状不一定相同，平均搜索长度不一定相同

12. 如果存在数据{53、30、37、12、45、24、96}，则从空的二叉树逐渐插入数据以形成二叉搜索树. 如果要最小高度，则应选择以下（）序列输入.

A.37、24、12、30、53、45、96

B.45、24、53、12、37、96、30

C.30、24、12、37、45、96、53

D.12、24、30、37、45、53、96

13. 对于一组节点，从一棵空树开始，将它们插入到二进制搜索树中数据结构二叉排序树，便建立了一个二进制搜索树. 此时，整个二叉搜索树的形状取决于（）.

A. 节点的存储结构

B. 节点值范围

C. 节点输入顺序

D. 电脑硬件

14. 以下语句是正确的（）.

A. 在任何非空的二进制搜索树中，删除一个节点并再次插入它，生成的二进制搜索树与删除之前的原始二进制搜索树相同.

B. 除叶节点外，二叉树中任何节点X的左子树根节点的值都小于节点（X）的值. 右子树根节点的值≥节点的点（X）的值，则该二叉树必须是二叉搜索树.

C. 尽管给定关键字序列的顺序不同，但是顺序生成的二叉搜索树是相同的.

D. 在二叉搜索树中插入一个新节点，该节点始终作为新的叶节点插入到最低级别.

15. 下图显示了已知的二进制排序树. 元素之间的大小关系应为:

A.x1

B.x1

C.x3

D.x4

16. 在具有25个节点的二元排序树上，找到键为35的节点，则要顺序比较的键序列可能是（）.

A.28,36,18,46,35

B.18,36,28,46,35

C.46,28,18,36,35

D.46,36,18,28,35

数据结构二进制搜索树

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-242894-1.html