# 1. R*-Tree 在 R-tree 最优变体的强制重插策略工程实现。 A 重插不限制次数 B 溢出时把远离中心的条目重插整棵树，降低 MBR 重叠，需限制重插次数 ✓ 正确答案 C 强制重插会立即分裂 D 重插与查询性能无关
# 2. R-Tree 的插入与节点分裂中最小包围盒（MBR）扩张、选择最小面积增量子树的插入策略？ A 插入任意子树 B 选择 MBR 面积增量最小的子树插入，溢出时分裂使两组 MBR 重叠最小 ✓ 正确答案 C MBR 扩张无关紧要 D 分裂不优化重叠
# 3. R-Tree 的删除与 CondenseTree 中节点下溢时如何合并或重新分布条目，为什么删除比插入更难保持平衡 A 删除比插入更容易平衡 B 下溢节点条目重新插入并收缩父 MBR，因删除被动触发重插扰动布局，比插入难保持平衡 ✓ 正确答案 C 删除不需要修复 D 下溢直接删除节点
# 4. KD-Tree 的构建与最近邻中交替维度中位数分割、回溯剪枝的距离下界，为什么高维时性能退化 A 维度不影响 KD-Tree 性能 B 高维时剪枝更有效 C 高维时查询更快 D 高维时距离接近均匀使下界剪枝失效，访问节点指数增长，退化为线性扫描 ✓ 正确答案
# 5. R-Tree 在空间数据库 GIST 索引的 MBR 维护。 A GIST 把 MBR 更新/收缩/分裂抽象为回调，用于空间查询的插入与分裂 ✓ 正确答案 B GIST 不维护 MBR C MBR 只用于插入 D GIST 只支持点索引
# 6. R-Tree 的范围查询与最近邻查询中查询时要维护候选分支列表并剪枝，节点重叠如何影响性能？ A 重叠不影响查询 B 重叠越大查询越快 C 无需剪枝 D 用候选分支列表按距离下界排序 + 全局最优剪枝，重叠越大剪枝越差性能越差 ✓ 正确答案
# 7. BSP-Tree 在碰撞检测 AABB 与 Plane 分割的 O(log n) 查询。 A 用查询 AABB 与分割平面位置剪枝子树，平衡树平均 O(log n) ✓ 正确答案 B 每次查询 O(n) 必然 C 平面分割不用于剪枝 D 无法用于碰撞检测
# 8. R*-Tree 的优化中强制重插入（forced reinsert）如何降低节点重叠、提升查询性能？ A 溢出时重插离群条目，使其分布更均匀，降低 MBR 重叠提升查询性能 ✓ 正确答案 B 立即分裂节点 C 重插会增加重叠 D 与查询性能无关
# 9. Geohash 与 R-Tree 中地理坐标索引的编码方式与范围查询差异？ A 两者编码方式相同 B Geohash 用前缀编码近似空间、范围查询需枚举相邻格子有边界误差，R-Tree 用 MBR 精确剪枝 ✓ 正确答案 C R-Tree 有边界误差 D Geohash 比 R-Tree 更精确
# 10. Geohash 与空间填充曲线中 Z-order 如何把二维映射为一维？ A Z-order 只用于三维 B Z-order 没有局部性保证 C Geohash 与 Z-order 无关 D 用位交错把二维坐标交替合并成一维整数，Geohash 是其 base32 编码形式 ✓ 正确答案
# 11. 批量加载中 STR packing 与 Hilbert packing 如何按空间序分批构造 R-Tree，与逐点插入的填充率差异 A packing 不按空间序 B 填充率与插入方式无关 C 逐点插入填充率更高 D 按空间序分块构造，填充率高、树紧凑，优于逐点插入的低填充率 ✓ 正确答案
# 12. 维数灾难中为什么高维空间索引查询退化接近线性扫描，最近邻距离趋于均匀分布 A 维数不影响剪枝 B 高维时距离更易区分 C 高维时索引更高效 D 高维时距离趋于均匀使距离剪枝失效，索引退化为线性扫描 ✓ 正确答案
# 13. BSP-Tree 在 Hidden Surface Removal 的 Painter's Algorithm 配合。 A BSP 沿树从后到前遍历得到视点无关的深度排序，配合画家算法绘制 ✓ 正确答案 B 画家算法需要视点相关排序 C BSP 无法提供深度排序 D 隐藏面消除不用 BSP
# 14. BSP-Tree 在 KD-Tree vs Octree 在 3D 渲染的取舍。 A BSP 适合静态深度排序，Octree 适合动态场景，KD-Tree 适合光线追踪 ✓ 正确答案 B 三者都适合动态场景 C KD-Tree 提供深度排序 D Octree 贴合几何
# 15. 四叉树/八叉树与 R-Tree 的对比中点集索引 vs 区域对象索引的适用边界？ A R-Tree 适合点集且不适用区域 B 四叉树适合均匀点集，R-Tree 用 MBR 适合区域对象与精确范围查询 ✓ 正确答案 C 四叉树适合区域对象 D 两者完全相同
# 16. 空间填充曲线（Z-order 与 Hilbert）如何把二维查询映射为一维范围，为什么 Hilbert 曲线的局部性优于 Z-order？ A Hilbert 有更多跳跃 B Z-order 局部性更好 C Hilbert 保证相邻格子一维距离有界，矩形映射到更少区间，局部性优于 Z-order ✓ 正确答案 D 两者局部性相同
# 17. R*-Tree 在 Hilbert 曲线填充的 Cache 性能优化。 A 按 Hilbert 序填充使相邻数据连续存储，提升缓存局部性与查询性能 ✓ 正确答案 B 填充顺序与缓存无关 C Hilbert 填充降低填充率 D 随机插入更友好
# 18. BSP-Tree 在光线追踪/碰撞检测中的应用中平面分割与视锥剔除的原理？ A 视锥剔除无需 BSP B 平面分割不用于剪枝 C 用分割平面与视锥/光线的位置关系剪枝子树，实现视锥剔除与减少相交测试 ✓ 正确答案 D 查询访问所有子树
# 19. 空间索引的工程落地中 PostGIS/Elasticsearch 中 R-Tree、Geohash、S2 的取舍？ A PostGIS 用 R-Tree 精确几何，Elasticsearch 用 Geohash/S2，S2 用 Hilbert 分层 cell 利于分布式 ✓ 正确答案 B 三者都能精确查询 C Geohash 比 R-Tree 更精确 D S2 不用于分布式
# 21. S2 的 cell 体系中 Hilbert 曲线分层 cell 如何做范围覆盖查询，与 Geohash 的精度边界差异 A Geohash 精确覆盖任意区域 B S2 用分层 cell + Hilbert 编码精确覆盖区域、层级可调，Geohash 固定格子边界误差大 ✓ 正确答案 C S2 cell 不分层 D 两者边界能力相同
