题11
题目
Q:下列关于小顶堆和败者树的说法中, 正确的是 ( ).
I. 败者树从下往上维护, 每上一层, 只需和失败结点比较 1 次
II. 败者树的每次维护, 必定要从叶结点一直走到根结点, 不可能从中间停止
III. 堆从上往下维护, 每下一层, 若其左右孩子均不为空, 则需比较 2 次
IV. 堆的每次维护, 必定要从根结点一直走到叶结点, 不可能从中间停止
A. I 、 III
B. II、III
C. I 、II 、III
D. I 、III、IV
分析
A:注意题目里面问了两个概念，一个是小根堆，一个是败者树。
解
C
I 正确, 是败者树的性质。
在败者树的维护过程中, 会让胜利者一直调整到根结点, II 正确。
以小根堆为例, 每次调整时, 先比较下一层的两个元素 (1 次), 找出较小值, 然后比较当前元素和下一层的较小元素 (1 次), 以决定是否向下交换位置, III 正确。
堆在维护时, 可能会在中间某层停止 (若此处无须调整), 而不一定要走到叶结点, IV 错误。