算法选择题：数组与哈希（5 题）
006 需要在长度为 n 的数组中频繁于第 k 个位置插入元素，哪种表述准确？
难度： 基础
- A. 动态数组扩容一次后，后续所有插入都严格 O(1)
- B. 插入成本与插入位置无关，恒为 O(1)
- C. 数组支持 O(1) 随机访问，所以插入也是 O(1)
- D. 数组中间插入需要把后续元素整体后移，单次最坏 O(n)；只在末尾追加且使用动态数组时平均 O(1)
查看答案与解析
正确答案D
正确原因： 数组中间插入通常需要搬移后续元素；末尾追加到动态数组通常是摊还 O(1)，关键边界是插入位置与扩容成本。
错误选项辨析： A 项：扩容本身是 O(n)，且不扩容时末尾追加才是摊还 O(1)；B 项：插入越靠前需要搬移的元素越多，成本与位置强相关；C 项：随机访问是按下标读取，与插入需要搬移后续元素是两回事。
007 关于哈希表查询复杂度，哪种表述准确？
难度： 进阶
- A. 哈希表无需处理扩容，查询复杂度与负载因子无关
- B. 均匀散列下查询平均为 O(1)；最坏情况（大量碰撞）和扩容成本不能省略，冲突严重时可能退化
- C. 哈希查询的复杂度恒为 O(log n)
- D. 哈希查询在任何输入下都严格 O(1)
查看答案与解析
正确答案B
正确原因： 合理哈希分布下查询平均为 O(1)；最坏情况、碰撞和扩容成本不能省略。
错误选项辨析： A 项：负载因子决定冲突概率，扩容也是成本的一部分；C 项：与二叉搜索树混淆，均匀散列下哈希查询是平均 O(1)；D 项：把平均情况当成最坏保证，忽略了碰撞导致的退化。
008 把自定义类型对象作为 Dictionary 的键放入后，以下哪种做法是正确的？
难度： 进阶
- A. 哈希表会自动追踪键字段的变化并重新定位
- B. 键被修改后，字典会自动抛出异常提醒
- C. 键放入哈希表后不应修改参与 GetHashCode 与 Equals 的字段；修改不参与哈希与相等的字段不会改变桶定位
- D. 键的任何字段都绝对不能修改，否则必然出 Bug
查看答案与解析
正确答案C
正确原因： 键进入哈希表后不应修改参与哈希与相等比较的字段；修改无关字段不会改变桶定位。
错误选项辨析： A 项：哈希表不会观察键对象的内部状态，桶位置只在插入时确定；B 项：.NET 字典不会校验键的哈希一致性，不存在这样的异常；D 项：只有参与哈希与相等比较的字段才影响桶定位，无关字段可安全修改。
009 需要反复查询数组任意闭区间 [left,right] 的元素和，哪种方案最合理？
难度： 进阶
- A. 预处理长度 n+1 的前缀和数组，闭区间和 = prefix[right+1] - prefix[left]，单次查询 O(1)，预处理 O(n)
- B. 每次查询都必须重新遍历区间，无法预处理
- C. 前缀和能让预处理本身也变成 O(1)
- D. 前缀数组长度与元数组相同即可，无需额外一位
查看答案与解析
正确答案A
正确原因： 用长度 n+1 的前缀数组可统一表示闭区间和；区间 [left,right] 对应 prefix[right+1]-prefix[left]。
错误选项辨析： B 项：前缀和正是为区间和查询做的预处理，单次查询 O(1)；C 项：前缀和只能加速查询，构建前缀数组仍需一次 O(n) 扫描；D 项：长度 n+1 才能统一表达空前缀与右边界，否则边界需要特判。
010 需要统计整数数组中每个值出现的次数，并快速判断某个值是否出现过，应如何选择结构？
难度： 综合
- A. Dictionary 与 HashSet 都保持插入顺序，可直接作为结果返回
- B. 只要用了哈希结构，去重与统计可以同时完成，无需区分
- C. HashSet 可以直接保存每个值的出现次数
- D. 需要次数时用 Dictionary<值,计数>；只判断存在性用 HashSet；结果顺序与重复语义必须由题目契约决定
查看答案与解析
正确答案D
正确原因： 只判断存在性用集合，需要保留次数时用值到计数的映射；结果顺序与重复语义必须由题目契约决定。
错误选项辨析： A 项：.NET 哈希结构不保证顺序，顺序语义必须由题目契约决定；B 项：去重与统计是不同能力，选型取决于是否真的需要次数；C 项：集合只保存元素本身，不保存次数，统计次数必须用值到计数的映射。