Final 1C/2011 (Algoritmos II)

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

Ejercicio 1[editar]

Verdadero o Falso, justifique o dé un contraejemplo:

  • a. Si f es O(g) y g es Ω(f), f es Θ(g)?
  • b. Si f es O(n), entonces para cualquier entrada f es Ω(n)
  • c. Si f es Ω(n), entonces para cualquier entrada f es Θ(n)
  • d.

Ejercicio 2[editar]

Sea S una secuencia de inserciones sobre un Arbol binario de Busqueda, donde S = { s1, s2, s3, s4, s5, s6, s7} donde s1 <= s2 <= s3 ... <= s7, describir las permutaciones de S que formen lo siguiente

  • a. Un arbol de altura minima
  • b. Un arbol de altura máxima

Ejercicio 3[editar]

Dada la siguiente especificación sobre una cena con participantes, encuentre los errores y corríjalos (axiomatice o describa como arreglar el error)

Tad Persona

generadores

nueva edad × dni → persona

observadores

. = . persona × persona → bool


Tad Cena

generadores

crear conj(personas) → cena

llega_invitado persona × plato x × cena → cena

observadores

invitados cena → conj(personas)

que_plato_trajo? persona p × cena c → plato { p ∊ invitados(c) }

suma_de_edades cena → nat

Tad Regalo es Nat

Ejercicio 4[editar]

Se quiere implementar un diccionario sobre una novedosa estructura x, se quiere dividir el trabajo entre 3 personas de la siguiente manera:

A) Escribe la interfaz B) Escribe algoritmos de inserción y borrado C) Escribe algoritmos de busqueda

Que le daria como minimo de la siguiente lista a cada uno como para que puedan hacer su trabajo, justificar y sea conciso.

TAD Dicc

TAD X

invariante de representacion de dicc sobre x

invariante de repr de x

funcion de abs de x

funcion de abs de diccionario sobre x

interfaz de x


Ejercicio 5[editar]

Se quiere implementar conjunto y diccionario cuyas operaciones tipicas sean en orden logaritmico (insertar, borrar, buscar o sus equivalentes). De los siguientes diseños, diga cual usaria y porque, si no le convence ninguna proponga una y justifique

  • a. Dicc y Conjunto sobre AVL, AVL sobre punteros a nodos
  • b. AVL sobre ABB, ABB sobre AB, AB sobre nodos, Dicc y Conj sobre AVL
  • c.
  • d.