Edición de «Final 01/03/18 (Algoritmos II)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
| Revisión actual | Tu texto | ||
| Línea 1: | Línea 1: | ||
Final tomado por Soulignac | Final tomado por Soulignac | ||
== Ejercicio 1 == | == Ejercicio 1 == | ||
a)Explicar (en castellano) como seria la interfaz del diseño de un modulo de secuencia sobre lista enlazada que permita hacer quicksort de manera eficiente.(y dejar claro lo del aliasing) | a)Explicar (en castellano) como seria la interfaz del diseño de un modulo de secuencia sobre lista enlazada que permita hacer quicksort de manera eficiente. | ||
(y dejar claro lo del aliasing) | |||
b)implementar el algoritmo de quicksort para la secuencia diseñada | b)implementar el algoritmo de quicksort para la secuencia diseñada | ||
c)explicar (en castellano) ccomo se implementarian las funciones usadas en el punto anterior | c)explicar (en castellano) ccomo se implementarian las funciones usadas en el punto anterior | ||
== Ejercicio 2 == | == Ejercicio 2 == | ||
a)Describir el principio de hashing uniforme en una tabla cerrada con direccionamiento abierto | a)Describir el principio de hashing uniforme en una tabla cerrada con direccionamiento abierto | ||
b) Linear probing y Hashing doble cumplen con eso? | b) Linear probing y Hashing doble cumplen con eso? | ||
== Ejercicio 3 == | == Ejercicio 3 == | ||
Explicar la definicion de complejidad amortizada y para cada caso calcular su complejidad(independientemente de la estructura | Explicar la definicion de complejidad amortizada y para cada caso calcular su complejidad(independientemente de la estructura | ||
a)recorrer la estructura de principio a fin | |||
b)reccorrer la estructura desde el final hasta el principio | |||
a) | |||
b) | |||
c)avanzar y retroceder n veces (queda apuntando al mismo valor en el q estaba) | c)avanzar y retroceder n veces (queda apuntando al mismo valor en el q estaba) | ||
Considerar un ABB balancecado(avl, rb-tree, etc) calcular la complejidad nuevamente para cada caso y analizarlo | Considerar un ABB balancecado(avl, rb-tree, etc) calcular la complejidad nuevamente para cada caso y analizarlo | ||
== Ejercicio | == Ejercicio 3 == | ||
Explique que estructura usaria manteniendo ordenado un conjunto de numeros y que se pueda agregar y borrar de forma eficiente para cada caso: | Explique que estructura usaria manteniendo ordenado un conjunto de numeros y que se pueda agregar y borrar de forma eficiente para cada caso: | ||
a)Que no tenga que pasar que te quedes momentaneamente esperando al programa | a)Que no tenga que pasar que te quedes momentaneamente esperando al programa | ||
b)Que la estructura(no los valores) ocupen el menor espacio posible | b)Que la estructura(no los valores) ocupen el menor espacio posible | ||
c)se tiene un sistema de noticias y se espera que la noticia mas vista sea la que menos tarde en cargar | c)se tiene un sistema de noticias y se espera que la noticia mas vista sea la que menos tarde en cargar | ||
