测一测丨检索算法基础，你掌握了多少？
简介：
本文介绍了多种数据结构的查询、插入及冲突处理机制。对比了无序与有序数据结构的查询效率，分析了二叉检索树、跳表、哈希表、位图、布隆过滤器和倒排索引的特性与适用场景，涵盖时间空间复杂度、平衡性、遍历性能及实际应用设计原则。（238字）
- 对于无序的数组和链表，如果我们想查询一个指定的值 k，平均时间代价是：O(n)
题目解析：对于无序的数组和链表，只能采用遍历的方式查询，时间代价是 O(n)
- 在有序的数组中查询一个指定的值 k，可用的方法有：
a. 顺序遍历
b. 二分查找
c. 都可以
d. 都不行
题目解析：数组是可以顺序遍历的，当然二分查找更高效。
- 在二叉检索树中查询一个指定的值 k，最差的时间代价可能是：O(n)
题目解析：当二叉检索树退化为链表时，查询代价为 O(n)。
- 有序数组和二叉检索树相比，优点是：占用空间更少
题目解析：二叉检索树需要指针连接，占用空间大。尽管实际实现上，由于内存局部性原理，有序数组的查询性能会比二叉检索树好，但两者在查询效率的时间代价分析上都是 O(log n)。 有序数组插入新元素代价是 O(n)，而二叉检索树是 O(log n)
- 以下哪个数据结构的查询空间最有可能不平衡？
a. 二叉检索树
b. AVL 树
c. 红黑树调表
题目解析：AVL 树和红黑树是做了平衡的二叉检索树，而跳表使用随机函数保持平衡。
- 对于跳表的描述，下面不正确的是：
a. 跳表的平均查询时间代价是 O(log n)
b. 跳表具有便捷的遍历能力、实际实现中，跳表在插入新元素时，只需要修改少数的前后节点的指针
c. 跳表不是二叉检索树，因此无法代替二叉检索树的检索功能
- 如果在单链表中间插入一个新元素，需要改动前后 2 个指针。那么在跳表中间，插入一个拥有 2 层指针的新元素，一共需要改动几个指针？
a. 2
b. 3
c. 4
d. 5
题目解析：有 2 层指针，说明要插入单链表 2 次，每次需要改动 2 个指针，那么一共要改动 4 次。
- 以下关于哈希函数的说法，错误的是 ：
a. 哈希函数不会造成冲突
b. 哈希函数可以将一个对象映射到一定范围的正整数内
c. 哈希函数有许多种具体实现方法
d. 理想的哈希函数能将数据均匀分布
- 一个理想哈希表的检索代价是:
a. O(n^2)
b. O(n)
c. O(log n)
d. O(1)
- 对于使用开放寻址法的哈希表来说，当哈希冲突发生时，不能解决冲突的方法是：
a. 线性探查
b. 二分查找
c. 二次探查
d. 双散列】
题目解析：二分查找不是用来解决哈希冲突的
- 对于使用链表法的哈希表来说，如果要保证哈希表的查询效率足够高效，有效的处理方法是：
a. 保证哈希表足够空闲
b. 使用均匀的哈希函数
c. 在链表足够长的时候
d. 转为红黑树
e. 以上都是
题目解析：ABC 这三种处理方法都可以提高哈希表的查询效率
- 哈希表和有序数组相比，有什么缺点？
a. 需要更多的存储空间
b. 遍历性能不高
c. 以上都是
d. 以上都不是
题目解析：哈希表需要保持足够空闲，因此需要更多空间，并且它没有高效遍历能力，只能穷尽整个数组空间来查找每一个元素。
- 关于位图的描述，下面哪一项是错误的？
a. 如果元素的值范围跨度较大，位图会比较耗费空间
b. 许多编程语言中直接支持以 bit 为数组的最小单位
c. 位图的访问时间代价是 O(1) 级别的
d. 当元素不存在时，可以直接将位图对应位置置为 0
题目解析：许多编程语言并不支持，因此需要设计位图的访问操作
- 以下关于布隆过滤器和位图的特点描述，正确的是：
a. 布隆过滤器一定要使用 3 个以上的哈希函数
b. 布隆过滤器不存在错误率
c. 以上都对
d. 以上都不对
题目解析：布隆过滤器存在错误率，并且哈希函数个数可以从 1 个到多个。
- 下列哪个场景不能使用布隆过滤器？
a. 用户注册账号时，需要查询 ID 是否已经被注册过
b. 查询一个用户的 ID 是什么
c. 在爬虫系统中
d. 判断一个网站是否被抓取过、邮箱系统需要快速判断一个陌生的邮件地址，是否在垃圾邮件列表中
题目解析：不是查询状态，而是查询具体值，这种情况不适合使用布隆过滤器。
- 对文档排好序以后，创建倒排索引的时间代价是：
a. O(n^2)
b. O(n)
c. O(log n)
d. O(1)
题目解析：依次遍历和分析文档，然后插入倒排表
- 以下关于倒排索引的说法，错误的是：
a. 在倒排索引中，为了提高检索效率，posting list 中的数据一般是有序
b. 在联合查询两个 key 的时候，我们可以使用归并的方式，对两个 key 对应的 posting list 进行结果合
c. 有了倒排索引就不需要使用正排索引
d. 在一个系统中，如果有需要，我们可以建立多个倒排索引
- 在倒排索引中，key1 的 posting list 长度为 m，key2 的 posting list 长度为 n，其中 m > n。查询条件为：key1 和 key2 要同时存在。假设查询结果长度为 k，那么：
a. k >= m
b. n < k < m
c. k <= n
d. 以上都有可能
题目解析：同时存在是取集合的交集，那么结果的个数一定不会大于最小的集合个数。
- 在倒排索引中，key1 的 posting list 长度为 m，key2 的 posting list 长度为 n，其中 m > n。查询条件为：“key1 和 key2 有一个存在即可”（查询表示为“key1 or key2”）。 假设查询结果长度为 k，那么：
a. k >= m
b. n < k < m
c. k <= n
d. 以上都有可能
题目解析：同时存在是取集合的并集，那么结果的个数一定不会小于最大的集合个数。
- 如果我们想在一个有许多电影信息的影评平台中，根据年份、电影类型、地区等方式检索。正确的设计方案是：
a. 按电影名为 key 建立正排索引，将年份、电影类型、地区分别建立倒排索引
b. 将年份为 key 建立正排索引，将电影名、电影类型、地区分别建立倒排索引
c. 将电影类型为 key 建立正排索引，将电影名、年份、地区分别建立倒排索引
d. 将地区为 key 建立正排索引，将电影名、年份、电影类型分别建立倒排索引
题目解析：因为年份、类型、地区这些都是属性，本身没有复杂内容，因此适合作为倒排。而电影是有复杂内容的主体，适合作为正排。
