Considere las siguientes declaraciones:
- I. El elemento más pequeño en un montón máximo siempre está en un Node hoja.
- II. El segundo elemento más grande en un montón máximo es siempre un elemento secundario del Node raíz.
- tercero Se puede construir un montón máximo a partir de un árbol de búsqueda binario en un tiempo Θ(n).
- IV. Se puede construir un árbol de búsqueda binaria a partir de un montón máximo en un tiempo Θ(n).
¿Cuál de las afirmaciones anteriores es/son VERDADERAS?
(A) II, III y IV
(B) I, II y III
(C) I, III y IV
(D) I, II y IV
Respuesta: (B)
Explicación: La afirmación (I) es correcta. En un montón máximo, el elemento más pequeño siempre está presente en un Node hoja. Entonces, debemos verificar todos los Nodes de hoja para el valor mínimo. La complejidad del peor de los casos será O(n)
12
/ \
/ \
8 7
/ \ / \
/ \ / \
2 3 4 5
La declaración (II) también es correcta; de lo contrario, no satisfará la propiedad max-heap .
La declaración (III) también es correcta, ya que el montón de compilación siempre toma un tiempo Θ(n), (Consulte: Convert BST to Max Heap ).
La declaración (IV) es falsa, porque la construcción del árbol de búsqueda binaria desde max-heap tomará tiempo O (nlogn).
Entonces, la opción (B) es correcta.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA