GESP 8级客观题｜倍增思想｜课后作业

考试频率：低频。本卷共 3 题。

1. 使用倍增表求树上第 $k$ 个祖先时，查询一次通常需要（ ）时间。

   {{ select(1) }}

• $O(1)$
• $O(\log k)$
• $O(k)$
• $O(k^2)$

2. 若 up[v][j] 表示结点 v 向上跳 $2^j$ 步到达的结点，则正确转移是（ ）。

   {{ select(2) }}

• up[v][j]=up[v][j-1]+1
• up[v][j]=up[up[v][j-1]][j-1]
• up[v][j]=v*2
• up[v][j]=up[v][0]

3. 倍增表的最大列数通常与什么量有关（ ）。

   {{ select(3) }}

• 结点名称长度
• 最大跳转步数的对数
• 边权之和
• 答案大小的平方