计算机笔试面试题库

外观

六、查找（第 65-78 题） ​

65. 二分查找（折半查找）的时间复杂度为( ) ​

标签：【互联网/国企笔试超高频】

A. O(1) B. O(log n) C. O(n) D. O(n log n)

答案：B

【结论】 时间复杂度为 O(log n)，选 B。

【逐项辨析】

  • A O(1)：这是哈希表查找的平均复杂度。
  • B O(log n)：正确。 每次把搜索范围缩小一半。
  • C O(n)：这是顺序查找的复杂度。
  • D O(n log n)：这是排序的复杂度，不是单次查找。

【知识点】 二分查找（折半查找）的原理

每次取中间元素 a[mid] 与目标 key 比较:
  a[mid] == key → 命中
  a[mid] >  key → 在左半区继续找(high = mid − 1)
  a[mid] <  key → 在右半区继续找(low  = mid + 1)

范围变化:n → n/2 → n/4 → ... → 1
比较次数 = log₂n 量级
查找算法时间复杂度前提条件
顺序查找O(n)无
二分查找O(log n)有序 + 随机访问
二叉排序树查找平均 O(log n)、最坏 O(n)需建树
哈希查找平均 O(1)需设计哈希函数

【记忆锚点】 “每次砍一半，次数就是 log₂n”——n = 1024 最多比较 ⌊log₂1024⌋+1 = 11 次（与本题【自测】、第 67 题公式一致）。

【易混对比】 二分查找的两个前提缺一不可:①数据有序;②支持随机访问（通常用数组）。链表虽然可以有序，但无法 O(1) 取中点，所以不能用二分（见第 76 题）。

【自测】 在 1024 个有序元素中做二分查找，最多需要比较几次？

答：⌊log₂1024⌋ + 1 = 11 次。与第 67 题连考。

【知识关联】

  • 同库连考：与第 66 题（前提有序+随机访问）、第 67 题（最坏比较 ⌊log₂n⌋+1）、第 68 题（顺序查找 O(n)）、第 74/76 题（查找比较与折半适用结构）构成查找专题；与第 71/105 题（哈希 ASL）对比 O(log n) vs 平均 O(1)。
  • 工程实现：Arrays.binarySearch、C++ lower_bound、数据库页内二分、Git bisect（用二分定位引入 bug 的提交）、配置阈值/版本回退搜索，都是 O(log n) 工程化。10 亿数据二分约 30 次比较，这是面试最爱给的数量级例子。
  • 408 / 国企真题：408 与国网「折半查找时间复杂度」必考 O(log n)；常配套问「最多比较几次」。干扰项 O(1) 是哈希，O(n) 是顺序查找。
  • 面试追问:①「n=1024 最多几次？」（11）；②「二分 mid 如何防溢出？」（lo+(hi-lo)/2）；③「有重复元素找第一个？」（lower_bound 变体，不是标准 binarySearch）。

【拓展延伸】

变式问法:①「二分复杂度？」（O(log n)，本题）；②「前提？」（有序+随机访问）；③「插值查找对均匀数据？」（期望更快，最坏仍可能 O(n)）。

工程映射：性能回归用 Git bisect；游戏数值表二分定位；IP 库/路由表前缀查找的决策树化；有序 LSM 内存块点查。

易错提醒：O(log n) 是渐进最坏/平均量级；严格最坏次数是 ⌊log₂n⌋+1。链表有序也不能二分，复杂度会因取中点退化。

66. 二分查找要求数据满足的条件是( ) ​

标签：【互联网/国企笔试高频】

A. 数据有序且支持随机访问 B. 数据无序 C. 数据存储在链表中 D. 数据元素唯一

答案：A

【结论】 要求“数据有序且支持随机访问”，选 A。

【逐项辨析】

  • B 错：无序数据无法判断该往哪半边找，二分无从下手。
  • A 对：两个前提是数据有序 + 支持随机访问。
  • C 错：链表不支持随机访问，不能二分。
  • D 错：元素唯一不是二分查找的前提（有重复元素也能二分，只是找到的位置可能不是第一个 / 最后一个）。

【知识点】 二分查找的两个前提（缺一不可）：

前提为什么必须反例
数据有序才能通过比较决定往左还是往右无序数组 → 无法确定半区
支持随机访问才能 O(1) 取到中点链表 → 取中点要 O(n)
有序但链表:能比大小,但每次取中点都要从头走 → 二分优势被抵消
无序但数组:能 O(1) 取中点,但不知往哪边走 → 二分失效

【记忆锚点】 “有序定方向，随机访问取中点”——两个条件各管一件事。

【易混对比】 “元素唯一”常被设为干扰项 —— 二分查找不要求元素唯一。当有重复元素时，标准二分可能返回其中任意一个；若要找“第一个 / 最后一个等于目标值”的位置，需用变体（如 lower_bound / upper_bound）。与第 76 题同考点。

【自测】 有序数组中有重复元素，会影响二分查找的“是否存在”判断吗？

答：不影响是否存在的判断，但可能返回任意一个匹配位置。若要定位首个 / 末个匹配，需用二分变体。与第 76 题连考。

【知识关联】

  • 同库连考：与第 76 题（折半查找适用于有序顺序表）是同一考点的两种问法——本题问「条件是什么」，第 76 题问「哪种结构满足」；与第 65、74 题（二分相关）同专题；与第 12 题（链表不能 O(1) 取第 i 个）因果相连：正是缺随机访问，有序链表也无法二分。
  • 工程实现：java.util.Arrays.binarySearch 要求数组（随机访问+应先有序）；LinkedList 即使数据有序也不能调二分 API；跳表（ConcurrentSkipListMap）通过多层索引在链表上“造出”近似随机访问；B+ 树叶子有序+页号随机读，是磁盘版的「有序+可定位」。
  • 408 / 国企真题：408 与国网「二分查找前提」超高频，干扰项固定套路：①「数据无序」②「存储在链表中」③「元素唯一」——三者都不对。真题还常反过来考「有序链表能否二分」。
  • 面试追问:①「有序单链表能不能二分？」（标准算法不能；取中点 O(n) 会把整体拖成 O(n)）；②「为什么不要求元素唯一？」（判定存在仍正确，只是返回的可能是任一下标；要 first/last 需 lower_bound 变体）；③「哈希表数据能二分吗？」（无序，不能）。

