# 1. 二分查找的边界模板（左闭右闭/左闭右开）如何统一记忆？死循环与越界的根因分析？ A 左闭右开模板中 r 初始化为 n-1，循环条件为 l<=r B 左闭右闭模板中 r 初始化为 n，访问 a[r] 不会越界 C 左闭右开模板中若进入 l=mid 分支必然死循环，故必须写 l=mid+1 或 r=mid ✓ 正确答案 D 两种模板的 mid 计算方式完全不同
# 2. Top-K 问题的四种解法对比（全排序/堆/快速选择/计数分桶）中不同数据规模与内存约束下如何选型？ A 快速选择最坏复杂度为 O(n log n) B 计数分桶适合任意类型的大对象集合 C 大小为 K 的小顶堆的时间复杂度为 O(n log K)，适合流式数据 ✓ 正确答案 D 全排序的内存占用必然小于堆
# 3. 手写快速排序中随机化基准与三路切分（荷兰国旗）分别解决什么退化场景？ A 三路切分把与 pivot 相等的元素一次性归位，能处理大量重复元素 ✓ 正确答案 B 三路切分主要解决数组已有序时的退化 C 随机化基准能彻底消除所有输入的最坏情况 D 随机化基准与三路切分不能同时使用
# 4. "寻找旋转排序数组中的最小值/目标值"中如何判断有序半边，重复元素如何处理？ A 无重复时查找最小值的时间复杂度为 O(n) B 比较 nums[mid] 与 nums[r] 可判断最小值所在半边 ✓ 正确答案 C 重复元素不会影响该问题的复杂度 D 求目标值时无法利用有序半边的性质
# 5. 两个有序数组的中位数（LeetCode 4）中二分短数组即可做到 O(log min(n,m))，奇偶与边界如何处理？ A 必须二分两个数组才能求解 B 复杂度为 O(log(m+n)) C 因为二分短数组，复杂度为 O(log min(m,n)) ✓ 正确答案 D 奇偶长度需要分别写两套完全不同的算法
# 6. 多数元素（出现次数超过 n/2）的摩尔投票法中候选者与计数器抵消策略能保证最后剩下的必是唯一候选，为何仍需第二遍扫描验证其真实计数，O(n) 时间与 O(1) 空间的依据？ A 候选者必然是多数元素，无需第二遍扫描 B 抵消策略保证候选者计数严格递增 C 该方法需要 O(n) 额外空间 D 当不确定存在多数元素时需要第二遍扫描验证真实计数 ✓ 正确答案
# 7. Top-K 问题中堆、快速选择、BFPRT 三种方案的复杂度与适用场景？ A 快速选择最坏复杂度为 O(n)，无需担心坏输入 B 堆的时间复杂度为 O(n²) 在最坏情况 C BFPRT 保证最坏 O(n) 但常数因子大、实现复杂 ✓ 正确答案 D 三种方案都只能用于流式数据
# 8. 堆排序的稳定性中为什么堆排序不稳定，其最好、平均、最坏复杂度均为 O(n log n)？ A 堆排序是稳定排序 B 堆排序最坏复杂度为 O(n²) C 堆排序最好、平均、最坏复杂度均为 O(n log n) ✓ 正确答案 D 建堆阶段复杂度为 O(n log n)
# 9. CLRS 中位数的最坏 O(n) 算法 BFPRT 的 partition 与 pivot 选择策略？ A 中位数的中位数保证每次划分至少排除固定比例，递推系数和 9/10<1 故 O(n) ✓ 正确答案 B pivot 取第一个元素即可保证最坏 O(n) C BFPRT 期望复杂度为 O(n log n) D 每组取 5 个元素是为了让数组恰好分成 5 组
# 10. 旋转有序数组的二分查找中有重复元素时最坏复杂度为何退化到 O(n)？ A 当 nums[l]==nums[mid]==nums[r] 时无法判断有序半边，需线性收缩，最坏 O(n) ✓ 正确答案 B 重复元素不影响二分查找的复杂度 C 有重复元素时复杂度仍恒为 O(log n) D 只需比较 nums[l] 与 nums[mid] 即可避免退化
# 11. 快速排序的退化条件与优化手段（三取样、双轴、插入排序兜底）？ A 三取样取中能完全消除 O(n²) 的所有可能 B 双轴快排一次划分把数组分成三区，减少常数开销 ✓ 正确答案 C 插入排序兜底用于处理大数组以降低递归开销 D 双轴快排一次划分只分成两区
# 12. 快速排序的最坏情况与优化中三数取中、随机化、双轴快排（Dual-Pivot）各自解决什么问题？ A 随机化能保证最坏复杂度为 O(n log n) B 三数取中与随机化都提升 pivot 质量，降低坏输入概率 ✓ 正确答案 C 双轴快排把最坏复杂度降为 O(n log n) D 双轴快排比单轴快排在最坏情况下更优
# 13. 二分答案的框架中把最优化问题转化为可行性判定（monotonic 条件）？ A 二分答案不需要判定函数单调 B 前提是可行性判定函数单调，复杂度为 O(log区间×check) ✓ 正确答案 C 二分答案只能用于求最小值 D check 函数必须为 O(n) 才能用二分答案
# 14. 二分查找的变体中寻找第一个不小于 target 的位置（lower_bound）与第一个大于 target 的位置（upper_bound）如何统一写法？ A 两者写法差异仅在于比较符号，upper_bound 用 a[mid]<=target 收缩左边界 ✓ 正确答案 B lower_bound 返回第一个大于 target 的位置 C upper_bound 必然返回数组末尾 D 两者复杂度不同
# 15. 归并排序的"逆序对计数"如何用合并过程计算，能否用树状数组替代？ A 归并计数时每合并一个左半元素就累加逆序对 B 当右半元素小于左半当前元素时，累加左半剩余元素个数 ✓ 正确答案 C 逆序对计数不能用树状数组实现 D 归并计数复杂度为 O(n²)
# 16. CLRS 选择算法 RANDOMIZED-SELECT 的期望线性时间与最坏 O(n²) 边界？ A 每次递归需要处理划分的两侧 B 最坏复杂度为 O(n log n) C 期望复杂度为 O(n)，最坏 O(n²) 但概率极低 ✓ 正确答案 D 期望复杂度为 O(n log n)
# 17. 归并排序为什么是稳定排序？外部排序场景为何首选归并思想？ A 归并排序稳定，因为合并时相等元素优先取左半 ✓ 正确答案 B 归并排序不稳定 C 外部排序首选归并是因为归并空间复杂度为 O(1) D 归并排序最坏复杂度为 O(n²)
# 18. 手写堆化（heapify）中自顶向下与自底向上建堆的复杂度差异证明？ A 自底向上 sift-down 建堆的时间复杂度为 O(n) ✓ 正确答案 B 自顶向下逐个插入建堆的时间复杂度为 O(n) C 两种建堆方式复杂度相同 D 自底向上建堆复杂度为 O(n log n)
# 19. 二分查找的边界处理中求第一个/最后一个满足条件的位置时，左右边界收缩的写法差异？ A 找第一个满足条件时，满足则 l=mid+1 B 找最后一个满足条件必死循环 C 两种写法完全相同 D 找第一个满足条件时满足则收缩右边界 r=mid，找最后一个时满足则收缩左边界 l=mid+1 ✓ 正确答案
# 20. CLRS 计数排序、基数排序、桶排序的线性时间下界与稳定性证明？ A 计数排序的稳定性来自从前往后扫描放置 B 桶排序无需做任何桶内排序 C 比较排序的下界是 O(n log n) D 基数排序依赖每轮稳定的低位排序，故必须稳定 ✓ 正确答案
