Práctico 5 – Tipos Abstractos de Datos
Ejercicio 1
Implemente en C++ todas las operaciones primitivas del TAD Queue utilizando cada una de las
siguientes representaciones. Luego haga un programa de prueba para cada representación:
a) Una estructura de arreglo con tope (asuma que el Queue es acotado).
b) Una estructura de LDEPPF.
Ejercicio 2
Implemente en C++ las operaciones primitivas Make, Member, Find e Insert del TAD Diccionario
utilizando cada una de las siguientes representaciones. Luego haga un programa de prueba para
cada representación:
a) Una estructura de hash (considere definida la función de dispersión h).
b) Una estructura de árbol binario de búsqueda.
El tipo de los elementos a almacenar en el diccionario es T y el tipo de las claves es K. Puede
suponer definida la función DarClave: T → K que dado un elemento, devuelve su clave.
Ejercicio 3
Se desea implementar la siguiente operación sobre un Deque de números naturales. Se quiere
modificar cada elemento del deque según el siguiente criterio:
Si el deque cuenta con N elementos, entonces los elementos en las posiciones k y (N-k+1) serán
sustituidos por la suma de ambos. Por ejemplo, si el deque cuenta con los valores [2, 4, 8, 6, 7]
entonces deberá quedar con los valores [9, 10, 16, 10, 9] luego de realizada la operación.
Implemente la operación solicitada utilizando solamente las primitivas del TAD Deque (puede
suponer implementadas dichas primitivas).
Ejercicio 4
Los algoritmos de DFS (recorrida en profundidad) y BFS (recorrida a lo ancho) sobre un grafo
pueden ser implementados en forma puramente iterativa. DFS se basa en la idea de hacer
llamadas recursivas para continuar la recorrida por los nodos vecinos. A efectos de obtener una
implementación puramente iterativa, las llamadas recursivas pueden ser sustituidas por el uso de
un Stack auxiliar donde ir almacenando los nodos que faltan visitar. BFS se basa en la idea de
continuar la recorrida por los vecinos en el mismo orden en que van siendo visitados. Es posible
respetar dicho orden usando un Queue auxiliar donde ir almacenando los nodos que faltan visitar.
a) Proponga una implementación puramente iterativa para DFS utilizando un Stack auxiliar.
b) Proponga una implementación puramente iterativa para BFS utilizando un Queue auxiliar.
Nota: Implemente ambos algoritmos utilizando las dos representaciones para grafos vistas en el
curso. Las recorridas deben ir listando los nodos por pantalla. Puede suponer implementadas
todas las primitivas de Stack y Queue que necesite.
Práctico 5 – Tipos Abstractos de Datos
Ejercicio 5
Se quiere modelar un consultorio médico que atiende pacientes diariamente. De cada paciente
interesa registrar su cédula, su teléfono y un historial de las consultas que ha realizado en el
consultorio. Interesa mantener ordenado el historial de cada paciente en forma cronológica. De
cada consulta se registra un código identificador de la afección correspondiente junto con la fecha
de realización de la consulta. Se realizó el siguiente análisis de Tipos Abstractos de Datos (TAD)
para esta realidad:
Pacientes = Diccionario (Paciente)
Paciente = Producto Cartesiano (Cédula, Teléfono, Historial)
Cédula = Entero, Teléfono = Entero
Historial = Secuencia (Consulta)
Consulta = Producto Cartesiano (Código, Fecha)
Código = Entero
Fecha = Producto Cartesiano (Día, Mes, Año)
Día = Entero, Mes = Entero, Año = Entero
Las operaciones que se realizan más frecuentemente en el consultorio son las siguientes:
1. Registrar un nuevo paciente en el sistema.
2. Dada la cédula de un paciente, registrar una nueva consulta para dicho paciente.
3. Dada la cédula de un paciente, listar por pantalla su historial de consultas.
4. Listar todos los pacientes ordenados por cédula de menor a mayor.
Se pide:
a) Elija las estructuras de datos que considere más apropiadas para representar los TAD
anteriores, considerando las operaciones propuestas. Se sabe además que la cuarta
operación es la que se realiza con mayor frecuencia. Justifique.
b) Defina en C++ los tipos de datos correspondientes a las estructuras elegidas en la parte (a) y
luego implemente las cuatro operaciones propuestas. Suponga predefinidas todas las
primitivas de los TAD involucrados e implemente cualquier otra operación auxiliar que utilice.
Ejercicio 6
Se quiere modelar una capilla donde las parejas contraen matrimonio. De cada pareja se registran
los datos del novio y de la novia. En el caso del novio, lo que se registra es su cédula, nombre,
edad y color del esmoquin. En el caso de la novia, lo que se registra es su cédula, nombre, edad y
estilo del vestido. Las parejas se inscriben en la capilla con antelación a contraer matrimonio y se
les asigna una fecha. A veces ocurre que se celebra más de una boda en una misma fecha.
Cuando la pareja se inscribe, debe proporcionar los datos de los invitados a la boda, dichos datos
son la cédula, el nombre y la edad del invitado. Las operaciones que se realizan más
frecuentemente en la capilla son las siguientes:
1. Inscribir una nueva pareja en la capilla.
2. Dada una fecha, listar los datos de todas las parejas que se casaron luego de esa fecha.
3. Dadas una fecha y la cédula de una persona, saber si dicha persona está invitada a
alguna de las bodas contraídas en dicha fecha.
Se pide:
a) Realice el análisis de los TAD necesarios para modelar esta realidad. Explique su elección.
b) Elija las estructuras de datos que considere más apropiadas para representar los TAD
anteriores, considerando las operaciones propuestas. Justifique.
