Final 01/03/18 (Algoritmos II)

Final tomado por Soulignac

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)

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

Ejercicio 2

a)Describir el principio de hashing uniforme en una tabla cerrada con direccionamiento abierto

b) Linear probing y Hashing doble cumplen con eso?

Ejercicio 3

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)Recorrer la estructura desde el final hasta el principio

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

Ejercicio 4

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

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