Final 01/03/23 (Algoritmos II)

De Cuba-Wiki
Revisión del 19:46 18 ago 2023 de 179.37.47.100 (discusión) (→‎Ejercicio 2)
(difs.) ← Revisión anterior | Revisión actual (difs.) | Revisión siguiente → (difs.)

Ejercicio 1

Problemas de axiomatizar otras operaciones sobre generadores. Dar un ejemplo de una operación que rompa la congruencia y otro que no.

Ejercicio 2

Explicar el invariante de un B-tree (no confundir con arbol binario, es otra estructura). Explicar por qué queremos árboles balanceados y consecuencia en sus algoritmos dar ejemplos de árboles balanceados y no balanceados.

Ejercicio 3

Era de tablas de hash. Explicar que función/característica tiene que cumplir la función de hash. Por qué no es bueno tener como clave de una tabla hash un objeto mutable como una lista. Sean a , b enteros b no negativo X = a ^ b

Ejercicio 4

Dar la estructura de divide and conquer en un array. Cómo obtener complejidad logarítmica en un algoritmo. Que modificación hay que hacer a búsqueda binaria para que de lineal.

Ejercicio 5

SelectionSort, insertionSort, mergeSort, heapSort y quickSort. A cuáles puedo cortar meter elementos nuevos y seguir. Cuáles son aptos sin modificaciones con modificaciones y no aptos.