Estructuras de Datos

Una tabla de dispersión utiliza un vector de tamaño predeterminado para almacenar datos. Verdadero. Falso.

El índice donde se guarda un dato en una tabla de dispersión se determina aleatoriamente. Verdadero. Falso.

Las tablas de dispersión son una implementación de un contenedor asociativo. Verdadero. Falso.

En una tabla de dispersión, la clave de un dato no influye en la posición donde se almacena. Verdadero. Falso.

Las tablas de dispersión pueden tener un tamaño que cambia dinámicamente sin afectar su funcionamiento. Verdadero. Falso.

En una tabla hash con clave entera, la operación de inserción se realiza asignando el dato a la posición indicada por la clave: tabla[clave] = dato. Verdadero. Falso.

Para buscar un dato en una tabla hash, se verifica si tabla[clave] es diferente de nulo. Verdadero. Falso.

El borrado en una tabla hash se realiza asignando nulo a la posición de la clave: tabla[clave] = nulo. Verdadero. Falso.

Un problema común de las tablas hash es que la clave puede ser alfanumérica y no solo entera. Verdadero. Falso.

Otro problema es que el rango de claves puede ser muy grande, lo que haría que la tabla hash sea demasiado pequeña. Verdadero. Falso.

Para manejar claves alfanuméricas o rangos muy grandes, es necesario usar funciones hash que transformen la clave en un índice manejable. Verdadero. Falso.

Una función de dispersión h(x) asocia cada clave con una posición específica en la tabla hash. Verdadero. Falso.

La función de dispersión siempre asigna claves distintas a posiciones distintas en la tabla. Verdadero. Falso.

El rango de posibles valores de las claves suele ser mayor que el número de posiciones disponibles en la tabla. Verdadero. Falso.

Una buena función de dispersión debe distribuir las claves de manera uniforme entre todas las posiciones de la tabla. Verdadero. Falso.

La función de dispersión transforma claves del mismo tipo (por ejemplo, enteras) en posiciones aleatorias dentro de la tabla. Verdadero. Falso.

Una buena función de dispersión debe tener un bajo coste de cálculo. Verdadero. Falso.

Una función de dispersión determinista devuelve diferentes posiciones cada vez que se evalúa con la misma clave. Verdadero. Falso.

Una buena función de dispersión debe distribuir las claves de manera uniforme en todo el rango de la tabla. Verdadero. Falso.

Es posible diseñar una función de dispersión que impida completamente las colisiones. Verdadero. Falso.

Las colisiones ocurren cuando dos claves diferentes son transformadas en la misma posición por la función de dispersión. Verdadero. Falso.

La dispersión por división se define como h(x) = x % t, donde t es el tamaño de la tabla. Verdadero. Falso.

La dispersión por división es óptima en todos los casos y no presenta desventajas. Verdadero. Falso.

El método de dispersión por división funciona mejor si el tamaño de la tabla t es un número primo. Verdadero. Falso.

Si el tamaño de la tabla t no es primo, se recomienda usar una fórmula como h(x) = (x % p) % t, donde p es un número primo mayor que t. Verdadero. Falso.

La fórmula h(x) = (x % p) % t no tiene ninguna ventaja sobre h(x) = x % t. Verdadero. Falso.

La dispersión por plegamiento es especialmente útil cuando las claves son grandes. Verdadero. Falso.

En la dispersión por plegamiento, la clave se divide en grupos de dígitos antes de ser procesada. Verdadero. Falso.

Después de dividir la clave en grupos de dígitos, se multiplican esos grupos entre sí para obtener la posición. Verdadero. Falso.

Para obtener una posición válida dentro de la tabla, puede aplicarse un módulo sobre el resultado de la suma de los grupos. Verdadero. Falso.

La dispersión por plegamiento no utiliza operaciones aritméticas como suma o módulo. Verdadero. Falso.

La dispersión por mitad del cuadrado es especialmente útil para trabajar con números reales. Verdadero. Falso.

El método de mitad del cuadrado consiste en elevar la clave al cuadrado y luego usar los dígitos centrales del resultado como índice. Verdadero. Falso.

La dispersión por mitad del cuadrado se basa en el uso de funciones aleatorias para generar los índices. Verdadero. Falso.

El objetivo de tomar los dígitos centrales tras elevar al cuadrado es evitar los patrones que se encuentran en los dígitos más altos o bajos. Verdadero. Falso.

El método de mitad del cuadrado se puede aplicar solo si la clave es un número primo. Verdadero. Falso.

Una solución trivial para aplicar una función de dispersión a una cadena es sumar los valores de sus caracteres. Verdadero. Falso.

Sumar los caracteres de una cadena garantiza una buena dispersión de las claves. Verdadero. Falso.

El problema principal de sumar los caracteres de una cadena es que puede producir la misma posición para cadenas distintas. Verdadero. Falso.

“CASA” y “SACA” pueden producir la misma posición si se usa la suma de caracteres como función de dispersión. Verdadero. Falso.

