Estructuras de Datos

La dispersión cerrada consiste en asignar otra posición libre alternativa de la tabla a una clave cuya posición natural está ya ocupada. Verdadero. Falso.

Una de las ventajas de la dispersión cerrada es que se utilizan estructuras secundarias para almacenar las claves colisionadas. Verdadero. Falso.

La dispersión cerrada permite un mejor aprovechamiento del espacio de la tabla. Verdadero. Falso.

En la dispersión cerrada, si la posición natural de una clave está ocupada, esta se elimina para dejar espacio a la nueva clave. Verdadero. Falso.

La exploración lineal busca un hueco libre en posiciones consecutivas dentro de la tabla. Verdadero. Falso.

La función hash en exploración lineal se calcula como h(x) = (x + i) % t, donde i representa el número de intento empezando en 0. Verdadero. Falso.

En exploración lineal, el valor de i no cambia en cada intento para encontrar una posición libre. Verdadero. Falso.

La exploración lineal puede provocar agrupamientos secundarios, donde varias claves colisionan y se almacenan en posiciones consecutivas. Verdadero. Falso.

La exploración lineal tiende a generar agrupamientos que atrapan nuevos datos y tienden a crecer. Verdadero. Falso.

Los agrupamientos primarios son grupos de datos que tienen la misma posición natural h(x), es decir, h(x1) = h(x2). Verdadero. Falso.

En los agrupamientos primarios, datos que van a distintas posiciones naturales compiten por los mismos huecos durante la resolución de colisiones. Verdadero. Falso.

Los agrupamientos primarios no afectan el rendimiento de búsqueda en una tabla hash con exploración lineal. Verdadero. Falso.

Los agrupamientos secundarios se producen cuando dos datos distintos x1 y x2 tienen la misma posición natural, es decir, h(x1) = h(x2). Verdadero. Falso.

En los agrupamientos secundarios, los datos con posiciones naturales diferentes (h(x1) ≠ h(x2)) compiten por los mismos huecos. Verdadero. Falso.

Los agrupamientos secundarios pueden afectar la eficiencia de la exploración lineal porque aumentan las colisiones en una misma posición natural. Verdadero. Falso.

Los agrupamientos secundarios son causados principalmente por claves que tienen diferentes posiciones hash y se distribuyen uniformemente. Verdadero. Falso.

Los agrupamientos primarios y secundarios tienden a alejar los datos de su posición natural en la tabla hash. Verdadero. Falso.

Cuando crecen los agrupamientos, se rellenan zonas contiguas de memoria y aumenta la posibilidad de colisiones. Verdadero. Falso.

El crecimiento de agrupamientos no afecta el rendimiento de una tabla hash con exploración lineal. Verdadero. Falso.

La exploración lineal es una buena solución para la resolución de colisiones debido a su bajo impacto en el rendimiento. Verdadero. Falso.

La función hash utilizada en la exploración cuadrática es h(x) = (x + i²) % t, donde i es el número de intento. Verdadero. Falso.

La exploración cuadrática evita tanto los agrupamientos primarios como los secundarios. Verdadero. Falso.

En la exploración cuadrática, la distancia entre posiciones alternativas crece de forma lineal con el número de intento i. Verdadero. Falso.

La exploración cuadrática es una técnica que puede reducir la formación de agrupamientos primarios en tablas hash. Verdadero. Falso.

La dispersión doble utiliza una segunda función hash para resolver las colisiones. Verdadero. Falso.

La función de dispersión secundaria h2(x) puede tomar el valor 0 sin problema. Verdadero. Falso.

Un ejemplo válido de función h2(x) es: h2(x) = 1 + (x % q), donde q es un número primo menor que el tamaño de la tabla t. Verdadero. Falso.

Con una función h2(x) bien escogida, la dispersión doble puede evitar tanto agrupamientos primarios como secundarios. Verdadero. Falso.

En dispersión cerrada, un dato siempre está almacenado en su posición natural. Verdadero. Falso.

La búsqueda en dispersión cerrada se detiene cuando se encuentra el dato o cuando se llega a un hueco libre. Verdadero. Falso.

En dispersión cerrada, borrar un dato es sencillo porque siempre está en su posición natural. Verdadero. Falso.

La necesidad de continuar la búsqueda más allá de la posición natural complica las operaciones en tablas con dispersión cerrada. Verdadero. Falso.

Un borrado en una tabla con dispersión cerrada puede confundir la búsqueda de otros datos. Verdadero. Falso.

En dispersión cerrada, borrar un dato siempre simplifica la búsqueda de otros elementos. Verdadero. Falso.

Para evitar confusiones en la búsqueda después de un borrado, se suele utilizar un marcador especial que indica "espacio borrado". Verdadero. Falso.

Después de un borrado, la búsqueda siempre debe detenerse en el primer hueco libre encontrado. Verdadero. Falso.

Las posiciones borradas en una tabla hash se marcan como disponibles para resolver problemas de búsqueda. Verdadero. Falso.

En una tabla hash con dispersión cerrada, existen tres tipos de casillas: vacías, disponibles y ocupadas. Verdadero. Falso.

Las búsquedas y borrados en una tabla hash deben detenerse al encontrar una casilla marcada como disponible. Verdadero. Falso.

