40道高级数据结构多选题

1) 开放地址法的装载因子是多少？

1. 1
2. 0
3. 5
4. 5

2) 对于给定的哈希表，使用二次探测法，元素58将被哈希到哪个位置？

0     49
1
2
3
4
5
6
7
8     18
9     89

1. 1
2. 2
3. 7
4. 6

3) 以下哪种数据结构在数据库系统实现中更受青睐？

1. AVL 树
2. B 树
3. B+ 树
4. 伸展树

4) 考虑一个大小为7的哈希表，起始索引为0，哈希函数为 (3x + 4)mod7。假设

哈希表初始为空，当序列 1, 3, 8, 10 使用闭合哈希法

插入表中时，表的内容是什么？注意 '_' 表示表中的空位置。

1. 8, _, _, _, _, _, 10
2. 1, 8, 10, _, _, _, 3
3. 1, _, _, _, _, _,3
4. 1, 10, 8, _, _, _, 3

5) AVL树的叶子节点之间可能的最大高度差是多少？

1. log(n)，其中n是节点数
2. n，其中n是节点数
3. 0 或 1
4. 最多为 1

6) 在红黑树中存储颜色信息时，如何节省内存？

1. 使用节点中某个指针的最低有效位来存储颜色信息
2. 使用另一个数组存储每个节点的颜色
3. 在节点结构中存储颜色信息
4. 使用正数和负数编号

7) 二叉搜索树的最坏情况和平均情况复杂度是多少？

1. O(n), O(n)
2. O(log n), O(log n)
3. O(log n), O(n)
4. O(n), O(log n)

8) 下列哪项是用于在字典中搜索单词的高效数据结构？

1. BST
2. 链表
3. 平衡二叉搜索树
4. Trie（字典树）

9) 在下面给出的哈希表中，使用线性探测法找到49的位置。

0
1
2
3
4
5
6
7
8 18
9 89

1. 7
2. 6
3. 2
4. 0

10) 当我们已经有了红黑树和AVL树，它们可以在对数时间内执行大部分操作，那么为什么还需要伸展树？

1. 没有，它没有特殊用途
2. 在实际应用中，据估计80%的访问只针对20%的数据，因此最常用的数据必须能被轻松获取
3. 红黑树和AVL树不够好
4. 它们只是另一种自平衡二叉搜索树

11) 给定一组n个不同的元素和一个有n个节点的未标记二叉树。有多少种方法可以填充这棵树，使其成为一个二叉搜索树？

1. 0
2. 1
3. n!
4. 1/n+1

12) 以下哪项是正确的？

1. B-树的阶数越大，分裂发生得越不频繁
2. B-树的阶数越大，分裂发生得越频繁
3. B-树的阶数越小，分裂发生得越频繁
4. B-树的阶数越小，分裂发生得越不频繁

13) 如果h是从一个通用哈希函数集合中选择的，并用于将n个键哈希到一个大小为m的表中，

其中 n ≤ m，涉及特定键x的预期碰撞次数小于 _______。

1. 1
2. 1/n
3. 1/m
4. n/m

14) 当一个条目插入到B-树中时，发生了五次节点分裂操作。那么有多少个节点被写入？

1. 14
2. 7
3. 11
4. 5

15) 字典有一组 -------，每个键都有一个唯一关联的值。

1. 键
2. 索引
3. 键和索引
4. 以上都不是

16) 考虑一个大小为7的哈希表，起始索引为0，哈希函数为 (3x + 4)mod7。假设哈希表初始为空，当序列 1, 3, 8, 10 使用闭合哈希法插入表中时，表的内容是什么？注意 '_' 表示表中的空位置。

1. 8 - - - - - 10
2. 1 8 10 - - - 3
3. 1 - - - - - 3
4. 1 10 8 - - - 3

17) 考虑下面的左-左旋转伪代码，其中节点包含值、指向左右子节点的指针和一个高度值，Height()函数返回存储在特定节点的高度值。

 avltree leftrotation(avltreenode z):
 avltreenode w =x-left
 x-left=w-right
 w-right=x
 x-height=max(Height(x-left),Height(x-right))+1 
 w-height=max(missing)+1 
 return w

缺少了什么？

1. Height(w-left), x-height
2. Height(w-right), x-height
3. Height(w-left), x
4. Height(w-left)

18) 哪种哈希技术没有聚集问题？

1. 线性探测
2. 双重哈希
3. 二次哈希
4. Rehash

