Ejercicios · Estructuras C21¶
Actividades para trabajar en el navegador, en el orden de los temas de la clase. Los programas y los valores no son los de la sesión: mismo tema, ronda nueva.
TAD tabla de direccionamiento directo¶
casillas¶
Una tabla de ocho casillas y nueve operaciones: qué casilla toca cada una, qué queda guardado y qué pasa con una clave fuera del universo.
costos¶
El costo de buscar, de crear la tabla y de encontrar la clave más pequeña, y tres universos para decidir si la tabla directa sirve: edades, habitaciones de hotel y placas de carro.
contar¶
Puntajes de un quiz contados en una tabla de contadores, el recorrido que la imprime y los bytes que ocupan dos tablas.
banderas¶
Un arreglo con dos valores repetidos: dónde se detiene la versión que compara pares y dónde la que marca banderas, y cuándo deja de convenir la tabla.
Pocas claves, universo enorme: la función hash¶
universo¶
Cuánto ocupa una tabla de direccionamiento directo para teléfonos de 7 dígitos, qué parte de ella se usa y cuánto cuesta buscar en una lista enlazada.
casilla¶
El método de la división con m = 17: la casilla de cada clave, los pares que chocan y lo que pasa con una tabla de 1000 casillas.
cadenas¶
La suma de los códigos y el polinomio en base 31 sobre mar y ram, paso a
paso.
Encadenamiento¶
encadenar¶
Seis claves que entran a una tabla de cinco casillas, colgando al frente de cada lista, y el factor de carga que queda.
buscar¶
Cuántas comparaciones hace cada búsqueda y qué puntero cambia al eliminar.
Lo que cuesta¶
carga¶
El promedio de las listas frente a la más larga, la búsqueda en el peor caso y la cota de 1 + α.
escoger¶
Las mismas claves con m = 100, 128 y 97: cuántas casillas se usan y cuánto mide la lista más larga.
Para el juez¶
negativos¶
El residuo de C++ con claves negativas y la corrección que deja la casilla entre 0 y m − 1.