🏷️ 知识点：B树和B+树
对于二叉排序树，下面的说法中，()是正确的。
A. 二叉排序树是动态树表，查找失败时插入新结点，会引起树的重新分裂和组合 B. 对二叉排序树进行层序遍历可得到有序序列 C. 用逐点插入法构造二叉排序树，若先后插入的关键字有序，二叉排序树的深度最大 D. 在二叉排序树中进行查找，关键字的比较次数不超过结点数的1/2
[tag_link]
正确答案：C
按()遍历二叉排序树得到的序列是一个有序序列。
A. 先序 B. 中序 C. 后序 D. 层次
[tag_link]
正确答案：B
在二叉排序树中进行查找的效率与()有关。
A. 二叉排序树的深度 B. 二叉排序树的结点的个数 C. 被查找结点的度 D. 二叉排序树的存储结构
[tag_link]
正确答案：A
在常用的描述二叉排序树的存储结构中，关键字值最大的结点()。
A. 左指针一定为空 B. 右指针一定为空 C. 左右指针均为空 D. 左右指针均不为空
[tag_link]
正确答案：B
设二叉排序树中关键字由1到1000的整数构成，现要查找关键字为363的结点，下述 关键字序列中，不可能是在二叉排序树上查找的序列是()。
A. 2,252,401,398,330,344,397,363 B.924,220,911,244,898,258,362,363 C. 925,202,911,240,912,245,363 D.2,399,387,219,266,382,381,278,363
[tag_link]
正确答案：C
二叉排序树（BST）的查找过程是：从根结点开始，将待查关键字与当前结点的关键字比较，若小于则进入左子树，若大于则进入右子树。 所以查找路径中的每个结点关键字必须满足：左子树所有结点 < 根结点 < 右子树所有结点。
选项C的查找路径为 925 → 202 → 911 → 240 → 912，注意在240之后进入912，而912大于911（上次比较的结点）， 但根据BST性质，在240（位于911的左子树）之后只能继续向左或向右查找该子树内结点，不可能跳回到一个大于当前路径中某结点（911）的值， 除非该值在正确的子树方向上。实际上，在240（在911左子树中）之后查找到912，但912 > 911且912不可能出现在911左子树的240之后， 因为911的左子树中所有结点都小于911。故C不可能。
分别以下列序列构造二叉排序树，与用其他3个序列所构造的结果不同的是()。
A. (100,80,90,60,120,110,130) B.(100,120,110,130,80,60,90) C. (100,60,80,90,120,110,130) D.(100,80,60,90,120,130,110)
[tag_link]
正确答案：C
二叉排序树（BST）的构造过程是依次插入元素，每次从根结点开始比较插入。
分析各序列构造的BST形状：
A: 100为根 → 80左 → 90（80右）→ 60（80左）→ 120（100右）→ 110（120左）→ 130（120右）
B: 100为根 → 120右 → 110（120左）→ 130（120右）→ 80（100左）→ 60（80左）→ 90（80右） 与A最终结构相同。
C: 100为根 → 60左 → 80（60右）→ 90（80右）→ 120（100右）→ 110（120左）→ 130（120右） 与A结构不同，因为60直接成为100的左孩子（而非80成为100的左孩子）。
D: 100为根 → 80左 → 60（80左）→ 90（80右）→ 120（100右）→ 130（120右）→ 110（120左） 与A最终结构相同。
故C序列构造的BST与其它三个不同。
从空树开始，依次插入元素52,26,14,32,71,60,93,58,24和41后构成了一棵二叉排序 树。在该树查找60,要进行比较的次数为()。 A . 3 B.4 C.5 D.6
[tag_link]
正确答案：A
在含有n 个结点的二叉排序树中查找某个关键字的结点时，最多进行()次比较。 2 0 2 7 年 数 据 结 构 考 研 复 习 指 导292 2 0 2 7 年 数 据 结 构 考 研 复 习 指 导
A. n/2 B.log₂n C.log₂n + 1 D.n
[tag_link]
正确答案：D
五个不同结点构造的二叉查找树的形态共有()种。
A. 20 B. 30 C.32 D.42
[tag_link]
正确答案：D
构造一棵具有n 个结点的二叉排序树时，最理想情况下的深度为()。
A. n/2 B.n C.Llog₂(n+1)」 D.[log₂(n+1)7
[tag_link]
正确答案：D
含有20个结点的平衡二叉树的最大深度为()。
A. 4 B.5 C.6 D.7
[tag_link]
正确答案：C
具有5层结点的平衡二叉树至少有()个结点。
A. 10 B.12 C.15 D.17
[tag_link]
正确答案：B
高度为3的平衡二叉排序树的形态共有()种。
A. 13 B.14 C.16 D.15
[tag_link]
正确答案：D
在平衡二叉树的基本操作中，可能发生两次旋转的操作是()。
A. 添加、删除结点 B. 仅删除结点 C. 仅添加结点 D. 都不会
[tag_link]
正确答案：A
将关键字1,2,3, …,1024依次插入到初始为空的平衡二叉树中，假设只有一个根结点的 二叉树的高度为0,则插入结束后的平衡二叉树的高度为()。
A. 8 B.9 C.10 D . 11
[tag_link]
正确答案：C
下列关于红黑树和AVL树的说法中，不正确的是()。 I. 一棵含有n 个结点的红黑树的高度至多为2log₂(n+1) II. 若一个结点是红色的，则它的父结点和孩子结点都是黑色的 Ⅲ.红黑树的查询效率一般要优于含有相同结点数的AVL 树 IV. 若 AVL 树的某结点的左右孩子的平衡因子都是零，则该结点的平衡因子也是零
A. I 、Ⅲ B.Ⅲ C. Ⅱ 、IV D.Ⅲ 、IV
[tag_link]
正确答案：D
下列关于红黑树和AVL 树的描述中，不正确的是()。
A. 两者都属于自平衡的二叉树 B. 两者查找、插入、删除的时间复杂度都相同 C. 红黑树插入和删除过程至多有2次旋转操作 D. 红黑树的任意一个结点的左右子树高度(含叶结点)之比不超过2
[tag_link]
正确答案：C
下列关于红黑树的说法中，正确的是()。
A. 红黑树的红结点的数目最多和黑结点的数目相同(不考虑虚构结点) B. 若红黑树的所有结点都是黑色的，则它一定是一棵满二叉树 C. 红黑树的任何一个分支结点都有两个非空孩子结点 D. 红黑树的子树也一定是红黑树
[tag_link]
正确答案：B
下列四个选项中，满足红黑树定义的是()。
A. B. C.
[tag_link]
正确答案：
将关键字1,2,3,4,5,6,7依次插入初始为空的红黑树T, 则 T 中红结点的个数是()。
A. 1 B.2 C.3 D. 4
[tag_link]
正确答案：C
将关键字5,4,3,2,1依次插入初始为空的红黑树T, 则 T 的最终形态是()。
[tag_link]
正确答案：D
在下图所示的红黑树中插入结点2且染成红色后，则下一步应进行的操作是()。 A . B. C. D .
A. 左旋 B. 右旋 C. 变色 D. 无须调整 23. 【2009统考真题】下列二叉排序树中，满足平衡二叉树定义的是()。
[tag_link]
正确答案：B
一棵二叉排序树按先序遍历得到的序列为(50,38,30,45,40,48,70,60, 75,80),试画出该二叉排序树，并求出等概率下查找成功和查找失败的平均查找长度。
[tag_link]
C
按照序列(40,72,38,35,67,51,90,8,55,21)建立一棵二叉排序树，画出该树，并求出在 等概率的情况下，查找成功的平均查找长度。
[tag_link]
B
依次把结点(34,23,15,98,115,28,107)插入初始状态为空的平衡二叉排序树，使得在每次插 入后保持该树仍然是平衡二叉树。请依次画出每次插入后所形成的平衡二叉排序树。
[tag_link]
A
给定一个关键字集合{25,18,34,9,14,27,42,51,38},假定查找各关键字的概率相同， 请画出其最佳二叉排序树。
[tag_link]
B
试编写一个算法，判断给定的二叉树是否是二叉排序树。
[tag_link]
C
设计一个算法，求出指定结点在给定二叉排序树中的层次。
[tag_link]
C
利用二叉树遍历的思想编写一个判断二叉树是否是平衡二叉树的算法。
[tag_link]
A
设计一个算法，求出给定二叉排序树中最小和最大的关键字。
[tag_link]
D
设计一个算法，从大到小输出二叉排序树中所有值不小于k 的关键字。
[tag_link]
D
编写一个递归算法，在一棵有n 个结点的、随机建立的二叉排序树上查找第k(1≤k ≤n) 小的元素，并返回指向该结点的指针。要求算法的平均时间复杂度为 O(log₂n)。 二叉排序树的每个结点中除data、1child、rchild 等数据成员外，增加一个 count 成员，保存以该结点为根的子树上的结点个数。
[tag_link]
D