1. 二叉排序树（BST）中序遍历的结果是（ ）。

{{ select(1) }}

• 降序序列
• 升序序列
• 乱序序列
• 与插入顺序相关

2. 在二叉搜索树（BST）中，若中序遍历序列为 {1, 2, 3, 4, 5}，且先序遍历的第一个元素为 3，下列说法正确的是（ ）。

{{ select(2) }}

• 3 是根节点，2 是 3 的左子节点，4 是 3 的右子节点
• 该 BST 是平衡的
• 3 是根节点，1 是 3 的左子树中的最左节点
• 5 是 3 的右子节点

3. 代码实现了二叉排序树的插入函数（假设没有相同数值），横线处填入（ ）。 Node* insert(Node* root, int val) { if (root == nullptr) return new Node(val); if (val < root->val) root->left = insert(________, val); else root->right = insert(root->right, val); return root; }

{{ select(3) }}

• root->left
• root->right
• root
• nullptr

4. 对于一棵二叉排序树，删除一个节点时，若要删除的节点有左右两个孩子，通常采用（ ）来替换被删除节点。

{{ select(4) }}

• 左子树中的最大值
• 左子树中的最小值
• 右子树中的最大值
• 任意节点即可

5. 一棵二叉排序树的查找效率取决于（ ）。

{{ select(5) }}

• 树的形状
• 节点数量
• 插入顺序
• 以上都是

6. 代码实现一个二叉排序树的插入函数（没有相同的数值），横线处应填入（ ）。 Node* insert(Node* root, int val) { if (root == nullptr) return new Node(val); if (val < root->val) root->left = insert(root->left, val); else root->right = insert(________, val); return root; }

{{ select(6) }}

• root->left
• root->right
• root
• nullptr

7. 对二叉排序树进行中序遍历得到的序列是（ ）。

{{ select(7) }}

• 递增序列
• 递减序列
• 先递增后递减
• 随机序列

8. 下面关于二叉排序树查找的描述，正确的是（ ）。

{{ select(8) }}

• 查找操作最坏情况下的时间复杂度是 O(log n)
• 查找操作最好情况下的时间复杂度是 O(1)
• 查找操作的时间复杂度与树的形状无关
• 查找操作只能递归实现

9. 在二叉搜索树中，查找一个节点的时间复杂度最好为（ ）。

{{ select(9) }}

• O(1)
• O(log n)
• O(n)
• O(n²)

10. 对于一棵二叉搜索树，如果要实现一个查找函数，下列算法中最合适的是（ ）。

{{ select(10) }}

• 二分查找
• 顺序查找
• 分块查找
• 哈希查找

11. 关于二叉排序树（BST），下列哪些说法是正确的？（ ）

{{ multiselect(11) }}

• 左子树中所有节点的值均小于根节点的值
• 中序遍历 BST 可以得到一个升序序列
• BST 的查找效率与树的高度有关
• 删除 BST 中的节点时，如果被删除节点有左右子树，可以用左子树的最大节点来替换

12. 关于二叉排序树的查找，下列说法正确的有（ ）。

{{ multiselect(12) }}

• 平均查找长度与树的形状有关
• 最坏情况下查找效率退化为 O(n)
• 二叉排序树查找效率一定高于顺序查找
• 插入和删除操作会改变树的形状

13. 对一棵二叉排序树进行中序遍历，可以得到一个递增的有序序列。（ ）

{{ select(13) }}

• 正确
• 错误

14. 二叉搜索树在连续的插入和删除操作后，所有节点都偏向一侧，可能导致退化为类似于链表的结构，此时查找、插入、删除操作的时间复杂度会从 O(log n) 退化到 O(n)。（ ）

{{ select(14) }}

• 正确
• 错误

15. 二叉排序树的查找、插入和删除操作的平均时间复杂度都是 O(log n)。（ ）

{{ select(15) }}

• 正确
• 错误