Final 1/2C/2007 (Algoritmos II)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Esteban Feuerstein y Fernando Schapachnik

Ejercicio 1[editar]

Daban un enunciado y un TAD ya especificado y había que encontrar errores. Había funciones que violaban la congruencia, dado el problema a modelar faltaban otros observadores y generadores, también faltaban restricciones en algunas funciones, había un TAD auxiliar que era dependiente del TAD que se estaba modelando, etc.

Ejercicio 2[editar]

Se puede hacer inducción sobre los reales? Y sobre el TAD racionales? Justifique.

Ejercicio 3[editar]

a) Se desea obtener una implementación eficiente de un diccionario y se lo representa por debajo directamente con nodos y punteros. Cree usted que esto es correcto? Por que si o por que no? Justifique.

b) Que relación hay entre la eficiencia de una estructura y su invariante de representación? Justifique.

Ejercicio 4[editar]

Explicar la complejidad temporal y espacial de los algoritmos MergeSort y HeapSort (óptimos).

Ejercicio 5[editar]

Dar un algoritmo que compare dos árboles dándolos por iguales si son exactamente iguales o bien si tienen intercambiados los subárboles derecho e izquierdo. Calcular la complejidad.

Ejercicio 6[editar]

Explicar las diferencias y similitudes entre las operaciones "partir al bajar" y "partir al subir" de los árboles B.