Download enunciado - Universidad Rey Juan Carlos

Universidad Rey Juan Carlos
Ingenierías Técnicas en Informática de Sistemas y de Gestión
Asignatura: Estructuras de Datos y de la Información
Hoja de Problemas Nº 9: Tablas
____________________________________________________________
1) Implementar en Ada95 un paquete hijo de Arbin para manejo de árboles binarios de búsqueda.
Para implementar la operación Eliminar se recomienda utilizar el procedimiento siguiente:
PROCEDURE EliminarMin(a: IN OUT TipoArbin; m: OUT TipoElemento);
-- PRE: ‘a’ es un árbol binario de búsqueda
-- POST: Elimina de ‘a’ el nodo del elemento más pequeño almacenado
-- en el árbol, conservando el orden de los elementos restantes;
-- la variable ‘m’ almacena el elemento del nodo eliminado.
-- En los dos ejemplos siguientes, los árboles de la derecha son el
-- resultado de aplicar el procedimiento EliminarMin a los árboles de la
izquierda:
4
EliminarMin
5
5
4
6
5
2
3
6
4
EliminarMin
3
6
5
6
2) Para trabajar con árboles binarios de búsqueda se necesita una operación ListaNodosMenores
que reciba como entradas un árbol binario de búsqueda y un elemento y devuelva una lista,
ordenada de menor a mayor, con todos los nodos del árbol que son estrictamente menores que
el elemento dado. Se pide:
a) especificar algebraicamente la operación ListaNodosMenores, supuestas disponibles,
además de todas las operaciones de los TADs ArbolBinarioBusqueda y Lista, las
operaciones de recorrido de árboles binarios (Preorden, Inorden y Postorden)
b) incluir en el paquete de árboles binarios de búsqueda dicha operación
3) Inserción en árboles AVL. Insertar los elementos que se indican, en ese mismo orden, en los
árboles correspondientes dibujando cada uno de los árboles resultantes después de cada
inserción y los factores de equilibrio de los nodos.
a) Insertar en el árbol vacío los elementos 7, 5, 2, 1, 4, 3, 6
b) Insertar en el siguiente árbol AVL los elementos 10, 8, 1, 2, 3 y 4
6
5
7
9
1
c) Insertar en el siguiente árbol AVL los elementos 28, 15, 22 y 17
d) Identificar una posible secuencia de elementos tal que la inserción consecutiva de sus
componentes en el árbol AVL que se muestra a continuación conlleve realizar los
siguientes tipos de rotaciones: II, ID y DI. Se deberá dibujar cada uno de los árboles
resultantes de la inserción de los elementos de la secuencia, junto con los factores de
equilibrio de sus nodos.
5.0
3.0
6.0
4) Extender la especificación algebraica del TAD Tabla visto en clase añadiendo las siguientes
operaciones (para cada una de ellas se deberá indicar el tipo de operación que es, su sintaxis y
su semántica):
•
•
•
•
NumElementos.Operación que devuelve el número de elementos almacenados en una tabla.
BorrarPropiedad..Operación
tal
que,
dada
una
tabla
y
una
función
Propiedad:TipoElemento→Booleano, que recibe como parámetro genérico, borra de la
tabla todos aquellos elementos tales que verifican la propiedad dada.
Acumular. Operación que recibe como parámetro genérico una función
Combinar:TipoElemento×TipoElemento → TipoElemento y tal que, dadas una tabla y un
elemento se comporta como sigue: en caso de que exista un elemento con la misma clave
que el elemento recibido como argumento, reemplazará dicha ocurrencia con el resultado de
aplicar la función Combinar al elemento recibido como argumento y al perteneciente a la
tabla; en caso contrario, añade el nuevo elemento a la tabla. Se supone que la función
Combinar no modifica la clave del elemento.
ModificarTodas. Operación que recibe como parámetro genérico una función Modificar:
TipoElemento→TipoElemento y, dada una tabla, devuelve la misma tabla pero con la
información asociada a cada entrada modificada de acuerdo con la función Modificar. Se
supone que la función Modificar no cambia la clave del elemento.
5) Implementar en Ada 95 un paquete hijo del paquete Tablas_Limited facilitado en clase que
incorpore las operaciones especificadas en el problema anterior. La implementación de las
operaciones deberá realizarse sin hacer uso del paquete de manejo de cursores (tablas_limitediteradores.ads).
2
6) Se desea trabajar con una tabla hash en la que las claves están representadas por números
naturales (la información asociada con cada clave no es relevante para resolver este problema).
Se considera una tabla de tamaño 11 (posiciones de 0 a 10), dotada de la función hash f(n)= n
MOD 11. Partiendo de una tabla vacía, se realizan, de forma consecutiva, las siguientes
operaciones:
(a)
(b)
(c)
(d)
Insertar en la tabla entradas con claves 12, 24, 4, 37, 169, 56 y 17.
Eliminar de la tabla entradas con claves 37 y 56.
Averiguar si las claves 1, 22, 15 y 17 están en la tabla.
Insertar en la tabla entradas con claves 59, 67 y 72.
Se pide mostrar cuál es la situación de la tabla después de realizar cada uno de los grupos de
operaciones (a), (b) y (d), y describir el proceso que se sigue en cada una de las operaciones de
búsqueda del apartado (c). Todo ello deberá realizarse en los siguientes supuestos:



la tabla está implementada mediante hash encadenado.
la tabla está implementada mediante hash abierto utilizando una función de resolución de
colisiones lineal.
la tabla está implementada mediante hash abierto utilizando una función de resolución de
colisiones cuadrática.
7) Utilizar el paquete
operaciones:
•
•
•
tablas_limited-iteradores.ads
para
re-implementar
las
siguientes
El procedimiento de escritura Put(f: IN File_Type; t: IN TipoTabla), incluido en el paquete
tablas_limited-io.
El procedimiento BorrarPropiedad enunciado en esta misma hoja.
El procedimiento ModificarTodas enunciado en esta misma hoja.
3