Examen de Programació II UDL 2022 · Segundo Parcial Enero 2022

Pregunta 1 (3 puntos). Operaciones sobre max-heap

Considera el max-heap que se ilustra a continuación:

Efectúa de forma independiente las dos operaciones indicadas a continuación sobre el árbol original:

a.

Remove (extracción de la raíz) sobre el max-heap original.

Describe de forma razonada la situación que se produce en cada instante, detallando los intercambios y las configuraciones intermedias hasta alcanzar la disposición definitiva.

b.

Insert del valor 65 sobre el max-heap original.

Describe de forma razonada la situación que se produce en cada instante, detallando los intercambios y las configuraciones intermedias hasta alcanzar la disposición definitiva.

Pregunta 2 (3,5 puntos). Tablas hash con dispersión abierta y cerrada

Se dispone de dos tablas hash inicialmente vacías (denominadas tabla 1 y tabla 2) de dimensión $M = 10$ (posiciones de 0 a 9) tal y como se muestra en la Figura 2-a.

Se debe simular paso a paso la inserción y eliminación de elementos aplicando la siguiente secuencia de 10 operaciones de parejas (clave, valor):

Insertar (100, 1000)

Insertar (10, 100)

Insertar (31, 310)

Insertar (55, 550)

Eliminar 10

Insertar (5, 50)

Eliminar 31

Insertar (1000, 10000)

Insertar (100, 90)

Insertar (320, 3200)

Función de dispersión común:

$$h(k) = \left(\left(\sum \text{dígitos de } k\right) + k + 1\right) \pmod{10}$$

Ejemplo: $h(43) = ((4 + 3) + 43 + 1) \pmod{10} = 51 \pmod{10} = 1$.

Aplica dicha secuencia y describe de forma razonada la situación que se produce en cada instante, detallando el estado de ambas estructuras según sus particularidades y explicando brevemente cada casuística nueva que acontezca (primera colisión, eliminación lógica vs física, sobreescritura de clave existente, etc.):

a)

Tabla 1 (dispersión abierta): Se representa mediante un array de listas enlazadas que almacenan pares (clave, valor). En caso de colisión, los nuevos elementos se añaden por la cabecera (o final, según corresponda de forma consistente). Si una clave ya existe, se actualiza su valor asociado.

b)

Tabla 2 (dispersión cerrada): Vector de tripletas (clave, valor, marca) (marcas: libre, ocupado, borrado) con resolución cuadrática definida por:

$$h_i(k) = (h(k) + i^2 + 1) \pmod{10} \quad \text{para } i = 0, 1, 2, \dots$$

Pregunta 3 (3,5 puntos). Método leavesMinusInternal para árbol binario

Escribe la implementación de un método en Java llamado leavesMinusInternal que tome por parámetro un árbol de tipo BinaryTree<Integer> y devuelva la diferencia resultante de restar la suma de los nodos interiores a la suma de los nodos hoja:

$$\text{Resultado} = \sum_{\text{hojas}} \text{valor} - \sum_{\text{nodos interiores}} \text{valor}$$

En el caso particular de que el árbol esté vacío, la función debe retornar 0.

En la Figura 3 se ilustran dos ejemplos de ejecución:

Interfaz proporcionada:

public interface BinaryTree<E> extends Collection<E> {

BinaryTree<E> left();

BinaryTree<E> right();

E root();

void removeLeft();

void removeRight();

int height();

Iterator<E> iterator();

BinaryTreeIterator<E> iteratorPre();

BinaryTreeIterator<E> iteratorIn();

BinaryTreeIterator<E> iteratorPost();

BinaryTreeIterator<E> iteratorLevels();

void clear();

boolean contains(Object o);

boolean containsAll(Collection<?> c);

boolean equals(Object o);

int size();

Object[] toArray();

boolean isEmpty();

}

public static int leavesMinusInternal(BinaryTree<Integer> tree)