19) 给定一组n个不同的元素和一个有n个节点的未标记二叉树。有多少种方法可以填充这棵树，使其成为一个二叉搜索树？

1. 0
2. 1
3. n!
4. (1/(n+1)).2nCn

20) 除法方法中使用哪种哈希函数？

1. h(k) = k/m
2. h(k) = k mod m
3. h(k) = m/k
4. h(k) = m mod k

21) 在什么情况下，优先选择红黑树而不是AVL树是最佳的？

1. 当有更多的插入或删除操作时
2. 当需要更多搜索操作时
3. 当树必须是平衡的时
4. 当需要log(nodes)的时间复杂度时

22) 在下图所示的平衡二叉树中，当一个节点作为节点 "g" 的子节点插入时，有多少个节点会变得不平衡？

1. 1
2. 3
3. 4
4. 7

23) 红黑树的特殊属性是什么，根节点应该永远是什么颜色？

1. 一种颜色，红色或黑色，且根节点应始终为黑色
2. 树的高度
3. 一种颜色，绿色或黑色
4. 指向下一个节点的指针

24) 使用伸展树的缺点是什么？

1. 当按非递减顺序访问元素时，伸展树的高度可以是线性的
2. 伸展操作很困难
3. 当一个节点只被读取时，伸展树会执行不必要的伸展操作
4. 没有显著的缺点

25) 下列哪种数据结构可以提供高效的元素搜索？

1. 无序列表
2. 二叉搜索树
3. 树堆 (treap)
4. 2-3 树

26) 考虑以下伪代码

int avl(binarysearchtree root): if(not root) return 0 left....tree....height = avl(left....of....root) if(left....tree....height== -1) return left....tree....height right....tree....height= avl(right....of....root) if(right....tree....height==-1) return

right....tree....height.

以上代码能否检查一个二叉搜索树是否是AVL树？

1. 是
2. 否

27) 给定一个空的AVL树，当给定一组数字时，如何在不执行任何旋转的情况下构建AVL树？

1. 直接用给定的输入构建树
2. 找到给定元素集合的中位数，将其作为根节点并构建树
3. 使用试错法
4. 使用动态规划来构建树

28) 如果有多个元素竞争哈希表中的同一个桶，这称为什么？

1. 扩散
2. 复制
3. 冲突
4. 重复 (Duplication)

29) 以下哪项不是自平衡二叉搜索树？

1. AVL 树
2. 红黑树
3. 伸展树
4. 以上都不是

30) 下面这段代码的输出是什么？

1. 3 和 5
2. 5 和 3
3. 2 和 4
4. 4 和 2

31) 一个有7个节点的AVL树的最大高度是多少？假设单个节点的树高度为0。

1. 2
2. 3
3. 4
4. 5

32) 下面的伪代码会产生什么输出？

1. 子树的右旋转
2. 子树的左旋转
3. zig-zag 操作
4. zig-zig 操作

33) 在除法方法中，m的值可以是什么？

1. 任何质数
2. 任何偶数
3. 2p - 1
4. 2p

34) 下面这段代码的功能是什么？

1. 前序遍历
2. 中序遍历
3. 后序遍历
4. 层序遍历

35) 数字72会被插入到下表的哪个位置？

索引 键

0   22
1   34
2
3
4
5   56
6
7   18
8   41
9
10

1. 3
2. 10
3. 7
4. 6

36) 为了在插入一个元素后恢复AVL属性，我们从插入点开始，并向该树的根移动。这个说法正确吗？

1. TRUE
2. FALSE

37) 为什么我们需要一个高度平衡的二叉树？

1. 为了避免形成斜树
2. 为了节省内存
3. 为了实现更快的内存访问
4. 为了简化存储

38) 红黑树可以在O(logn)时间复杂度内执行哪些操作？

1. 插入、删除、查找前驱、查找后继
2. 仅插入
3. 仅查找前驱、查找后继
4. 用于排序

39) 字典也被称为

1. 哈希 (a hash)
2. 映射 (a map)
3. 哈希映射 (a hashmap)
4. 以上全部

40) 对于从0到2020范围内的整数i，以下哪个哈希函数能将键最均匀地分布在编号为0到9的10个桶中？

1. h(i)=i*i mod 10
2. h(i)=i*i*i mod 10
3. h(i)=(11∗i*i) mod 10
4. h(i)=(12∗i) mod 10