Búsqueda De Datos

Búsqueda de Datos

Estructura de Datos

Instituto IACC

Enero de 2015

Desarrollo

1. Defina con sus propias palabras, qué se entiende por “colisiones” en el tratamiento de los datos mediante Tablas Hash y explique cuáles son las medidas que podemos utilizar para tratarlas.

Para poder explicar lo que se entiende por “colisiones” en el tratamiento de los datos mediante Tablas Hash, primero debemos comprender el funcionamiento de dichas tablas.

Al usar el sistema de búsquedas en Tablas Hash resolvemos la búsqueda con mayor rapidez, sin necesidad de que los elementos del arreglo estén ordenados con anterioridad. En este se le asigna un índice a cada elemento mediante una función de conversión llamada Hash (existen distintos métodos para hacer una función de conversión); La colisión se produce cuando mediante el uso de estas funciones, asignamos el mismo índice para dos o más elementos del arreglo.

Las medidas que podemos usar para tratar las colisiones producidas en el uso de tablas hash son:

 Se puede asignar el primer índice libre a partir de la posición de colisión, aunque este método no es muy eficaz si es que al nuevo elemento se le asigna un índice que ya esté ocupado, generando nuevamente una colisión haciendo este proceso más lento.

 Dejar lugares al final del arreglo para asignar el índice de las colisiones, pero tenemos la desventaja de no saber cuántos lugares debemos reservar. Este método también puede hacer que el proceso sea más lento cuando el elemento buscado es una colisión.

 Crear un arreglo de punteros, en lugar de un arreglo de números, cada puntero señalará el inicio de una lista enlazada. Cada elemento que enlaza con un determinado índice se coloca en el último lugar de la lista. Este es el método más efectivo y reduce el tiempo de búsqueda

2. Defina con sus propias palabras los siguientes términos e indique brevemente cómo trabajan sus algoritmos básicos. Indique para cada uno de ellos de qué orden es el tiempo de ejecución esperado de dichos algoritmos:

a. Búsqueda Secuencial.

En esta forma de búsqueda se recorre todo el arreglo de forma secuencial (de principio a fin) buscando el elemento deseado y devolviendo la posición que tiene este dentro del arreglo.

Como la búsqueda se realiza dentro de todo el arreglo su tiempo de ejecución es mayor que en la búsqueda binaria.

b. Búsqueda Binaria.

La búsqueda binaria se realiza dividiendo en dos el arreglo previamente ordenado y comparando el elemento buscado con el elemento central del arreglo. Como el arreglo ya está ordenado, según la comparación realizada con el elemento intermedio me quedaré con la primera o segunda parte del arreglo, en la que

...