lunes, 19 de mayo de 2014

Unidad 7: Métodos de Búsqueda Parte 2


Cuestionario

1.- ¿Qué es y en qué consiste la búsqueda lineal?

El algoritmo de búsqueda lineal busca por cada elemento de un arreglo en forma secuencial. Si la clave de búsqueda no coincide con un elemento en el arreglo, el algoritmo evalúa cada elemento y, cuando se llega al final del arreglo, informa al usuario que la clave de búsqueda no está presente. Si la clave de búsqueda se encuentra en el arreglo, el algoritmo evalúa cada elemento hasta encontrar uno que coincida con la clave de búsqueda y devuelve el índice de ese elemento.


          2.-  ¿Qué es y en qué consiste la búsqueda binaria?

El algoritmo de búsqueda binaria es más eficiente que el algoritmo de búsqueda lineal, pero requiere que el arreglo se ordene. La primera iteración de este algoritmo evalúa el elemento medio del arreglo. Si éste coincide con la clave de búsqueda, el algoritmo termina. Suponiendo que el arreglo se ordene en forma ascendente, entonces si la clave de búsqueda es menor que el elemento de en medio, no puede coincidir con ningún elemento en la segunda mitad del arreglo, y el algoritmo continúa sólo con la primera mitad (es decir, el primer elemento hasta, pero sin incluir, el elemento de en medio). Si la clave de búsqueda es mayor que el elemento de en medio, no puede coincidir con ninguno de los elementos de la primera mitad del arreglo, y el algoritmo continúa sólo con la segunda mitad del arreglo (es decir, desde el elemento después del elemento de en medio, hasta el último elemento). Cada iteración evalúa el valor medio de la porción restante del arreglo. Si la clave de búsqueda no coincide con el elemento, el algoritmo elimina la mitad de los elementos restantes. Para terminar, el algoritmo encuentra un elemento que coincide con la clave de búsqueda o reduce el subarreglo hasta un tamaño de cero.


  3.-  ¿Qué es y en que consiste la transformación Haves Hashing?

El grupo de búsquedas por transformación de llaves (Hash), aumenta la eficiencia, en cuanto al tiempo de ejecución, ya que accede a los registros por lo general más rápidamente, pero va a depender de su implementación.
Entre las ventajas que trae consigo están:

  •  Aumentar la velocidad de ejecución, independientemente del número de elementos que contenga la lista.

  •  Los elementos de la lista donde se realiza la búsqueda no forzosamente deben estar clasificados. La lista de datos, puede estar en un archivo o en un arreglo.

  •  No se necesita recorrer todos los registros anteriores (como en la búsqueda secuencial) o realizar muchas comparaciones (como podría llegar a ser en la búsqueda binaria). Idealmente encontraría directamente el registro que se está buscando.

Las funciones de Hash, para lograr su objetivo de proporcionar la dirección donde debe estar el elemento buscado a partir de su llave, lo logran haciendo algunas operaciones sobre los caracteres que la componen. Es importante hacer notar que la misma función de Hash, que se utiliza, para almacenar, es la misma que se ocupa para recuperar la llave. Cuando se transforma la llave por el método de suma, por ejemplo al sumar el primer dígito con el tercero, dará como resultado la dirección donde se almacenará el registro, pero se puede presentar el caso de que la dirección ya esté ocupada por otro elemento.
     
     4.-  ¿Cuál es el algoritmo para la búsqueda secuencial (lineal)?

inicio
i=0

bandera = 0

mientras i < n

si k [ i] = x

inicio

desplegar “búsqueda exitosa y el dato es” x

desplegar “y se encuentra en la posición” i i=n

bandera = 1

else

i=i+1

fin

fin

si bandera = 0

desplegar “no se encontró el dato en la lista”

fin

5.- ¿Cuál es el algoritmo para la búsqueda binaria?

inicio

LI = 0

LS = n – 1

mientras LI ~LS

M = Parte Entera (LI + LS) /2)

si dato< lista[M]

LS = M -1

en caso contrario si dato> lista [M]

LI = M +1

en caso contrario

desplegar “el elemento buscado está en la posición”, M

break

fin


desplegar “el elemento” dato “no se encontró en la lista”



1.       El arreglo debe estar previamente ordenado

2.       Se compara el dato con la posición del centro

3.       Si coinciden hemos encontrado el dato

4.       Si no:

4.1   Si el dato es menor al del centro, se busca en la primera mitad del arreglo

4.2   Si el dato es mayor al del centro, se busca en la segunda mitad del arerglo


No hay comentarios.:

Publicar un comentario