【拓展延伸】

变式问法:①「二分查找要求？」（有序且随机访问，本题）；②「对有序链表做二分，时间复杂度？」（退化为 O(n)，因每次取中点 O(n)）；③「若给链表附加指向中点的指针/建索引呢？」（可接近二分，本质是跳表/索引的思想）。

工程映射：数据库为什么用 B+ 树而不是「有序链表」——页是随机访问单元，键在页内有序，才能在磁盘上实现 O(log n) 点查；LSM 的分层有序 run + 稀疏索引，也是「有序 + 可定位」的工程化。

易错提醒：「有序」和「随机访问」缺一不可，考试爱用「有序链表」做最强干扰；「元素唯一」不是前提。另外二分 mid 计算注意防溢出：low + (high-low)/2。

67. 对长度为n的有序表进行二分查找，最多需要比较( )次。 ​

标签：【互联网/国企笔试高频】

A. n B. n/2 C. ⌊log₂n⌋ + 1 D. log₂n

答案：C

【结论】 最多比较 ⌊log₂n⌋ + 1 次，选 C。

【逐项辨析】

  • A n：这是顺序查找的最坏比较次数。
  • B n/2：无依据。
  • C ⌊log₂n⌋ + 1：正确。 等于二分查找判定树的高度。
  • D log₂n：漏了 +1（判定树的层数从 1 计）。

【知识点】 二分查找的比较次数与判定树

二分查找的判定树是一棵平衡的二叉排序树:
  根     = 第一次比较的中间元素
  左子树 = 左半区,右子树 = 右半区
  树的高度 = 最多比较次数 = ⌊log₂n⌋ + 1
n⌊log₂n⌋ + 1最多比较次数
111
733
1044
10077
10001010
n = 10 的判定树（mid=⌊(lo+hi)/2⌋，树高 4；内部结点 10 个、失败外部叶子 11 个）：
                 5
              /     \
             2       8
            / \     / \
           1   3   6   9
                \   \   \
                 4   7  10
（3 的右孩子 4、6 的右孩子 7 不能省 —— 缺了它们就只有 8 个内部结点，凑不满 n=10）

【记忆锚点】 “比较次数 = 判定树高度 = ⌊log₂n⌋ + 1”。

【易混对比】 注意与第 68 题区分

查找算法平均查找长度 ASL最坏比较次数
顺序查找(n+1)/2n
二分查找≈ log₂n⌊log₂n⌋ + 1

二分查找的比较次数是对数级，顺序查找是线性级 —— 这是两者最本质的差别。

【自测】 对长度为 100 的有序表做二分查找，最多比较几次？

答：⌊log₂100⌋ + 1 = 6 + 1 = 7 次。与第 65 题连考。

【知识关联】

  • 同库连考：与第 6 题（循环次数含 log₂n）、第 35 题（完全二叉树深度 ⌊log₂n⌋+1）同一对数骨架——二分判定树高度 = 完全二叉树深度公式；与第 65/66/76 题（二分前提）配套；与第 68 题（顺序查找最坏 n 次）对照「对数 vs 线性」。
  • 工程实现：超时/重试设计按「最多比较次数」估上界；Java Arrays.binarySearch 内部循环次数受同一公式约束；Redis 跳表、有序集合查找代价也按层高 ≈ log 量级理解。二分查找判定树的平均查找长度 ASL ≈ log₂n（更精确与成功/失败路径有关），最坏才是 ⌊log₂n⌋+1。
  • 408 / 国企真题：408 原题「长度为 n 的有序表二分最多比较次数」答案 ⌊log₂n⌋+1 或等价的 ⌈log₂(n+1)⌉——两式对所有正整数 n 恒等（穷举 n=1..1999 无一例外），不是「只在 2^k−1 时相同」，教材只是写法不同；国网常给 n=10/100/1000 直接算次数。
  • 面试追问:①「n=1024 最多几次？」（⌊log₂1024⌋+1=11）；②「n=1000 呢？」（⌊log₂1000⌋=9，+1=10）；③「平均比较次数？」（约等于判定树的平均深度，成功时 ≈ log₂n 量级）。

【拓展延伸】

变式问法:①「最多比较几次？」（⌊log₂n⌋+1，本题）；②「查找失败最多几次？」（同样不超过判定树高度）；③「判定树有多少叶子/内部结点？」（与 n 相关，失败结点 n+1 个外部结点的模型）。

工程映射：性能上界用对数估——「10 亿数据二分最多约 30 次比较」；分页 UI、游戏数值表二分定位、IP 库最长前缀匹配的决策树高度，都按 log n 设计 SLA。

易错提醒：选项 D log₂n 少加 1，是最高频错选；公式来自树高从第 1 层起算，不是边数。再提醒：本库第 35 题（完全二叉树深度 ⌊log₂n⌋+1）用的就是这个式子，三处口径已统一为「恒等」。

68. 顺序查找的平均查找长度(ASL)为( ) ​

标签：【互联网/国企笔试高频】

A. (n+1)/2 B. n/2 C. log₂n D. n

答案：A

【结论】 顺序查找 ASL = (n+1)/2，选 A。

【推导过程】 等概率下，查找第 i 个元素需要比较 i 次

ASL成功 = (1 + 2 + 3 + ... + n) / n
       = [n(n+1)/2] / n
       = (n+1)/2
元素位置比较次数概率
第 1 个11/n
第 2 个21/n
………
第 n 个n1/n

【逐项辨析】

  • A (n+1)/2：正确。 等概率下的平均比较次数。
  • B n/2：与“顺序表插入平均移动 n/2”混淆了（见第 17 题）。
  • C log₂n：这是二分查找的量级。
  • D n：这是最坏比较次数（查找最后一个元素，或按不计表外那次判定的口径统计查找失败，见下方【知识点】）。

【知识点】 顺序查找的两种 ASL（必背）：

查找成功:ASL成功 = (n+1)/2
查找失败:ASL失败 = n + 1        (计入「表外失败判定/哨兵」那一次比较的教材口径)
          另一口径:只与表内 n 个元素比、不计那次表外判定 → ASL失败 = n
两式只差「是否计入表外那次比较」,不是两个互相矛盾的结论:背 n + 1 时说明含表外判定,选项里只有 n 时按不含口径选它。

