数据结构查找（王道习题）

一、顺序查找和折半查找

1 顺序查找

2 再看

3

4

5 二分查找 错题

6 顺序存储的折半查找和顺序查找

综合以上分析，顺序存储的折半查找与顺序查找速度（比较次数）一致的情况，集中在表长极小（n≤2） 的极端场景，具体可归纳为 3 类：

1. 表长 n=1：无论查找 “存在的目标” 还是 “不存在的目标”，两者均只需 1 次比较，速度完全一致；
2. 表长 n=2：
   • 查找 “存在的目标”（a1 或 a2）：比较次数分别为 1 次、2 次，与顺序查找完全相同；
   • 查找 “不存在的目标”：两者均需 2 次比较，速度一致；
3. n>2 时无一致场景：此时折半查找通过 “折半缩区间”，比较次数始终≤顺序查找（最坏情况为log₂(n+1)次，远小于顺序查找的n次），速度必然更快，无一致可能。

简言之，仅当有序表的长度为 1 或 2 时，折半查找的速度才可能与顺序查找一样；表长超过 2 后，折半查找的效率优势会完全体现，速度始终优于顺序查找。

7 折半查找判定树 错题

8 折半查找和二叉排序树的区别 记结论

选B

9 模拟折半查找

10 注意折半查找是下标移动 ，再看

11 折半查找

12 错题，折半查找判定树的高度 很重要

13 不会，判定树，必须再看，向下取整，右子树和左子树的关系

14 查找成功、查找失败平均查找长度， 不会

15 错题

16 分块查找的概念，重要

17 分块查找的计算

18 分块查找计算

19 再看，分块计算

20 真题

21 错题再看，15年真题

必须一口气

22 再看不会

23 再看不会

24 不会，画判定树

25

二、树型查找

26 二叉排序树

27

28

29

30 二叉排序树的查找

31

答案C

32

33

34 重点题、划归思想、卡特兰数（n个结点二叉树形态的总数）

34 重点题、取特殊值法

35 重点题、平衡二叉树的性质

36

37 错题，划归的方法，注意 1 1 这种情况只有两层