PUERTA | PUERTA-CS-2006 | Pregunta 76

Un montón máximo de 3 arios es como un montón máximo binario, pero en lugar de 2 hijos, los Nodes tienen 3 hijos. Un montón de 3 arios se puede representar mediante una array de la siguiente manera: la raíz se almacena en la primera ubicación, a[0], los Nodes en el siguiente nivel, de izquierda a derecha, se almacenan de a[1] a a[3 ]. Los Nodes del segundo nivel del árbol de izquierda a derecha se almacenan desde una ubicación [4] en adelante. Un elemento x se puede insertar en un montón tripartito que contiene n elementos colocando x en la ubicación a[n] y empujándolo hacia arriba en el árbol para satisfacer la propiedad del montón.

¿Cuál de las siguientes es una secuencia válida de elementos en una array que representa un montón máximo de 3 arios?
(A) 1, 3, 5, 6, 8, 9
(B) 9, 6, 3, 1, 8, 5
(C) 9, 3, 6, 8, 5, 1
(D) 9, 5, 6 , 8, 3, 1

Respuesta: (D)
Explicación: El siguiente montón máximo de 3 arios se puede construir a partir de la secuencia dada por la opción (D)

                                      9
                                   /  |   \
                                /     |     \
                              5       6      8
                           /  |
                         /    |
                       3      1

Cuestionario de esta pregunta