哨兵优化： 把待查找的关键字放在数组下标 0 的位置（或末尾）作为哨兵，循环时不必每次判断下标越界，可减少约一半的比较次数。

普通写法:for (i = n; i >= 1 && a[i] != key; i--);   ← 每次比两个条件
哨兵法:  a[0] = key;                                  ← 哨兵
        for (i = n; a[i] != key; i--);                ← 每次只比一个条件
        返回 i(若 i == 0 则查找失败)

【记忆锚点】 “顺序查找从 1 加到 n，平均就是 (n+1)/2”。

【易混对比】 三组“平均数字”务必分清（国企笔试最爱考）：

操作平均代价记忆点
顺序表插入n/2位置数 n+1
顺序表删除(n−1)/2位置数 n
顺序查找(n+1)/2比较次数从 1 到 n

【自测】 对长度为 10 的顺序表做顺序查找，平均查找长度是多少？

答：(10+1)/2 = 5.5。与第 17 题连考。

【知识关联】

  • 同库连考：与第 17 题三连数字（插 n/2、删 (n−1)/2、查 (n+1)/2)必须一起背；与第 65 题（二分）对比。
  • 工程实现：线性扫描 indexOf；小数组顺序查往往比二分快（常数小）。
  • 408 / 国企真题:2025 国网同型；408 ASL。
  • 面试追问:①「失败 ASL？」(不计表外那次判定是 n,含表外判定是 n+1,先问口径);②「有序顺序查找成功平均？」((n+1)/2 仍，可早停）。

【拓展延伸】

完整验算:

成功:[1+2+...+n]/n = (n+1)/2
失败:n 个元素都比完 → n;再加上表外那次失败判定 → n+1(与【知识点】的 n+1 是同一件事的两种口径,不是两个答案)
若「下标哨兵」(a[0]=key)从尾部反查,可少判断下标越界,关键字比较次数不变

变式：各元素查找概率不等时按概率降序放表头可降 ASL。

工程应用：小表扫描、配置项查找。

69. 在一棵二叉排序树中查找关键字，最坏情况下的时间复杂度为( ) ​

标签：【互联网/国企笔试高频】

A. O(1) B. O(log n) C. O(n) D. O(n log n)

答案：C

【结论】 最坏情况下退化为 O(n)，选 C。

【逐项辨析】

  • A O(1)：哈希表才能达到。
  • B O(log n)：这是 BST 平衡时的复杂度。
  • C O(n)：正确。 BST 退化成单链时，查找要走到链尾。
  • D O(n log n)：这是排序的量级。

【知识点】 BST 查找复杂度与树高的关系

查找复杂度 = O(树高 h)

平衡时:h = O(log n) → 查找 O(log n)
退化成链:h = n      → 查找 O(n)

退化的原因： 按有序序列插入时，每个新结点都挂在最右侧（或最左侧），树变成单链。

插入 1, 2, 3, 4, 5(有序):
1                    查找 5 需要比较 5 次
 \
  2                  → 退化为 O(n)
   \
    3
     \
      4
       \
        5

解决办法： 使用自平衡二叉搜索树 —— AVL 树、红黑树，可保证树高恒为 O(log n)。

【记忆锚点】 “有序插入必退化，自平衡树来救场”。

【易混对比】 与第 43 题（平均 O(log n))对照：题目问“平均”选 O(log n)，问“最坏”选 O(n)。这一对是“查找”模块最高频的对照考点。

【自测】 依次插入 1、2、3、4、5、6 构造 BST，树的高度是多少？

答：6。完全退化成单链，高度 = 结点数。与第 43 题连考。

【知识关联】

  • 同库连考：与第 43 题（BST 查找平均 O(log n)）构成「平均 vs 最坏」对照双题——问平均选 log n，问最坏选 n；与第 70 题（AVL：最坏也是 O(log n)，比「平均」更强的保证）连考；与第 46 题（BST 删除）同属 BST 操作；与红黑树/AVL 相关题（第 39/45 题一带）给出「如何避免退化」的手段。
  • 工程实现：Java TreeMap/TreeSet 底层是红黑树，树高保证 O(log n)，不会因有序插入退化；HashMap 在 JDK8 起、同一桶结点数超过 8（即插入第 9 个）且 table.length ≥ 64 时树化为红黑树（代码常量 TREEIFY_THRESHOLD=8；JDK 17 实测：同 hashCode 的键在第 8 个时桶内仍是 Node，第 9 个才变 TreeNode；初始容量 <64 时先扩容、不树化），防的正是「哈希冲突长链 → O(n) 查找」这一与 BST 退化同构的问题；数据库索引用 B/B+ 树、跳表，动机相同。
  • 408 / 国企真题：408「二叉排序树查找最坏时间复杂度」标准答案 O(n)；国网/银行科技岗常同时给「平均」与「最坏」两个空，务必看清题干。真题还常考「依次插入有序序列，树的形态」→ 单支树。
  • 面试追问:①「1,2,3,4,5 依次插入，树高多少？」（5，退化成右链）；②「查找第 5 个关键字比较几次？」（5 次=O(n)）；③「工程上怎么保证不退化？」（AVL/红黑树/随机化插入/Treap；或直接用哈希/跳表）。

【拓展延伸】

变式问法:①「BST 最坏查找？」（O(n)，本题）；②「平均？」（O(log n)，随机插入假设）；③「AVL/红黑树最坏？」（O(log n)，高度有界）。

工程映射：面试手写 BST 后必被追问「有序数据会怎样」——这正是本题；生产环境几乎不用裸 BST，而用平衡树或哈希；TimSort 对小规模用插入、大规模防退化，与「有序输入最坏化快排」是同一类工程防御。

易错提醒：题干有「最坏」二字时绝不能选 O(log n)；有「平均」才选 log n。退化场景=关键字本身有序或接近有序插入，与快排「已有序最坏」形成高频对照组。

70. 平衡二叉树（AVL树）中查找的时间复杂度为( ) ​

标签：【互联网/国企笔试常考】

A. O(1) B. O(log n) C. O(n) D. O(n log n)

答案：B

【结论】 AVL 树查找的时间复杂度为 O(log n)，选 B。

【逐项辨析】

  • A O(1)：哈希表才能达到。
  • B O(log n)：正确。 AVL 树通过旋转保证树高恒为 O(log n)。
  • C O(n)：这是普通 BST 退化后的复杂度。
  • D O(n log n)：排序的量级。

