<img src="https://www.geeksforgeeks.org/" alt="技术学习平台" />
- 课程
- 教程
- 面试准备
最后更新：讨论评论
问题 1
以下哪项陈述是正确的？
- 搜索 AVL 树的代价是 θ (log n)，但搜索二叉搜索树的代价是 O(n)
- 搜索 AVL 树的代价是 θ (log n)，但搜索完全二叉树的代价是 θ (n log n)
- 搜索二叉搜索树的代价是 O (log n )，但搜索 AVL 树的代价是 θ(n)
- 搜索 AVL 树的代价是 θ (n log n)，但搜索二叉搜索树的代价是 O(n)
问题 2
将 $n^2$ 个元素插入到一个初始拥有 n 个元素的 AVL 树中，其最坏情况下的时间复杂度是多少？
- Θ(n^4)
- Θ(n^2)
- Θ(n^2 log n)
- Θ(n^3)
问题 3
一个程序接收一个具有 n 个叶节点的平衡二叉搜索树作为输入，并计算每个节点 x 的函数 g(x) 的值。如果计算 g(x) 的代价是 {x 的左子树中的叶节点数, x 的右子树中的叶节点数} 中的较小值，那么该程序的最坏情况时间复杂度是：
- Θ(n)
- Θ(nLogn)
- Θ(n^2)
- Θ(n^2log n)
问题 4
AVL 树可能达到的最大高度是多少？
- 2Logn （假设 log 的底数为 2）
- 1.44log n （假设 log 的底数为 2）
- 取决于具体实现
- Theta(n)
问题 5
考虑以下在自调整二叉搜索树中常用的左旋和右旋函数：
T1, T2 和 T3 是以 y（在左侧）为根的树
或以 x（在右侧）为根的树的子树
y x
/ \ Right Rotation / \
x T3 – - – - – - – > T1 y
/ \ < - - - - - - - / \
T1 T2 Left Rotation T2 T3
以下哪项是左旋和右旋操作的最紧确上界？
- O(1)
- O(Logn)
- O(LogLogn)
- O(n)
问题 6
下面哪一个是 AVL 树？
**A**
100
/ \
50 200
/ \
10 300
**B**
100
/ \
50 200
/ / \
10 150 300
/
5
**C**
100
/ \
50 200
/ \ / \
10 60 150 300
/ \ \
5 180 400
- 仅 A
- A 和 C
- A, B 和 C
- 仅 B
问题 7
与二分查找复杂度相关的递归关系是：
- T(n) = 2T(n/ 2) + k ，其中 k 是常数
- T(n) = T(n / 2) + k ，其中 k 是常数
- T(n) = T(n / 2) + log n
- T(n) = T(n / 2) + n
问题 8
假设数字 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 按此顺序插入到一个初始为空的二叉搜索树中。该二叉搜索树使用自然数的逆序，即假设 9 是最小的，0 是最大的。结果得到的二叉搜索树的中序遍历是：
- 9, 8, 6, 4, 2, 3, 0, 1, 5, 7
- 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
- 0, 2, 4, 3, 1, 6, 5, 9, 8, 7
- 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
问题 9
现在需要一种数据结构来存储一组整数，使得以下每个操作都能在 O(log n) 时间内完成，其中 n 是集合中的元素数量。
I. 删除最小元素
II. 如果元素尚未存在于集合中，则插入该元素
以下哪种数据结构可用于此目的？
- 可以使用堆，但不能使用平衡二叉搜索树
- 可以使用平衡二叉搜索树，但不能使用堆
- 平衡二叉搜索树和堆都可以使用
- 平衡搜索树和堆都不能使用
问题 10
给定两棵平衡二叉搜索树，B1 包含 n 个元素，B2 包含 m 个元素，已知最好的算法将这两棵树合并成另一棵包含 m+n 个元素的平衡二叉树的时间复杂度是多少？
- O(m+n)
- O(mlogn)
- O(nlogm)
- O(m^2 + n^2)
标签：DSA 测验
还有 20 个问题要完成。
参加