Para cadenas, se recomienda siempre usar funciones hash más complejas que consideren la posición de cada carácter. Verdadero. Falso.

Existen algoritmos más avanzados y eficientes que la suma de caracteres para dispersar cadenas. Verdadero. Falso.

El algoritmo djb2, creado por Dan Bernstein, es un ejemplo de una buena función de dispersión para cadenas. Verdadero. Falso.

El algoritmo djb2 produce colisiones intencionalmente para simplificar el cálculo. Verdadero. Falso.

El algoritmo djb2 es adecuado para claves alfanuméricas, como las cadenas de texto. Verdadero. Falso.

Los algoritmos como djb2 no son deterministas; pueden dar resultados distintos para la misma cadena. Verdadero. Falso.

El usuario de una tabla hash debe decidir el tamaño de la tabla antes de empezar a usarla. Verdadero. Falso.

El factor de carga λ de una tabla hash se define como el cociente entre el número de datos n y el tamaño de la tabla t. Verdadero. Falso.

Un valor de λ entre 0.0 y 0.7 indica que el número de accesos necesarios para buscar un dato tiende a mantenerse constante. Verdadero. Falso.

Cuando el factor de carga supera 0.7, el número de colisiones y accesos necesarios disminuye. Verdadero. Falso.

Se recomienda que el tamaño de la tabla t sea al menos un 33% mayor que el número de datos esperados. Verdadero. Falso.

En una tabla hash, como en los árboles AVL, el tamaño se ajusta automáticamente a medida que se insertan datos. Verdadero. Falso.

La dispersión abierta es una técnica que se utiliza para resolver colisiones en tablas hash. Verdadero. Falso.

En la dispersión abierta, cada posición de la tabla contiene una única entrada. Verdadero. Falso.

El encadenamiento separado es otro nombre para la dispersión abierta. Verdadero. Falso.

En la dispersión abierta, no se necesita una función de dispersión porque todos los elementos se colocan en listas. Verdadero. Falso.

La dispersión abierta permite insertar múltiples claves que colisionan en la misma posición sin perder datos. Verdadero. Falso.

La dispersión en tablas hash requiere conocer de antemano el número máximo de datos que se almacenarán. Verdadero. Falso.

La redispersión consiste en recalcular la posición de los elementos en una nueva tabla de diferente tamaño. Verdadero. Falso.

Cuando el factor de carga λ supera 0.7, se recomienda hacer una redispersión a una tabla más grande. Verdadero. Falso.

La redispersión solo se realiza cuando el número de datos aumenta, pero no cuando disminuye. Verdadero. Falso.

Una buena estrategia al aumentar el tamaño de la tabla es duplicar su tamaño anterior. Verdadero. Falso.

La dispersión ofrece una estructura asociativa con un rendimiento óptimo constante O(1) para las operaciones básicas. Verdadero. Falso.

Para que la dispersión funcione eficientemente, no es necesario conocer la naturaleza de las claves. Verdadero. Falso.

Una buena función de dispersión es irrelevante para el rendimiento de una tabla hash. Verdadero. Falso.

Dimensionar correctamente la tabla hash ayuda a evitar operaciones de redispersión costosas. Verdadero. Falso.

La dispersión es una técnica compleja que no es recomendada para implementaciones sencillas. Verdadero. Falso.

La dispersión es la técnica más utilizada para mantener las tablas de símbolos en compiladores e intérpretes. Verdadero. Falso.

La dispersión abierta es la forma más directa de implementar una tabla hash. Verdadero. Falso.

La dispersión abierta no requiere ninguna estructura de datos secundaria para su funcionamiento. Verdadero. Falso.

En aplicaciones que manejan datos en disco, la dispersión abierta puede no ser viable. Verdadero. Falso.

La dispersión abierta es la técnica más eficiente para manejar tablas en todos los sistemas de almacenamiento. Verdadero. Falso.

La dispersión abierta utiliza estructuras de datos dinámicas, por lo que es adecuada principalmente para uso en memoria principal. Verdadero. Falso.

La dispersión cerrada es una técnica que solo puede implementarse en lenguajes de bajo nivel. Verdadero. Falso.

La dispersión cerrada usa exclusivamente un vector y resuelve colisiones reubicando los datos dentro de ese vector. Verdadero. Falso.

La dispersión cerrada requiere estructuras dinámicas como listas enlazadas para manejar las colisiones. Verdadero. Falso.

La dispersión abierta no es adecuada para su uso en ficheros debido a que requiere estructuras dinámicas. Verdadero. Falso.

En la dispersión cerrada, cuando ocurre una colisión, se puede usar una técnica de sondeo lineal para encontrar una nueva posición libre. Verdadero. Falso.

La dispersión abierta es menos eficiente que la dispersión cerrada cuando la tabla está muy llena, debido al uso de listas enlazadas. Verdadero. Falso.

La dispersión cerrada no requiere conocer el tamaño máximo de datos a insertar, ya que puede crecer dinámicamente. Verdadero. Falso.