【知识点】 AVL 树为什么能保证 O(log n)?

AVL 树要求:任一结点的左右子树高度差 ≤ 1
→ 结点数 n 与树高 h 满足 n ≥ (h 层 AVL 树的最少结点数)

h 层 AVL 树的最少结点数递推:
  N(1) = 1, N(2) = 2, N(h) = N(h−1) + N(h−2) + 1
  → h ≈ 1.44 log₂n  →  h = O(log n)
树查找插入删除树高
BST（平均）O(log n)O(log n)O(log n)O(log n)
BST（最坏）O(n)O(n)O(n)n
AVL 树O(log n)O(log n)O(log n)O(log n)

【记忆锚点】 “AVL 树靠旋转兜底，树高永远 log n”。

【易混对比】 AVL 树 vs 红黑树（见第 39 题）：AVL 严格平衡（高度差 ≤ 1），查找略快但插删旋转多；红黑树弱平衡（最长 ≤ 2 × 最短），插删代价小。两者查找都是 O(log n)，差别在维护成本。

【自测】 为什么普通 BST 最坏是 O(n)，而 AVL 树最坏仍是 O(log n)?

答：因为 AVL 树通过旋转主动维持平衡，树高被限制在 O(log n)；普通 BST 没有平衡机制，有序插入会退化成单链，树高为 n。与第 69 题连考。

【知识关联】

  • 同库连考：与第 43 题（BST 平均 O(log n)）、第 69 题（BST 最坏 O(n)）三题一组；与第 45 题（AVL |BF|≤1 定义）——本题的 O(log n) 正由该平衡约束推出；与第 39 题（红黑树同样 O(log n)）。
  • 工程实现：需要最坏可控的内存有序映射可用 AVL/红黑树/跳表；Java TreeMap（红黑树）查找 O(log n)；数据库内存临时有序段同理。AVL 常数更大但更矮，查找密集时略优；写密集选红黑。
  • 408 / 国企真题：408「平衡二叉树查找时间复杂度」O(log n)；常与「普通 BST 最坏 O(n)」同卷对照。国企题库可能问「AVL 树高度数量级」→ O(log n)，更紧约 1.44 log₂n。
  • 面试追问:①「AVL 为何最坏也 log n？」（高度差≤1 ⇒ 树高有上界）；②「与哈希比？」（哈希平均 O(1) 但无序；AVL 保持有序，支持范围查）；③「与 B+ 树比？」（B+ 树为磁盘 I/O 优化，扇出大、树更矮）。

【拓展延伸】

变式问法:①「AVL 查找复杂度？」（O(log n)，本题）；②「插入删除？」（也是 O(log n)，含旋转）；③「h 层 AVL 最少结点递推？」（N(h)=N(h−1)+N(h−2)+1）。

工程映射：有序统计（区间和、前驱后继）、内存索引、需要「查找+有序遍历」的场景；对比哈希「快但无序」、数组「有序但插入 O(n)」。

易错提醒：AVL 的 O(log n) 是最坏保证，比「BST 平均 O(log n)」更强；不要与第 69 题混淆。选项 A O(1) 是哈希平均，不是树。

71. 设哈希表长度为 13，哈希函数 H(key) = key mod 13，采用线性探测再散列法处理冲突。依次插入关键字 18、14、2、31、26，则查找成功时的平均查找长度 ASL 为( ) ​

标签：【国企笔试超高频】

A. 1 B. 1.5 C. 1.2 D. 2

答案：C

【结论】 ASL = 6/5 = 1.2，选 C。

【推导过程】 哈希函数 H(key) = key mod 13，表长 13，线性探测处理冲突

关键字H(key)探测过程存入位置比较次数
185位置 5 为空51
141位置 1 为空11
22位置 2 为空21
3155 已被 18 占用，探测到 6 为空62
260位置 0 为空01
哈希表最终状态:
下标:  0    1    2    3    4    5    6  ...  12
      [26] [14] [2] [ ]  [ ]  [18] [31] ...  [ ]

ASL成功 = (1 + 1 + 1 + 2 + 1) / 5 = 6 / 5 = 1.2。

【逐项辨析】

  • A 1：只有在完全没有冲突时才成立（本题 31 发生了冲突）。
  • C 1.2：正确。 6/5。
  • B 1.5：计算错误。
  • D 2：高估了冲突次数。

【知识点】 哈希表 ASL 的计算方法

ASL成功 = Σ(每个关键字的比较次数) / 关键字个数
ASL失败 = Σ(从每个哈希地址出发探测到空位的次数) / 表长

查找失败 ASL 的分母是表长（而不是关键字个数），这是最易错的地方

分子分母
ASL成功各关键字比较次数之和关键字个数
ASL失败各哈希地址探测次数之和表长

【记忆锚点】 “成功的分母是元素数，失败的分母是表长”。

【易错提醒】 ①必须逐项模拟探测过程，不能只算哈希地址；②开放定址法下删除元素不能直接置空，需设置删除标记（如 "deleted"），否则会切断后续探测链导致查找失败；③线性探测容易产生聚集（连续占用），降低效率。国网、银行科技岗笔试常考此类“给序列算 ASL”的计算题。

【自测】 本题若求查找失败的 ASL，分母应该是多少？

答：13（表长），而不是 5（关键字个数）。与本题对照记忆。

【知识关联】

  • 同库连考：与第 95~100 题（哈希）同一专题；线性探测 ASL 计算是国企高频计算题。
  • 工程实现:Java HashMap 链地址+树化，不是开放定址；Python dict 开放定址。
  • 408 / 国企真题：国网/银行「给序列算 ASL」。
  • 面试追问:①「删除为何不能置空？」（截断探测链）；②「聚集？」（一次聚集/二次聚集）。

【拓展延伸】

完整验算模板:

H(key)=key mod m,线性探测
逐个插入,记录探测次数
成功 ASL = Σ探测次数 / n
失败 ASL = 对每个空位/未命中路径求平均 / 表长约定

变式：平方探测、双散列降低聚集。

工程应用：缓存、布隆过滤器对比、内存哈希表。

72. B+树相对于B树的优势不包括( ) ​

标签：【互联网笔试·数据库高频】

A. 所有数据都在叶子节点，便于范围查询 B. 叶子节点形成链表，便于顺序访问 C. 非叶子节点不存数据，可以容纳更多索引 D. 查找效率比B树低

答案：D

【结论】 B+ 树的查找效率不低于 B 树，故“查找效率比 B 树低”不是其优势，选 D。

【逐项辨析】

  • A 是优势：所有数据都在叶子节点，便于范围查询。
  • B 是优势：叶子节点形成链表，便于顺序访问。
  • C 是优势：非叶子节点不存数据，可容纳更多索引，树更矮、I/O 更少。
  • D 不是优势：B+ 树的查找效率通常不低于 B 树。

【知识点】 B 树 vs B+ 树

B 树B+ 树
数据存储位置所有结点都存数据只有叶子结点存数据
叶子结点不互联通过链表相连
非叶子结点存数据 + 索引只存索引
查找可能在非叶结点命中必须走到叶子
范围查询不方便高效（沿叶子链表扫描）
树高相对高更矮（单结点容纳更多索引）
B+ 树结构示意:
              [30 | 60]              ← 非叶结点只存索引
             /    |    \
      [10|20] [40|50] [70|80]        ← 叶子结点存数据
        ↕        ↕        ↕
      ────────────────────────→      ← 叶子结点用链表相连

【记忆锚点】 “B+ 树：数据全在叶子，叶子连成链，非叶只当路标”。

【易混对比】 为什么 MySQL 的 InnoDB 用 B+ 树而不用 B 树？三个原因：①树更矮 —— 非叶结点只存索引，单结点容纳更多键，减少磁盘 I/O;②范围查询高效 —— 叶子链表支持顺序扫描；③查询性能稳定 —— 每次查找都必须走到叶子，路径长度一致。

【自测】 B+ 树为什么比 B 树更适合数据库索引？

答：①非叶结点不存数据，可容纳更多索引，树更矮 → I/O 更少；②叶子结点链表支持高效范围查询；③每次查找路径长度一致，性能稳定。互联网笔试 / 面试高频。

【知识关联】

  • 同库连考：与第 39 题（红黑树，内存）对照「磁盘 vs 内存」；与第 65/76 题（二分）、第 74 题（查找算法比较）同属查找代价网；与第 103-107 题（文件组织、索引结点）在「索引与数据分离、服务随机查+顺序扫」上同构。
  • 工程实现：MySQL InnoDB 聚簇索引叶子存整行、二级索引叶子存主键；页大小 16KB，非叶只放键+页号 → 扇出大、树高 3~4 层即可索引海量行；SSD 上仍 B+ 树为主；LSM（写优化）是另一条路线。面试必问「为何不用 B 树/红黑树/哈希」。
  • 408 / 国企真题：408 外部查找/B 树 B+ 树考点；互联网数据库笔试「B+ 树相对 B 树优势」高频，答案要点=叶子链表+非叶不存数据+范围查询+查询稳定（本题 D 把「效率低」说成优势，故选 D）。
  • 面试追问:①「为何 MySQL 用 B+ 树不用 B 树？」（范围查询、树更矮、每次查找路径长度一致）；②「不用哈希？」（哈希不支持范围与有序扫描）；③「不用红黑树？」（内存结构，磁盘 I/O 次数随树高上升，B+ 树扇出更优）；④「聚簇索引？」（叶子即数据行）。

【拓展延伸】

变式问法:①「B+ 树优势不包括？」（查找效率比 B 树低——这是错误说法，本题选它）；②「B+ 树叶子？」（有序链表）；③「非叶结点作用？」（纯索引/路标）。

工程映射：几乎全部关系库主键索引；文件系统目录大规模时类似设计；列存的 min/max 稀疏索引、跳表，都是「多层路标+叶子有序」思想变体。

易错提醒：本题问「不包括」；D 说 B+ 树查找效率更低，不符合事实（最坏也不低于 B 树，且工程 I/O 更优），故 D 是答案。A/B/C 都是公认优势。

73. 关于 Java HashMap，下列说法错误的是( ) ​

标签：【互联网 Java 笔试超高频】

A. 默认初始容量为 16，默认负载因子为 0.75 B. HashMap 允许 key 为 null（最多一个），value 可以为 null C. HashMap 是线程安全的，可直接用于并发场景 D. 扩容时容量翻倍，并对已有元素重新计算哈希位置

答案：C【结论】 HashMap 非线程安全，“是线程安全的”说法错误，选 C。

【逐项辨析】

  • A 对：默认初始容量 16，默认负载因子 0.75（阈值 = 16 × 0.75 = 12）。
  • B 对：允许 1 个 null key 与任意多个 null value。
  • C 错：HashMap 非线程安全，并发场景应使用 ConcurrentHashMap 或 Collections.synchronizedMap。
  • D 对：扩容时容量翻倍，并重新计算每个元素的桶位置。注意两版都不重算 hash 值（hash 存在 Node.hash 里），也都用位运算定位——容量恒为 2 的幂，hash & (cap−1) 与「按容量取模」等价，所以「JDK7 取模、JDK8 位运算」的说法不成立。真实差异在定位算法与插入方式：JDK7 的 transfer() 对每个元素用 indexFor(hash, newCap) = hash & (newCap−1) 按新容量重新求下标，并头插进新表（链表因此逆序，并发扩容时两段环相接 → 死循环）；JDK8 用 hash & oldCap 把原桶一次拆成「留在 j」与「移到 j + oldCap」两条子链，并以尾插保持原有顺序，无需按新容量逐位重算。

【知识点】 HashMap 的三类并发问题

1. 数据覆盖:两个线程同时 put 到同一个桶,后写入的覆盖先写入的
2. size 统计不准:并发修改导致 size 与实际元素数不符
3. JDK 1.7 扩容死循环:头插法 + 并发扩容可能形成环形链表,
   导致后续 get 操作陷入死循环(1.8 改为尾插后已修复)
HashMapHashtableConcurrentHashMap
线程安全❌✅ 全表一把锁✅ 锁粒度到桶
null 键 / 值允许 1 个 null key❌ 都不允许❌ 都不允许
并发性能—差好
读操作不加锁加锁不加锁（volatile 保证可见性）

【记忆锚点】 “Hashtable 和 ConcurrentHashMap 都不许 null”——因为并发场景下无法区分“key 不存在”与“value 为 null”。

