Edición de «Final 03/05/17 (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: | ||
Tomado por Esteban Feuerstein, corregido por Fernando Schapachnik. | |||
[[Archivo:Final-algo2-03-05-2017-parte1.jpeg|500px]] | |||
Para aprobar: como mínimo 3 ejercicios BIEN | Para aprobar: como mínimo 3 ejercicios BIEN | ||
Línea 41: | Línea 43: | ||
top: pila -> indicador | top: pila -> indicador | ||
hay_elem?: indicador -> bool | hay_elem?: indicador -> bool | ||
elem: pila x indicador i -> elem { hay_elem?(i) } | elem: pila x indicador i -> elem { hay_elem?(i) } | ||
== Ejercicio 2 == | == Ejercicio 2 == | ||
Supongamos que extendemos el TAD Diccionario agregándole una operación RestricciónDeRango(x,y), con x<=y, que elimina del diccionario todos los valores que son | Supongamos que extendemos el TAD Diccionario agregándole una operación RestricciónDeRango(x,y), con x<=y, que elimina del diccionario todos los valores que son mayores que x o menores que y. Por ejemplo, si las claves son reales, luego de una operación RestricciónDeRango(x,y) el diccionario contendría solamente las claves en el intervalo cerrado [x,y]. Proponga una estructura de datos para implementar eficientemente tanto las operaciones tradicionales de diccionario como la nueva operación, considerando los siguientes casos: | ||
a) Se | a) Se ruede asumir que x e y están en el diccionario. | ||
b) No se puede asumir que x e y están en el diccionario. | b) No se puede asumir que x e y están en el diccionario. | ||
[[Archivo:Final-algo2-03-05-2017-parte2.jpeg|500px]] | |||
== Ejercicio 3 == | == Ejercicio 3 == | ||
Línea 75: | Línea 66: | ||
== Ejercicio 5 == | == Ejercicio 5 == | ||
Suponiendo que un programador tiene un error en una implementación de un diccionario con hashing doble, de modo que una de las dos funciones devuelve el mismo valor (distinto de 0), describir lo que sucede en cada situación (cuando es la primera función la que está mal y cuando lo es la segunda). | Suponiendo que un programador tiene un error en una implementación de un diccionario con hashing doble, de modo que una de las dos funciones devuelve el mismo valor (distinto de 0), describir lo que sucede en cada situación (cuando es la primera función la que está mal y cuando lo es la segunda). | ||