Final 2C/2006 (Algoritmos II)
Esteban Feuerstein y Fernando Schapachnik
Ejercicio 1
Considere el TAD Carta de un Restaurante. La carta esta constituida por menús, consistente de pares Plato-Vino. cada uno con un precio determinado. Los platos y los vinos son a su vez otros TADS y el precio es un NAT. Los platos son identificados con una cadena de caracteres que se consulta con la operación ident y un vino es una tupla ident, región, calidad. las 2 primeras son cadenas de caracteres y la ultima es nat.
Las operaciones del TAD carta son:
Crear: genera una nueva instancia.
Añadir: Agrega un nuevo menú consistente de un plato, un vino y precio. Si el par plato-vino ya existía, se actualiza el precio, sino se da de alta.
Retirar: Se elimina de la carta un nuevo vino dado. todos los menús que contenían ese vino, son reemplazados por otro que contenga el mismo plato, un vino de la misma región, y calidad inmediata inferior.
Mas_Selecto: devuelve el vino mas caro que ofrece la carta.
a) Especificar completamente el TAD. identificar observadores y generadores. Justificar la elección. incorporar otras operaciones si fuera necesario. Definir igualdad observacional. Axiomatizar observadores.
b) Proponer una estructura de representación del TAD de forma que Retirar y Mas_selecto tengan complejidad optima. Justificar.
�� ������ ������ ����� �� ���������! �������� ��������� ����� �����,
Ejercicio 3
Dar una secuencia de inserciones de claves enteras en un AVL inicialmente vació, que produce un árbol de Fibonacci de altura 5. Mostrar como queda después de cada inserción. Todos los árboles que se van obteniendo son Fibonacci?
Ejercicio 4
Escribir el pseudocódigo de un algoritmo que recorre un árbol de enteros positivos usando backtracking a la búsqueda de una hoja tal que la suma de los elementos de los nodos en el camino de la raíz hacia la hoja, sea menor a un valor X. Ejemplificar sobre un árbol binario de 5 niveles usando un valor X que permita ilustrar las distintas circunstancias del algoritmo.