【易混对比】 注意“扩容为 2 倍”这一细节：JDK 1.8 起利用“容量为 2 的幂”的特性，扩容时元素要么留在原位、要么移到“原位 + 旧容量”，无需重新计算哈希（见第 78 题）。

【自测】 HashMap 的默认初始容量和负载因子分别是多少？阈值是多少？

答：初始容量 16，负载因子 0.75，阈值 = 12（超过 12 个元素即触发扩容）。与第 78、98 题连考。

【知识关联】

  • 同库连考：与第 78 题（2 的幂）、第 98 题（三容器）、第 95~100 题（哈希原理）互联网 Java 网。
  • 工程实现:JDK8 HashMap：数组+链表+红黑树；负载因子 0.75；TREEIFY_THRESHOLD=8（实测链长要到 9 才真正树化，且要求 table.length≥64，否则只扩容）。
  • 408 / 国企真题:Java 岗笔试超高频。
  • 面试追问:①「为何 0.75？」（泊松分布折中冲突与空间）；②「线程不安全表现？」（丢数据、死循环旧版）。

【拓展延伸】

完整验算：默认容量 16，阈值 12。

变式:LinkedHashMap 保序；WeakHashMap 弱键。

工程应用：几乎一切缓存与去重。

74. 以下关于查找算法的比较，正确的是( ) ​

标签：【互联网/国企笔试常考】

A. 二分查找一定比顺序查找快 B. 分块查找不需要额外空间 C. 二叉排序树的查找一定为O(log n) D. 哈希查找的平均时间复杂度为O(1)

答案：D

【结论】 哈希查找平均时间复杂度为 O(1)，该说法正确，选 D。

【逐项辨析】

  • A错：对于小规模数据或“几乎立即找到”的情况，顺序查找可能更快（二分查找的常数开销更大）。
  • D 对：设计良好的哈希表，查找、插入、删除的平均时间复杂度为 O(1)。
  • C错：BST 最坏退化为 O(n)。
  • B错：分块查找需要索引表来记录每块的最大关键字和起始位置，需要额外空间。

【知识点】 五种查找算法的完整对比

查找算法平均 ASL前提条件额外空间适合场景
顺序查找(n+1)/2无无小规模、无序
二分查找≈ log₂n有序 + 随机访问无静态有序表
分块查找≈ √n块间有序索引表动态变化、折中方案
二叉排序树O(log n)需建树树结点动态查找
哈希查找O(1)需设计哈希函数哈希表等值查找、追求速度
分块查找(索引顺序查找)结构:
索引表:  [块1最大值 | 起始地址] [块2最大值 | 起始地址] ...
数据表:  [块1(内部无序,块间有序)] [块2] [块3] ...

查找过程:先在索引表中确定所在块(可用二分),再在块内顺序查找

【记忆锚点】 “要快用哈希，要序用二分，动态用树，折中用分块”。

【易混对比】 注意“二分查找一定比顺序查找快”是错的 —— 当 n 很小（如 n < 10）或目标恰好在表头时，顺序查找的实际速度可能更快（二分查找每次迭代要做除法 / 移位和边界判断，常数开销大）。比较算法快慢既要看渐进复杂度，也要看实际场景。

【自测】 分块查找的平均查找长度大约是多少？

答：约 √n。设分 √n 块、每块 √n 个元素，索引表内查找 √n 次 + 块内查找 √n 次 ≈ 2√n，数量级为 O(√n)。408 高频考点。

【知识关联】

  • 同库连考：与第 65/66/76 题（二分条件）、第 67/68 题（二分 vs 顺序次数）、第 9/12 题（随机访问）、第 95 题（哈希效率因素）、第 43/69 题（BST 平均/最坏）构成查找总表；与第 72 题（B+ 树）延伸到磁盘查找。
  • 工程实现：小 n 顺序扫描可能更快（缓存友好、无建索引代价）；分块查找=内存索引顺序文件思想；动态数据用树/跳表；等值热点键用哈希。「一定更快」类选项在工程题里多半是错的——要分规模、初态、访问模式。
  • 408 / 国企真题：408「下列关于查找算法说法正确的是」综合题；本题正确项是哈希平均 O(1)。错项套路：二分「一定」快、分块「无额外空间」、BST「一定」O(log n)。国网也考分块 ASL≈√n 的计算。
  • 面试追问:①「二分一定比顺序快吗？」（否，小 n/表头命中时顺序可能更快）；②「分块要什么额外结构？」（索引表：块内最大关键字+起始位置）；③「如何选查找结构？」（静态有序→二分；动态→树/跳表；等值→哈希；磁盘→B+ 树）。

【拓展延伸】

变式问法:①「说法正确的是？」（哈希平均 O(1)，本题）；②「分块查找平均 ASL？」（约 √n）；③「BST 查找一定 O(log n)？」（否，最坏 O(n)）。

工程映射：数据库优化器在索引扫描 vs 全表扫描间选择；缓存命中路径；游戏实体列表小规模线性扫仍是合理工程选择。

易错提醒：看到「一定」「不需要额外空间」等绝对化表述要警惕；D 项「平均 O(1)」带了「平均」二字才严谨。

75. 用一维数组顺序存储一棵完全二叉树，若根结点存放在下标 1 的位置，则下标为 i 的结点，其左孩子与右孩子的下标分别为( ) ​

标签：【国企笔试高频】

A. 2i 与 2i+1 B. 2i-1 与 2i C. i/2 与 i/2+1 D. 2i 与 2i+2

答案：A

【结论】 左孩子 2i、右孩子 2i+1，选 A。

【逐项辨析】

  • A 2i 与 2i+1：正确。 根从下标 1 开始编号时的标准公式。
  • B 2i−1 与 2i：偏移了一位。
  • C i/2 与 i/2+1：这是“求双亲”的方向，且表达式不对。
  • D 2i 与 2i+2：右孩子算错了（应为 2i+1）。

【知识点】 完全二叉树顺序存储的两套公式（极易混淆）：

根结点存放位置左孩子右孩子双亲
下标 12i2i+1⌊i/2⌋(i > 1)
下标 02i+12i+2⌊(i−1)/2⌋
根在下标 1:
下标:  1    2    3    4    5    6    7
      [A]  [B]  [C]  [D]  [E]  [F]  [G]
      i=2:左孩子 4(D)、右孩子 5(E)  ✓
      i=3:左孩子 6(F)、右孩子 7(G)  ✓