Las casillas disponibles permiten que la búsqueda continúe tras un borrado sin perder elementos almacenados más adelante. Verdadero. Falso.

En una tabla con cubetas, cada posición puede contener más de un dato. Verdadero. Falso.

Las tablas con cubetas aumentan el riesgo de tener que reasignar datos a otras posiciones. Verdadero. Falso.

En una tabla con cubetas, cada posición es un compartimento que puede almacenar cero o más elementos. Verdadero. Falso.

Las tablas con cubetas eliminan completamente la posibilidad de colisiones en una tabla hash. Verdadero. Falso.

Con una buena función de dispersión y un tamaño adecuado de tabla y cubeta, los datos deberían asignarse a la posición correcta. Verdadero. Falso.

Aunque se use una buena función de dispersión y cubetas adecuadas, siempre es necesario contar con una técnica de resolución de colisiones. Verdadero. Falso.

En tablas con cubetas, no es necesario usar técnicas de resolución de colisiones. Verdadero. Falso.

La exploración lineal es un ejemplo de técnica para resolver colisiones en tablas con cubetas. Verdadero. Falso.

Durante la inserción en tablas con cubetas, se usa una marca para identificar cubetas desbordadas. Verdadero. Falso.

En la búsqueda con cubetas, se detiene la búsqueda al encontrar el dato o al llegar a una cubeta que nunca se ha desbordado. Verdadero. Falso.

La búsqueda con cubetas no necesita controlar si una cubeta ha sido desbordada durante la inserción. Verdadero. Falso.

La marca de cubetas desbordadas ayuda a optimizar la búsqueda al evitar revisar cubetas vacías innecesariamente. Verdadero. Falso.

Una tabla de dispersión cerrada se deteriora notablemente con las inserciones y borrados. Verdadero. Falso.

Las casillas disponibles o cubetas desbordadas tienden a acortar las secuencias de búsqueda en la tabla. Verdadero. Falso.

La redispersión es una solución para mejorar el rendimiento, aunque tiene un coste esperado de O(n). Verdadero. Falso.

La dispersión cerrada es adecuada principalmente cuando se realizan muchas búsquedas y pocas inserciones o borrados. Verdadero. Falso.

El rendimiento O(1) para inserciones en dispersión cerrada está siempre garantizado, independientemente de la carga. Verdadero. Falso.

La dispersión cerrada es menos sensible que la dispersión abierta a factores de carga altos. Verdadero. Falso.

Las clases unordered_map y unordered_set de C++ STL se implementan como tablas de dispersión cerrada basadas en cubetas. Verdadero. Falso.

Las operaciones como insert, find y operator[] no están disponibles en unordered_map y unordered_set. Verdadero. Falso.

Las clases unordered_map y unordered_set no ofrecen métodos para conocer el estado de la tabla, como el factor de carga o el tamaño de las cubetas. Verdadero. Falso.

El método rehash permite cambiar el número de cubetas en una tabla dispersa para mejorar su rendimiento. Verdadero. Falso.

En las tablas de dispersión, es posible indicar una clase de dispersión específica para el tipo de dato utilizado. Verdadero. Falso.

No es posible especificar una clase de comparación de igualdad para las claves en tablas dispersas. Verdadero. Falso.

Indicar una clase de dispersión y una clase de comparación de igualdad permite personalizar el comportamiento de las tablas dispersas. Verdadero. Falso.

Las tablas de dispersión cerrada en STL son más eficientes que los mapas si la función de dispersión y el tamaño de la tabla están bien definidos. Verdadero. Falso.

Las tablas de dispersión cerrada en STL devuelven los datos ordenados al iterar sobre ellas. Verdadero. Falso.

La implementación dinámica de las tablas en STL implica ampliar el tamaño y redistribuir los datos cuando el factor de carga se acerca a 1. Verdadero. Falso.

Es recomendable usar la operación resize() para indicar desde el principio el tamaño aproximado de la tabla. Verdadero. Falso.

La dispersión cerrada es más sencilla y aprovecha mejor el espacio que la dispersión abierta, pero puede sufrir más problemas de rendimiento. Verdadero. Falso.

El uso de cubetas en tablas de dispersión aumenta el riesgo de colisiones. Verdadero. Falso.

Las tablas con cubetas son especialmente recomendadas para almacenamiento en memoria secundaria, como ficheros. Verdadero. Falso.

Existe una extensión de la STL que implementa conjuntos y mapas mediante tablas de dispersión. Verdadero. Falso.

La dispersión cerrada utiliza memoria secundaria, como ficheros, para almacenar los datos. Verdadero. Falso.

La dispersión cerrada disminuye el número de colisiones, pero no las elimina por completo. Verdadero. Falso.

En la dispersión cerrada, cuando la posición natural de una clave está ocupada, se busca una posición alternativa libre en la tabla. Verdadero. Falso.

La exploración cuadrática evita tanto agrupamientos primarios como secundarios. Verdadero. Falso.

El método rehash en tablas hash permite cambiar el tamaño de la tabla y redistribuir los elementos para mejorar el rendimiento. Verdadero. Falso.

Las tablas con cubetas pueden almacenar múltiples datos en una misma posición para reducir colisiones. Verdadero. Falso.

La dispersión doble utiliza dos funciones de dispersión para minimizar tanto los agrupamientos primarios como secundarios. Verdadero. Falso.