目标

通过 2009～2025 年的 7 道 408 真题与 8 道王道习题，检查自己能否准确处理顺序查找、分块查找与折半查找的前提条件、比较次数与判定树形态。

完成后应能：

• 写出顺序、分块和折半查找各自成立的前提与比较次数；
• 说明折半查找对"有序 + 随机访问"的双重依赖；
• 判别一棵二叉树能否成为折半查找判定树（mid 取整一致性）；
• 由折半判定树高度推算失败查找的最多比较次数；
• 判断一种存储结构或查找序列能否用折半查找；
• 由最优块长理解分块查找两级代价的权衡。

前置知识

建议先阅读 8.1 基础查找与折半查找，并复习 8.2 节二叉排序树中"查找路径"的对比视角。

环境、输入与预期输出

• 环境：任意现代浏览器；建议准备纸笔，用于画折半判定树。
• 输入：本页 15 道单项选择题（真题与王道习题按主题排列）。
• 预期输出：一份独立作答记录，以及每道错题的错误原因和正确推理。

作答方法

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

选择题

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

第 1 题

难度基础考点顺序查找、存储结构标识search-wd72-q01

顺序查找适合于存储结构为（ ）的线性表。

请选择一个答案

A顺序存储结构或链式存储结构

B散列存储结构

C索引存储结构

D压缩存储结构

第 2 题

难度进阶考点顺序查找、平均时间标识search-wd72-q02

由 n 个数据元素组成的两个表：一个递增有序，一个无序。采用顺序查找算法，对有序表从头开始查找，发现当前元素已不小于待查元素时，停止查找，确定查找不成功。已知查找任意一个元素的概率相同，则在两种表中成功查找（ ）。

请选择一个答案

A平均时间后者小

B平均时间两者相同

C平均时间前者小

D无法确定

第 3 题

难度基础考点折半查找、前提条件标识search-wd72-q05

下列关于二分查找的叙述中，正确的是（ ）。

请选择一个答案

A表必须有序，表可以顺序方式存储，也可以链表方式存储

B表必须有序且表中数据必须是整型、实型或字符型

C表必须有序，而且只能从小到大排列

D表必须有序，且表只能以顺序方式存储

第 4 题

难度基础考点折半查找、存储结构标识search-408-2024-q05

下列数据结构中，不适合直接使用折半查找的是（ ）。

I. 有序链表
II. 无序数组
III. 有序静态链表
IV. 无序静态链表

请选择一个答案

A仅 I、II

B仅 II、IV

C仅 I、II、IV

DI、II、III、IV

第 5 题

难度基础考点折半查找、比较次数标识search-408-2010-q09

已知一个长度为 16 的顺序表 L，其元素按关键字有序排列。若采用折半查找法查找一个 L 中不存在的元素，则关键字的比较次数最多是（ ）。

请选择一个答案

A4

B5

C6

D7

第 6 题

难度基础考点折半查找、比较次数标识search-408-2023-q08

对含有 600 个元素的有序顺序表进行折半查找，关键字之间的比较次数最多是（ ）。

请选择一个答案

A9

B10

C30

D300

第 7 题

难度基础考点折半查找、比较序列标识search-wd72-q09

在有 11 个元素的有序表 A[1, 2, …, 11] 中进行折半查找（$\lfloor (\text{low}+\text{high})/2\rfloor$），查找元素 A[11] 时，被比较的元素下标依次是（ ）。

请选择一个答案

A6, 8, 10, 11

B6, 9, 10, 11

C6, 7, 9, 11

D6, 8, 9, 11

第 8 题

难度基础考点折半查找、判定树高度标识search-wd72-q12

对长度为 n 的有序表进行折半查找，其判定树的高度为（ ）。

请选择一个答案

A$\lceil {\log }_2(n+1)\rceil$

B$\lfloor {\log }_2(n+1)\rfloor -1$

C$\lceil {\log }_{2}n\rceil$

D$\lfloor {\log }_{2}n\rfloor -1$

第 9 题

难度基础考点折半查找、判定树标识search-wd72-q07

折半查找过程所对应的判定树是一棵（ ）。

请选择一个答案

A最小生成树

B平衡二叉树

C完全二叉树

D满二叉树

第 10 题

难度进阶考点折半查找、判定树形态标识search-408-2017-q08

下列二叉树中，可能成为折半查找判定树（不含外部结点）的是（ ）。选项以 1(2(3,_),4) 式记法表示树形：括号内依次为左、右子树，_ 表示空指针，标号仅为表述方便。

请选择一个答案

A1(2(4(8,_),5(9,_)),3(6(10,_),7))

B1(2(4(8,_),5),3(6(_,10),7(_,9)))

C1(2(3(4,5),_),6(7(_,9),8(_,10)))

D1(2(4(8,_),5),3(6,7(9,10)))

第 11 题

难度基础考点折半查找、比较序列标识search-408-2015-q07

下列选项中，不能构成折半查找中关键字比较序列的是（ ）。

请选择一个答案

A500，200，450，180

B500，450，200，180

C180，500，200，450

D180，200，500，450

第 12 题

难度进阶考点顺序查找、折半查找、比较次数标识search-408-2016-q09

在有 $n$（$n>1000$）个元素的升序数组 A 中查找关键字 x。算法每次让 k 增加 3，再依次检查 A[k]、A[k-1]、A[k-2]。本算法与折半查找相比，有可能具有更少比较次数的情形是（ ）。

c

k = 0;
while (k < n && A[k] < x) k = k + 3;
if (k < n && A[k] == x) success;
else if (k - 1 < n && A[k - 1] == x) success;
else if (k - 2 < n && A[k - 2] == x) success;
else fail;

请选择一个答案

A当 x 不在数组中

B当 x 接近数组开头处

C当 x 接近数组结尾处

D当 x 位于数组中间位置

第 13 题

难度基础考点分块查找、最优块长标识search-408-2025-q07

已知查找表中有 400 个元素，各元素查找概率相同。采用均匀分块查找，使用顺序查找确定元素所在块，块内也使用顺序查找。为使效率最高，每块应包含（ ）个元素。

请选择一个答案

A8

B10

C20

D25

第 14 题

难度基础考点分块查找、组织方式标识search-wd72-q16

采用分块查找时，数据的组织方式为（ ）。

请选择一个答案

A数据分成若干块，每块内数据有序

B数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D数据分成若干块，每块（除最后一块外）中数据个数需相同

第 15 题

难度进阶考点分块查找、最优块长标识search-wd72-q17

对有 2500 个记录的索引顺序表（分块表）进行查找，最理想的块长为（ ）。

请选择一个答案

A50

B125

C500

D$\lceil {\log }_{2}2500\rceil$

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

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

完成清单

• 15 道题均在提交答案前独立作答；
• 每道错题都记录了错误原因，而不只抄写正确答案；
• 能画出至少两道折半查找题的判定树并说明高度；
• 能解释分块查找为什么取最优块长 √n 附近的值。

思考题

1. 为什么折半查找同时要求"有序"和"随机访问"，缺一不可？
2. 分块查找的两级顺序查找，代价为什么近似正比于 s + n/s？
3. 顺序查找在什么情况下反而是比折半查找更合理的选择？

复盘

• 我是否混淆了"最多比较次数"和"平均比较次数"？
• 哪道题我靠记结论作答，而没有回到判定树或上下界推导？
• 分块查找的块长权衡里，我在哪一步最容易被"块越细越好"的直觉带偏？