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