• Author / Uploaded
• Jorge Marcillo

Citation preview

Tablas de Hash 1.- Se tiene una tabla de Hash cerrado parcialmente llena. Para optimizar el espacio se planea redispersar los datos a una nueva tabla con menos cubetas. Sabiendo que originalmente los datos fueron ingresados en orden alfabético y conociendo el número de colisiones existentes al llenar la tabla original, llene la nueva tabla de hash usando una función lineal. Cubetas

# colisiones

0

F

1

1

G

1

2

Cubetas

0

3

A

0

1

4

C

1

2

5

3

6

4

7

5

8

B

0

9

D

1

10

E

2

6

2.- Dada la siguiente tabla con hashing abierto (acepta colisiones) como quedaría la tabla si fuera un hashing cerrado(no acepta colisiones) y tiene una función rehashing lineal. Considere que el orden como fueron ingresados los elementos en sus posiciones fue alfabéticamente. Tabla Inicial (hashing abierto)

3.- Considere las asociaciones entre los siete valores y las siete claves mostrados en la tabla. Clave 24 48 32 66 22 40 49

Valor E B D A F C G

Asuma un escenario donde se desea insertar estos valores en el orden mostrado, del 1 al 7, en una tabla de Hash, de tamaño 7, que utilizan aritmética modular como función de dispersión. Escriba el valor que almacenarán las cubetas de cada una de las tablas de Hash que resultan de aplicar las siguientes estrategias de re-dispersión o re-hashing: Cubetas

Estrategia

0

1

2

3

4

5

6

Re-hashing Lineal Re-hashing función

con

doble

h' ( x)=(2 x−3)mod B 4.- Una universidad desea generar unos talleres especiales con una cantidad fija de estudiantes(30). A los participantes se les asigna una identificación unicamente para el taller y correspondiente al orden de inscripción. a) Defina: El TDA estudiante que contenga las calificaciones ponderadas que se obtendrán durante el taller. Agregue todos los campos que considere necesarios. El TDA Taller que almacenara al conjunto de estudiantes inscritos. b) Ahora proponga 2 TDA similares a los anteriores pero que cumplan con los siguientes nuevos requisitos: - Se debe de poder buscar al estudiante por su numero de matricula (previamente asignado) Esta operación debe ser altamente eficiente y de tiempo constante. - La cantidad de estudiantes puede variar entre 20 y 30 estudiantes. 5.-A partir del TDA HashMap de la librería del curso: a) Diseñar e implementar la versión del TDA con hashing abierto. b) Se define el índice radial de una Tabla Hash abierta como el número de cubetas de la tabla multiplicado por el número de elementos de la lista enlazada con mayor tamaño de todas. Diseñar un algoritmo adecuado para calcular tal índice radial. 6.- Se dispone de una aplicación de radares de tráfico que permite llevar la contabilidad del número de veces que ha pasado un determinado coche por dicho radar superando el límite de velocidad. Para ello se consulta un Diccionario (Diccionario) implementado mediante una Tabla Hash. Con el fin de contabilizar el número de veces que ha pasado un coche se requiere actualizar el Diccionario de la aplicación. Implemente una función que dado el Diccionario y un numero de matricula realice el proceso de actualización.