Centro Asociado de Asturias CABUEÑES –GIJÓN

1.-    Para encontrar la primera presencia de una palabra en un texto se dispone de tres algoritmos: el método de búsqueda directa de cadena, el método de Knuth-Morris-Pratt (KMP) y el algortimo de Booyer-Moore (BM).

a) Indicar cuál de ellos utilizaría para encontrar una palabra en un texto con 10000 caracteres. ¿Utilizaría el mismo si el texto fuera de 50 caracteres?. Explique su elección en cada caso razonando comparativamente, es decir, mostrando sus ventajas respecto a los otros métodos.

b) Explicar claramente como se realiza la comparación de caracteres en el algoritmo de Boyer-Moore y como se calcula su tabla de distancias. Implementar en modula-2 el segmento de código para calcular dicha tabla.

(NO ENTRA CON EL TEMARIO ACTUAL) RESOLUCIÓN

2.-    Explicar detalladamente el método de inserción binaria utilizando para ello el siguiente arreglo inicial

Completar en Modula-2 el código del siguiente programa para que realice el algoritmo de inserción binaria y realizar el análisis del programa, calculando el número de comparaciones y movimientos.

PROCEDURE insercion_binaria;
    VAR I,j,m,L,R :    INTEGER;
     x :                INTEGER
BEGIN
     FOR i:=2 TO n DO
          x:=a[I];
         L:= ... ; R:= ... ;
         WHILE ... DO
              m:= ...
               IF ... THEN L:=m+1 ELSE R:=m END;
         END
         FOR j:=i TO R+1 BY –1 DO ... END;
     a[R]:=x;
     END;
END;

RESOLUCIÓN

Fórmulas: ,

3.-    Se dispone de dos listas enlazadas construidas dinámicamente con nodos del mismo tipo base y de igual longitud. Realizar un procedimiento en Modula-2 que determine si ambas listas son iguales o diferentes. Serán iguales si el campo llave del primer nodo tiene el mismo valor en ambas listas, el campo llave del segundo nodo tiene el mismo valor en ambas listas, y así sucesivamente.

RESOLUCIÓN

4.-    Explicar detalladamente en qué consisten las tablas de transformación de llaves (hashing), cuáles son sus características y las ideas fundamentales necesarias para elegir una función de transformación. Explicar qué es una colisión y cómo se realiza el manejo de colisiones en general. Detallar la exploración lineal y cuadrática.

RESOLUCIÓN