查找算法分析与应用

解题思路：

本题考查三种查找结构的时间复杂度与适用场景。比较的起点是它们各自对查找表提出的额外要求：顺序查找无要求，折半查找要求有序，哈希表要求设计良好的哈希函数。

详细步骤：

1. 顺序查找$O(n)$，适合无序/小数据
2. 折半查找$O(\log_2 n)$，适合有序表
3. 哈希表$O(1)$，适合大数据/高频查找
4. 对比说明：顺序查找几乎可用于任何线性表，但效率随数据量线性下降；折半查找要求表有序，换来对数级效率；哈希表以额外空间换取近乎常数的查找速度，但只支持等值查找。

最终答案：

顺序查找适合无序小表，折半查找适合有序表，哈希表适合大数据高频查找。

解题思路：

本题要求为“频繁查找 + 区间查询”的应用做结构选型。选型的关键是只有能把待查区间内的关键字按序连续取出的结构，才能高效地支持区间查询。

详细步骤：

1. 频繁查找+区间查询，B+树最优
2. B+树叶子节点链式连接，适合范围查找
3. 补充：哈希表虽然能做高频等值查找，但关键字在表中无序，无法支持区间查询；B+ 树把全部关键字集中在叶子结点并用链表顺序连接，区间查询只需从起始关键字沿链表扫描，同时树结构又保证了单点查找的效率。

最终答案：

推荐 B+树，查找和区间查询效率高。

解题思路：

本题考查哈希表与 B 树在大规模数据下的取舍。比较时需要把查找效率、空间开销和能否支持范围查询三个维度放在一起看，并注意大规模数据通常还要考虑外存访问代价。

详细步骤：

1. 哈希表查找快，空间大，适合等值查找
2. B 树查找略慢，适合磁盘/范围查找，空间利用高
3. 补充：哈希表在内存中做等值查找几乎是常数时间，但需要为全部元素分配桶空间且关键字无序，不适合范围查询；B 树一次结点访问即可同时比较多个关键字，查找路径短、空间利用率高，更适合存放在磁盘上的大规模数据与区间查找。

最终答案：

哈希表查找快但不适合范围查找，B 树适合大规模磁盘数据和区间查找。