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.
2.
La función que se encarga de transformar una clave en un índice dentro de la tabla se llama función de ______.
Respuesta: ____________________________________________
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.
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.
5.
El cociente entre el número de elementos almacenados y el tamaño de la tabla se denomina ______.
Respuesta: ____________________________________________
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.
7.
¿Cuál de las siguientes NO es una técnica de manejo de colisiones?
Encadenamiento.
Sondeo lineal.
Rehashing.
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: ____________________________________________
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.
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)
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
12.
El término que describe cuando dos o más claves diferentes se asignan al mismo índice se llama ______.
Respuesta: ____________________________________________
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.
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.
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
16.
En direccionamiento abierto, para marcar una posición como eliminada sin romper la secuencia de sondeo, se utiliza un valor especial llamado ______.
Respuesta: ____________________________________________
17.
El agrupamiento primario (primary clustering) en direccionamiento abierto está asociado principalmente con:
Sondeo lineal.
Sondeo cuadrático.
Doble hash.
Sondeo aleatorio.
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.
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.
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.