这正是“堆”能用数组实现的基础 —— 大顶堆 / 小顶堆就是利用这一下标关系做上浮与下沉调整。

【记忆锚点】 “根从 1 开始：左 2i、右 2i+1；根从 0 开始：左 2i+1、右 2i+2”——从 1 开始好记，从 0 开始全部 +1。

【易错提醒】 两套公式不可混用，答题前必须先看清根结点从 0 还是从 1 开始编号。从 1 开始：左 2i、右 2i+1;从 0 开始：左 2i+1、右 2i+2。该题型在国企笔试（国网、银行科技岗）“树与二叉树”模块中属高频计算题。

【易混对比】 注意“顺序存储完全二叉树”与“顺序表”的关系：数组下标对应层序编号，只有完全二叉树才能这样紧凑存储（普通二叉树会有大量空位，需用特殊标记）。

【自测】 若根结点存放在下标 0，则下标为 i 的结点的左孩子、右孩子下标分别是多少？

答：左孩子 2i+1、右孩子 2i+2，双亲为 ⌊(i−1)/2⌋。与本题对照记忆，408 高频。

【知识关联】

  • 同库连考：与第 32、50 题（完全二叉树）、第 84 题（堆）下标公式；根从 0 或 1 两套公式。
  • 工程实现:PriorityQueue 下标从 0：左 2i+1 右 2i+2；教材从 1:2i、2i+1。
  • 408 / 国企真题：国网高频计算。
  • 面试追问:①「父结点？」(⌊(i-1)/2⌋ 或 ⌊i/2⌋ 视起点）;②「堆化从哪开始？」（最后一个非叶）。

【拓展延伸】

完整验算：根 1：子 2i、2i+1；根 0：子 2i+1、2i+2。

变式：三叉堆、d 叉堆下标。

工程应用：堆、线段树、Fenwick 树编号。

76. 折半查找适用于以下哪种存储结构？ ​

标签：【互联网/国企笔试常考】

A. 单链表 B. 双链表 C. 有序顺序表 D. 有序链表

答案：C

【结论】 折半查找要求“有序”且“能随机访问”，只有有序顺序表满足，选 C。

【逐项辨析】

  • A 单链表：不支持 O(1) 随机访问，找中点要 O(n) 遍历，折半的 O(log n) 优势被抵消。
  • B 双链表：双向指针解决的是“找前驱”，依然不能随机访问。
  • C 有序顺序表：正确。 有序（折半前提）+ 下标 O(1) 取中点，两个条件都满足。
  • D 有序链表：“有序”满足，但“随机访问”不满足 —— 这是本题最强干扰项，也是最爱考的陷阱。

【知识点】 折半查找的两个必要条件与实现

下标:  0    1    2    3    4    5    6
值:  [ 7,  11,  18,  25,  33,  40,  52 ]
      ↑              ↑               ↑
     low           mid=3            high

取 mid = ⌊(low+high)/2⌋,比较 a[mid] 与目标值:
  相等 → 命中;目标更小 → high = mid−1;目标更大 → low = mid+1
  • 时间复杂度：O(log₂n)；比较次数上限：⌈log₂(n+1)⌉。
  • 判定树是一棵平衡的二叉排序树。
  • 前提缺一不可：无序 → 无法决定往哪半边找；不能随机访问 → 找不到 O(1) 的中点。

【记忆锚点】 “折半要两样：有序 + 能跳着找（顺序表）”——缺一样都不成立。

【易混对比】

存储结构有序？随机访问？能否折半查找
有序顺序表✅✅✅
有序单链表✅❌❌
无序顺序表❌✅❌
顺序栈 / 顺序队列—✅❌（操作受限，不用于查找）

【自测】 对长度为 n 的有序顺序表做折半查找，最多需要比较多少次？

答：⌈log₂(n+1)⌉ 次（判定树高度）。与第 67、75 题连考。

【知识关联】

  • 同库连考：与第 66 题（二分前提=有序+随机访问）是同一考点的「条件版 vs 结构版」双题；与第 67 题（最多比较次数 ⌊log₂n⌋+1）、第 68 题（顺序查找 ASL=(n+1)/2）、第 75 题（完全二叉树数组下标）、第 12 题（链表取第 i 个 O(n)）构成「折半查找」完整链；与第 104 题（文件顺序存储可随机存取）在「随机访问」概念上同构。
  • 工程实现：ArrayList 可 binarySearch，LinkedList 即使有序也不行；Collections.binarySearch 对 List 要求实现 RandomAccess，否则算法退化——JDK 用接口标记来表达本题条件；跳表、B+ 树、分段索引都是「链式/磁盘结构如何补上随机访问」的答案。
  • 408 / 国企真题：408 与国网「折半查找适用于」原题，标准答案「有序顺序表」；最强干扰项是「有序链表」——有学生误以为「有序就行」，忽略随机访问。真题变体还有「顺序栈能否折半」（操作受限，不用于查找）。
  • 面试追问:①「有序链表能折半吗？」（不能，标准实现要 O(1) 取中点）；②「哈希表能折半吗？」（不能，无序）；③「B+ 树叶子有序，为何还要树？」（磁盘上页是随机访问单元，多层索引避免线性扫叶子）。

【拓展延伸】

变式问法:①「折半适用于？」（有序顺序表，本题）；②「块查找（分块）前提？」（块间有序、块内可无序，块间索引支持定位）；③「斐波那契查找/插值查找对结构的要求？」（仍需有序+随机访问，只是选点策略不同）。

工程映射：数据库主键索引、有序 LSM + 稀疏索引、文件系统目录有序数组、游戏数值表二分，工程上凡是要 O(log n) 点查的结构，都必须同时满足「有序」与「可按位置跳转」。

易错提醒：D 有序链表是本题最强陷阱——只满足一半条件。答题口诀：「有序定方向，顺序表能跳」。另：折半要求的是存储结构支持随机访问，不是「有栈/队列操作」。

77. 实现 LRU（最近最少使用）缓存淘汰算法，最合适的数据结构组合是( ) ​

标签：【互联网面试高频】

A. 数组 + 栈 B. 哈希表 + 双向链表 C. 队列 + 哈希表 D. 两个栈

答案：B【结论】 LRU 最合适的数据结构组合是“哈希表 + 双向链表”，选 B。

【逐项辨析】

  • A 数组 + 栈：数组删除中间元素要 O(n)，栈只能一端操作。
  • B 哈希表 + 双向链表：正确。 哈希表 O(1) 定位，双向链表 O(1) 删除与移动。
  • C 队列 + 哈希表：队列只能在一端删除，无法 O(1) 删除任意结点。
  • D 两个栈：栈无法 O(1) 删除任意结点。

【知识点】 LRU(Least Recently Used)缓存的实现

哈希表 map:key → 链表结点(实现 O(1) 定位)
双向链表:按"最近使用"排序
  头部 = 最近使用
  尾部 = 最久未使用

get(key):
  ① map 中不存在 → 返回 −1
  ② 存在 → 把该结点移到链表头部(标记为最近使用),返回值

put(key, value):
  ① 已存在 → 更新值,移到头部
  ② 不存在 → 新建结点插入头部;
     若超出容量 → 删除链表尾部结点(最久未使用),并同步从 map 删除
双向链表结构(容量 3,最近使用在头部):
头部 ← [C] ⇄ [A] ⇄ [B] → 尾部
       最近              最久未使用(淘汰对象)

为什么必须用双向链表？ 因为删除任意结点时需要 O(1) 访问它的前驱；单链表要 O(n) 找前驱，做不到 O(1)。

【记忆锚点】 “哈希表负责找得到，双向链表负责排得开”——一个管定位，一个管顺序。

【易混对比】 三种缓存淘汰策略

策略淘汰谁英文
LRU最久未使用的Least Recently Used
LFU使用频率最低的Least Frequently Used
FIFO最早进入的First In First Out

LRU 关注“最近一次使用时间”，LFU 关注“累计使用次数” —— 这是两者最本质的区别。

【自测】 为什么 LRU 的双向链表不能用单链表实现？

答：因为删除任意结点需要 O(1) 访问它的前驱，单链表求前驱要 O(n)。LeetCode 146，字节、腾讯、阿里等大厂超高频（常要求手写实现）。

【知识关联】

  • 同库连考：与第 13 题（集合）、第 39 题（红黑树）、第 78 题（HashMap 细节）。
  • 工程实现：哈希 O(1) 定位 + 双向链表 O(1) 调整顺序；accessOrder=false 是插入序（FIFO），true 才按访问序，再重写 removeEldestEntry 才构成 LRU。
  • 408 / 国企真题：互联网面试高频。
  • 面试追问:①「LFU 区别？」（按频率）；②「如何 O(1) 实现？」（哈希+双向链表/堆）。

【拓展延伸】

完整验算:get/put 皆 O(1)。

变式:LRU-K、ARC、W-TinyLFU。

工程应用：页面置换、Redis、CDN 缓存。

78. HashMap 要求数组容量为 2 的幂，主要原因是( ) ​

标签：【互联网 Java 笔试高频】

A. 便于内存对齐，加快遍历 B. 便于序列化和反序列化 C. 减少哈希冲突 D. 可用位运算 (n-1) & hash 代替取模运算，速度更快且分布更均匀

答案：D【结论】 为用位运算 (n−1) & hash 代替取模，速度更快且分布更均匀，选 D。

【逐项辨析】

  • A错：内存对齐不是主要原因。
  • D 对：容量为 2 的幂时，hash & (n−1) 等价于 hash % n，位运算更快；且 (n−1) 的二进制低位全为 1，能保留 hash 的低位信息，分布更均匀。
  • C错：减少冲突是“分布更均匀”带来的附带效果，不是根本原因。
  • B错：与序列化无关。

【知识点】 位运算与取模的等价关系

当 n 是 2 的幂时:hash & (n − 1) ≡ hash % n

示例:n = 16(2⁴),n − 1 = 15 = 0000 1111(二进制)

hash = 26 = 0001 1010
  hash & 15 = 0000 1010 = 10
  hash % 16 = 26 % 16   = 10     ✓ 两者相等

若 n = 15(非 2 的幂),n − 1 = 14 = 0000 1110
  hash & 14 = 0000 1010 = 10
  hash % 15 = 26 % 15   = 11     ✗ 不再相等

为什么“分布更均匀”？ n−1 的二进制低位全为 1（如 15 = 1111），与 hash 做按位与时能完整保留 hash 的低 4 位，均匀映射到 0~15；若 n−1 的某位为 0（如 14 = 1110），该位永远得不到 1，一半桶位会被浪费。

扩容翻倍也便于已有元素迁移： 容量翻倍后仍是 2 的幂，元素要么留在原位、要么移到“原位 + 旧容量”，无需重新计算哈希。

【记忆锚点】 “2 的幂才敢用位运算，(n−1) 低位全 1 分布才均匀”。

【易混对比】 注意 JDK 1.8 的 hash 扰动函数

java
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

把高 16 位异或到低 16 位 —— 因为取模只用到低位，若不扰动，高位信息会被完全丢弃，导致冲突增加。这是“容量为 2 的幂”这一设计的重要配套措施。Java 笔试高频，常考位运算与取模的等价关系。

【自测】 为什么 HashMap 的容量必须是 2 的幂，而不是 3 的幂？

答：因为只有 2 的幂才能用 hash & (n−1) 等价替代 hash % n（位运算比取模快）；而且 n−1 的二进制低位全为 1，能保留 hash 的全部低位信息，使分布更均匀。与第 73、98 题连考。

【知识关联】

  • 同库连考：与第 73 题(HashMap)、第 98 题(ConcurrentHashMap)；与第 96 题（装填因子）。
  • 工程实现:JDK8 (n-1) & hash 代替取模；扩容高低位拆分。
  • 408 / 国企真题:Java 笔试超高频。
  • 面试追问:①「为何不用 3 的幂？」（位运算只有 2 的幂对齐掩码）；②「hash 扰动？」（高 16 异或低 16）。

【拓展延伸】

完整验算:

capacity=16, n-1=15=0b1111
index = hash & 15 → 取低 4 位
扩容到 32:新下标要么原位要么 +16

变式:ConcurrentHashMap 也 2 的幂。

工程应用：一切开放寻址/链地址哈希的性能细节。

持续学习，持续积累。

Copyright © 2026 smallxuetua