Examen Final - 75.41. Algoritmos y Programación II

Cátedra: Calvo
Fecha: ? Oportunidad - Segundo Cuatrimestre 2010
Día: 15/02/2011

1. Defina TDA Cola.
2. Describa una implementación del TDA Cola que no use memoria dinámica y para la cual el coste tempral tanto del alta como de la baja sea O(1),siendo N el tamaño de la entrada del problema. Debe indicar cual es la estructura para almacenar los datos (elegida) y describir detalladamente el algoritmo de alta y el de baja. En cada caso,muestre con un ejemplo la secuencia de operaciones realizadas mostrando el estado de la estructura en cada etapa.

1. Defina TDA Conjunto.
2. Elija una implementeción para el TDA Conjunto que asegure coste O(logN) para el alta y para la búsqueda. Indique cuál es la estructura que eligió, describa el algoritmo de alta y muestre gráficamente cómo se realiza la inserción de estos datos en su estructura, considerando que inicialmente estará vacía. Datos: 2,5,8,13,1,78,65,43,34.
3. Luego muestre gráficamente el algoritmo de borrado,procediendo a eliminar las claves 2,1 y 5.

1. Describa un algoritmo de recorrido a la estructura del ítem anterior (el 2) en el estado final en que ésta se encuentre (es decir después de realizadas las bajas). Indique en que orden serían visitadas las claves.
2. Grafique el árbol de llamadas recursivas (si la estructura elegida tenía punteros, coloque a cada uno un identificador para facilitar la tarea).
3. Responda: En cuanto a la eficiencia, la altura del árbol de llamadas recursivas ¿con qué se asocia? ¿Por qué?. También en relación con la eficiencia: el número de nodos del árbol de llamadas ¿Con qué se asocia? ¿Por qué?.

1. Para el siguiente grafo, se pide un algoritmo que permita determinar el coste mínimo de los caminos que permitan enlazar todos los pares de vértices distintos entre sí. Escriba el algoritmo, aplíquelo al caso y determine su coste temporal.

(Grafo) NdE: jajajaja, te pasás :P

1. ¿Qué es herencia pública?
2. ¿Cuando utiliza herencia pública?
3. ¿Qué es redefinir un método?
4. ¿Hay diferencia entre redefinir y sobrecargar? ¿Cuál?
5. Muestre un caso en el cual sea conveniente redefinir un método. Ejemplifique.