目标

通过 2009～2025 年的 18 道 408 选择题，检查自己能否准确处理 B 树与 B+ 树的结构边界、插入删除调整，以及散列表冲突处理与平均查找长度。

完成后应能：

• 根据 m 阶 B 树的结点上下界判断合法结构，推演插入与删除；
• 区分 B 树和 B+ 树的查找终点、叶结点链接和应用场景；
• 构造开放定址散列表，分别计算成功与失败 ASL；
• 说明散列函数、冲突策略与装填因子怎样影响查找效率。

前置知识

建议依次阅读：

• 8.4 B 树与 B+ 树
• 8.5 散列表

环境、输入与预期输出

• 环境：任意现代浏览器；建议准备纸笔，用于画 B 树和散列表。
• 输入：按年份排列的 18 道单项选择题，每题恰有四个选项。
• 预期输出：一份独立作答记录，以及每道错题的错误原因和正确推理。

作答方法

1. 阅读题面后点击一个选项，先写下选择依据；
2. 点击"提交答案"，再核对对错、正确答案和题解；
3. 做错的题点击"重新作答"后再次推导，直到能说明其余选项为什么不成立；
4. 完成全部题目后再使用页面末尾的答案总览复核，避免只记答案字母。

选择题

答题进度已答 0/18正确 0

第 1 题

难度基础考点B 树、基本性质标识search-408-2009-q08

下列叙述中，不符合 m 阶 B 树定义要求的是（ ）。

请选择一个答案

A根结点最多有 m 棵子树

B所有叶结点都在同一层上

C各结点内关键字均升序或降序排列

D叶结点之间通过指针链接

第 2 题

难度基础考点散列表、装填因子、冲突处理标识search-408-2011-q09

为提高哈希表的查找效率，可以采取的正确措施是（ ）。

I. 增大装填因子
II. 设计冲突少的哈希函数
III. 处理冲突时避免产生堆积现象

请选择一个答案

A仅 I

B仅 II

C仅 I、II

D仅 II、III

第 3 题

难度进阶考点B 树、删除、借键标识search-408-2012-q09

已知一棵 3 阶 B 树如下，每个方括号表示一个结点：

                [45]
          /               \
      [17,35]            [55,65]
     /   |   \          /   |    \
  [10] [21] [37]      [47] [60,62] [78]

删除关键字 78 得到一棵新 B 树，其最右叶结点中的关键字是（ ）。

请选择一个答案

A60

B60，62

C62，65

D65

第 4 题

难度基础考点B 树、最少关键字标识search-408-2013-q10

在一棵高度为 2 的 5 阶 B 树中，所含关键字的个数最少是（ ）。题目把根结点计为第 1 层。

请选择一个答案

A5

B7

C8

D14

第 5 题

难度基础考点散列表、堆积、平均查找长度标识search-408-2014-q08

用散列方法处理冲突时可能出现堆积现象。下列选项中，会受堆积现象直接影响的是（ ）。

请选择一个答案

A存储效率

B散列函数

C装填因子

D平均查找长度

第 6 题

难度基础考点B 树、结点数量标识search-408-2014-q09

在一棵具有 15 个关键字的 4 阶 B 树中，含关键字的结点个数最多是（ ）。

请选择一个答案

A5

B6

C10

D15

第 7 题

难度基础考点B 树、B+ 树、顺序查找标识search-408-2016-q10

B+ 树不同于 B 树的特点之一是（ ）。

请选择一个答案

A能支持顺序查找

B结点中含有关键字

C根结点至少有两个分支

D所有叶结点都在同一层上

第 8 题

难度基础考点B+ 树、应用场景标识search-408-2017-q09

下列应用中，适合使用 B+ 树的是（ ）。

请选择一个答案

A编译器中的词法分析

B关系数据库系统中的索引

C网络中的路由表快速查找

D操作系统的磁盘空闲块管理

第 9 题

难度基础考点B 树、最少关键字、树高标识search-408-2018-q08

高度为 5 的 3 阶 B 树含有的关键字个数至少是（ ）。题目把根结点计为第 1 层。

请选择一个答案

A15

B31

C62

D242

第 10 题

难度基础考点散列表、线性探测、成功 ASL标识search-408-2018-q09

现有长度为 7、初始为空的散列表 HT，散列函数 $H(k)=kmod7$，用线性探测再散列法解决冲突。将关键字 22、43、15 依次插入 HT 后，查找成功的平均查找长度是（ ）。

请选择一个答案

A1.5

B1.6

C2

D3

第 11 题

