CSP-J/S 二分法与二分答案综合测试

本试卷共 25 道单项选择题，每题 4 分，满分 100 分。

一、基础二分与边界查找

1. 二分法能够正确使用的本质前提是（ ）。

{{ select(1) }}

• 数据必须全部不同
• 能根据中点判断并排除一半无答案区域
• 数据必须存放在链表中
• 循环次数必须等于 n

2. 在闭区间 [l,r] 的普通二分模板中，区间非空条件是（ ）。

{{ select(2) }}

• l<r
• l<=r
• l==r
• l>r

3. 为减少 l+r 溢出的风险，中点推荐写成（ ）。

{{ select(3) }}

• (l+r+r)/2
• l+(r-l)/2
• l+r/2
• (r-l)/2

4. 普通升序二分中，若 a[mid]<target，应更新（ ）。

{{ select(4) }}

• l=mid
• r=mid
• l=mid+1
• r=mid-1

5. lower_bound(first,last,x) 返回（ ）。

{{ select(5) }}

• 最后一个 <x 的位置
• 第一个 >=x 的位置
• 第一个 >x 的位置
• 任意一个等于 x 的位置

6. upper_bound(first,last,x) 返回（ ）。

{{ select(6) }}

• 第一个 >=x 的位置
• 最后一个等于 x 的位置
• 第一个 >x 的位置
• 第一个 <x 的位置

7. 有序数组中 x 的出现次数可用（ ）。

{{ select(7) }}

• upper_bound(x)-lower_bound(x)
• lower_bound(x)-upper_bound(x)
• binary_search(x)+1
• n-lower_bound(x)

8. lower_bound 的返回位置（ ）。

{{ select(8) }}

• 一定小于 n
• 可能等于 n，此时不能访问 a[n]
• 一定指向等于目标值的元素
• 只能用于无重复数组

9. binary_search 的返回类型和主要含义是（ ）。

{{ select(9) }}

• 整数，返回第一次出现下标
• 指针，返回最后一次出现位置
• 布尔值，只判断是否存在
• 浮点数，返回出现次数

10. 在已按降序排列的数组中调用 STL 边界函数，比较器通常使用（ ）。

{{ select(10) }}

• less<int>()
• greater<int>()
• equal_to<int>()
• 不需要比较器

二、二分答案

11. 求最小可行值时，若 check(mid) 为真，通常更新（ ）。

{{ select(11) }}

• l=mid+1
• r=mid
• l=mid
• r=mid-1

12. 求最大可行值时，若 check(mid) 为真，通常更新（ ）。

{{ select(12) }}

• l=mid
• r=mid
• l=mid+1
• r=mid-1

13. 闭区间收敛模板求最大可行值时，为避免死循环应取（ ）。

{{ select(13) }}

• 下中位数
• 随机中点
• 上中位数
• 左端点

14. 求 floor(sqrt(n)) 时，为避免乘法溢出，判断 mid²<=n 可改写为（ ）。

{{ select(14) }}

• mid+mid<=n
• mid==0 || mid<=n/mid
• mid<n-mid
• mid%n==0

15. 将物品按原顺序装入不超过 m 个箱子，最小容量的下界应为（ ）。

{{ select(15) }}

• 最重物品重量
• 最轻物品重量
• 物品数量
• 0

16. 上题中容量的一个安全上界是（ ）。

{{ select(16) }}

• 平均重量
• 最大重量减最小重量
• 箱子数量
• 所有物品重量之和

17. 在最小装载容量问题中，容量越大，check(cap) 通常（ ）。

{{ select(17) }}

• 越难满足
• 越容易满足
• 没有任何规律
• 一定为假

18. 最大化相邻已选点的最小距离时，距离要求 d 越小，通常（ ）。

{{ select(18) }}

• 越容易选出足够多的点
• 越难选出足够多的点
• 答案一定更小
• 必须改用 DFS

19. 将长度为 L 的绳子切成整数长度 x，可切出的段数是（ ）。

{{ select(19) }}

• x/L
• L/x
• L%x
• L+x

20. 实数二分中较稳定的停止方式是（ ）。

{{ select(20) }}

• 等待 l==r
• 只循环 1 次
• 固定循环约 80～100 次
• 只判断整数部分

三、复杂度与易错点

21. 若二分答案的 check 为 O(n)，答案值域大小为 V，总复杂度通常是（ ）。

{{ select(21) }}

• O(n+V)
• O(n log V)
• O(V log n)
• O(n²)

22. 仅仅因为 check(x) 很快，就一定能二分答案，这一说法错误的原因是（ ）。

{{ select(22) }}

• 二分只能处理字符串
• 还必须保证答案范围很小
• check(x) 还必须具有单调性
• 必须使用递归

23. 把 [l,r] 和 [l,r) 两套模板混合使用，最容易导致（ ）。

{{ select(23) }}

• 自动排序
• 越界、漏解或死循环
• 时间复杂度变成 O(1)
• 编译器自动修复

24. lower_bound 找到的位置（ ）。

{{ select(24) }}

• 不保证值等于目标，需要再次检查
• 一定是最后一个目标值
• 一定是数组中点
• 一定小于 0

25. 有序数组中最后一个 <=x 的位置可表示为（ ）。

{{ select(25) }}

• lower_bound(x)
• lower_bound(x)+1
• upper_bound(x)
• upper_bound(x)-1