Saltar a contenido

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.