数据结构第七章查找客观测试题

### 数据结构第七章查找部分的客观测试题

#### 单项选择题

1. 下列哪种数据结构适合既需要高效查找又能够处理频繁更新的情况？
A. 哈希表
B. 平衡二叉搜索树
C. 静态数组
D. 双向链表

2. 当使用哈希函数 `h(key) = key % m` 进行散列时，为了减少冲突的发生，m 应该选取什么类型的数最为合适？
A. 质数
B. 合数
C. 任意整数
D. 2 的幂次方

3. 如果在一个开放地址法解决冲突的哈希表中查找失败，则意味着什么呢？
A. 表已满无法再插入新元素
B. 查找的关键字确实不在表内
C. 存在大量同义词导致性能下降
D. 使用了错误的哈希函数

4. 对于给定的一组关键字 {19, 14, 27, 8, 10} 和哈希函数 h(k)=k mod 7，在不发生任何碰撞的情况下，这些关键字会被映射到哪些位置上？
A. 5, 0, 6, 1, 3
B. 5, 0, 6, 1, 2
C. 5, 0, 6, 1, 4
D. 以上都不是

5. 关键字序列{45, 80, 55, 40, 42, 85}利用二次探测法解决冲突建立哈希表，设表长为11，哈希函数H(K)=K%11。请问当插入最后一个数值85之后，它最终存放在哪个槽位里?
A. 4
B. 5
C. 6
D. 7

#### 判断题

1. 在最坏情况下，顺序查找的时间复杂度为O(n)，其中n表示待查集合中的元素数量。（）

2. 若两个不同关键字通过相同的哈希函数计算得到相同的结果，则称这两个关键字互称为“伪同义词”。（）

3. 折半查找适用于有序列表，并且每次比较可以排除一半的数据范围。（）

4. 开放寻址法是一种用于构建静态索引文件的技术。（）

5. B-Tree 是一种自平衡多路搜索树，常被用来实现数据库管理系统中的外存储器上的索引结构。（）

def hash_function(key, table_size):
    return key % table_size


keys = [19, 14, 27, 8, 10]
table_size = 7
positions = [hash_function(key, table_size) for key in keys]

print(positions)