难度进阶考点散列表、线性探测、失败 ASL标识search-408-2019-q08

现有长度为 11 且初始为空的散列表 HT，散列函数为 $H(key)=keymod7$，采用线性探测法解决冲突。将关键字序列 87、40、30、6、11、22、98、20 依次插入后，HT 查找失败的平均查找长度是（ ）。

请选择一个答案

A4

B5.25

C6

D6.29

第 12 题

难度进阶考点B 树、插入、分裂标识search-408-2020-q10

依次将关键字 5、6、9、13、8、2、12、15 插入初始为空的 4 阶 B 树后，根结点中包含的关键字是（ ）。

请选择一个答案

A8

B6，9

C8，13

D9，12

第 13 题

难度进阶考点B 树、删除、借键、合并标识search-408-2022-q08

5 阶 B 树 T 的根和五个叶孩子如下：

根：[60, 90, 260, 350]
孩子：[30,50] | [70,80,85] | [100,110] | [280,300] | [400,500]

删除关键字 260 并完成必要调整后得到 T1。下列选项中，不可能是 T1 根结点关键字序列的是（ ）。

请选择一个答案

A60，90，280

B60，90，350

C60，85，110，350

D60，90，110，350

第 14 题

难度基础考点散列表、平均查找长度标识search-408-2022-q09

下列因素中，影响散列方法平均查找长度的是（ ）。

I. 装填因子
II. 散列函数
III. 冲突解决策略

请选择一个答案

A仅 I、II

B仅 I、III

C仅 II、III

DI、II、III

第 15 题

难度进阶考点B 树、插入、删除、查找标识search-408-2023-q07

下列关于非空 B 树的叙述中，正确的是（ ）。

I. 插入操作可能增加树的高度
II. 删除操作一定会导致叶结点的变化
III. 查找某关键字一定要查找到叶结点
IV. 插入的新关键字最终位于叶结点中

请选择一个答案

A仅 I

B仅 I、II

C仅 III、IV

D仅 I、II、IV

第 16 题

难度进阶考点散列表、删除标记、失败 ASL标识search-408-2023-q09

现有长度为 5、初始为空的散列表 HT，散列函数 $H(k)=(k+4)mod5$，用线性探测法解决冲突。将 2022、12、25 依次插入后删除关键字 25（保留删除标记），则 HT 查找失败的平均查找长度是（ ）。

请选择一个答案

A1

B1.6

C1.8

D2.2

第 17 题

难度进阶考点B 树、结构计数标识search-408-2025-q08

给定 7 个不同的关键字，能够构成不同 4 阶 B 树的个数为（ ）。这里只区分结点中关键字数量形成的合法树形。

请选择一个答案

A7

B8

C9

D10

第 18 题

难度基础考点散列表、线性探测、平方探测标识search-408-2025-q09

下列关于散列法处理冲突的叙述中，正确的是（ ）。

请选择一个答案

A只要散列表不满，线性探测再散列一定能找到一个空闲位置

B只要散列表不满，平方探测再散列一定能找到一个空闲位置

C线性探测再散列处理的冲突一定发生在同义词之间

D平方探测再散列处理的冲突一定发生在非同义词之间

答案总览（建议完成全部题目后查看）

1. 第 1 题：D
2. 第 2 题：D
3. 第 3 题：D
4. 第 4 题：A
5. 第 5 题：D
6. 第 6 题：D
7. 第 7 题：A
8. 第 8 题：B
9. 第 9 题：B
10. 第 10 题：C
11. 第 11 题：C
12. 第 12 题：B
13. 第 13 题：D
14. 第 14 题：D
15. 第 15 题：B
16. 第 16 题：C
17. 第 17 题：C
18. 第 18 题：A

完成清单

• 18 道题均在提交答案前独立作答；
• 每道错题都记录了错误原因，而不只抄写正确答案；
• 能对至少两道 B 树题画出插入/删除前后的完整结构变化；
• 能独立构造开放定址散列表，并分别写出成功与失败 ASL 的推导。

思考题

1. B 树与 B+ 树在"查找终点"和"叶结点链接"上的差别，如何决定它们的应用场景？
2. 装填因子、散列函数、冲突解决策略三者各自怎样影响平均查找长度？
3. 线性探测的"堆积"与平方探测的"不一定覆盖全表"分别意味着什么？

复盘

• 我是否在计算失败 ASL 时误用了成功查找的比较口径？
• B 树的借键与合并，我是否清楚什么时候上移、什么时候下移？
• 哪道题的干扰项利用了"B 树与 B+ 树性质混记"的常见误区？