Tablas hash y funciones de dispersión
Nombre: ___________________________
Fecha: ____________________________
Puntaje: __________________________
1.
¿Qué es una tabla hash?
Una estructura que asocia claves con valores mediante una función de dispersión.
Una lista enlazada ordenada.
Un árbol binario de búsqueda balanceado.
Una estructura que asocia claves con valores mediante una función de dispersión.
2.
La función que se encarga de transformar una clave en un índice dentro de la tabla se llama función de ______.
Respuesta: ____________________________________________
dispersión
3.
¿Cuál de los siguientes es un requisito para una buena función de dispersión?
Debe ser determinista.
Debe ser computacionalmente eficiente.
Debe distribuir uniformemente las claves.
Todas las anteriores.
Todas las anteriores.
4.
En el encadenamiento (chaining), las colisiones se manejan:
Buscando la siguiente posición vacía.
Almacenando los elementos que colisionan en una lista enlazada.
Usando una segunda función hash.
Ignorando la colisión.
Almacenando los elementos que colisionan en una lista enlazada.
5.
El cociente entre el número de elementos almacenados y el tamaño de la tabla se denomina ______.
Respuesta: ____________________________________________
factor de carga
6.
En direccionamiento abierto con sondeo lineal, si la posición h(k) está ocupada, el siguiente paso es:
Rehashing.
Revisar la siguiente posición secuencialmente.
Usar doble hash.
Duplicar el tamaño de la tabla.
Revisar la siguiente posición secuencialmente.
7.
¿Cuál de las siguientes NO es una técnica de manejo de colisiones?
Encadenamiento.
Sondeo lineal.
Rehashing.
Ordenamiento.
Ordenamiento.
8.
Cuando el factor de carga supera un umbral, se aumenta el tamaño de la tabla y se reinsertan los elementos usando una nueva función de dispersión. Este proceso se llama ______.
Respuesta: ____________________________________________
rehashing
9.
En doble hash, el tamaño del paso para el sondeo se determina mediante:
Una segunda función hash.
El cociente entre la clave y el tamaño de la tabla.
La inversión de la clave.
El número de colisiones previas.
Una segunda función hash.
10.
Si todas las claves de una tabla hash con encadenamiento caen en el mismo índice, el tiempo de búsqueda en el peor caso es:
O(1)
O(log n)
O(n)
O(n log n)
O(n)
11.
El umbral típico del factor de carga para redimensionar una tabla hash en la práctica es:
0.5
0.75
1.5
0.75
12.
El término que describe cuando dos o más claves diferentes se asignan al mismo índice se llama ______.
Respuesta: ____________________________________________
colisión
13.
¿Cuál es una ventaja del encadenamiento sobre el direccionamiento abierto?
Eliminación de elementos más sencilla.
No hay límite en el factor de carga.
Mejor rendimiento de caché.
Todas las anteriores.
Eliminación de elementos más sencilla.
14.
Si una función de dispersión está mal diseñada y produce muchas colisiones, el principal efecto es:
Mayor velocidad de inserción.
Menor velocidad de búsqueda.
No hay impacto.
Mejora el uso de memoria.
Menor velocidad de búsqueda.
15.
Considere una tabla hash de tamaño 10 con sondeo lineal. Se insertan las claves 12, 22 y 32, usando h(k)=k%10. ¿En qué índice queda finalmente la clave 32?
2
3
4
4
16.
En direccionamiento abierto, para marcar una posición como eliminada sin romper la secuencia de sondeo, se utiliza un valor especial llamado ______.
Respuesta: ____________________________________________
centinela
17.
El agrupamiento primario (primary clustering) en direccionamiento abierto está asociado principalmente con:
Sondeo lineal.
Sondeo cuadrático.
Doble hash.
Sondeo aleatorio.
Sondeo lineal.
18.
Una función de dispersión que produce un índice único para cada clave (cuando las claves se conocen de antemano) se llama:
Función hash perfecta.
Función hash sin colisiones.
Función hash criptográfica.
Función hash identificadora.
Función hash perfecta.
19.
En comparación con un árbol binario de búsqueda balanceado, una tabla hash generalmente ofrece:
Búsqueda promedio más rápida bajo buenas condiciones.
Orden garantizado de los elementos.
Menor uso de memoria en todos los casos.
Búsqueda promedio más rápida bajo buenas condiciones.
20.
Una tabla hash con un factor de carga de 0 significa:
La tabla está completamente llena.
La tabla está vacía.
La tabla tiene la mitad de su capacidad.
Es un valor inválido.
La tabla está vacía.
Respuestas
-
A.
Una estructura que asocia claves con valores mediante una función de dispersión.
-
dispersión
-
D.
Todas las anteriores.
-
B.
Almacenando los elementos que colisionan en una lista enlazada.
-
factor de carga
-
B.
Revisar la siguiente posición secuencialmente.
-
D.
Ordenamiento.
-
rehashing
-
A.
Una segunda función hash.
-
C.
O(n)
-
B.
0.75
-
colisión
-
A.
Eliminación de elementos más sencilla.
-
B.
Menor velocidad de búsqueda.
-
C.
4
-
centinela
-
A.
Sondeo lineal.
-
A.
Función hash perfecta.
-
A.
Búsqueda promedio más rápida bajo buenas condiciones.
-
B.
La tabla está vacía.