Instrucciones: Conteste cada una de las siguientes preguntas. Cada pregunta vale un número entero entre cero y cinco puntos. La calificación de esta tarea será la suma de esos puntos dividida entre cuatro.

Pregunta 1: Considere la cadena formada por la concatenación de todas las letras de FRANCISCO, JAVIER, ZARAGOZA, MARTINEZ y las de todos sus nombres, sepárelas de dos en dos (FR, AN, CI, ...) e insértelas en un índice simple. Ahora ponga primero las letras de todos sus nombres y luego las de los míos, sepárelas de dos en dos y bórrelas del índice.

Pregunta 2: ¿Se podrá realizar la operación XOR de forma cosecuencial en dos listas? Justifique su respuesta. NOTA: la operación XOR entre dos listas de entrada produce una lista de salida en la cual aparecen aquellas entradas que están en exactamente una lista de entrada.

Pregunta 3: Suponga que tiene una cinta con 1,000,000,000 de registros y que cada registro contiene únicamente un caracter ASCII. Describa un algoritmo eficiente que escriba al final de los registros grabados en esa misma cinta todos los registros ordenados de forma ascendente.

Pregunta 4: Suponga que tiene una capacidad de memoria para M registros de tamaño fijo y que tiene dos archivos con KM registros cada uno (donde K es un entero mayor que 1). Más aún, suponga que un archivo está ordenado ascendentemente y el otro descendentemente. Describa un algoritmo eficiente para producir un archivo de salida que contenga los 2KM registros ordenados ascendentemente.

Pregunta 5: Muestre el proceso de creación de un árbol B de orden 5 donde las claves son las mismas que insertó en el índice de la pregunta 1.

Pregunta 6: Muestre el proceso de creación de un árbol B+ donde las claves son las mismas que insertó en el índice de la pregunta 1, el orden del árbol B es 3 y en cada secuencia hay un mínimo de 2 y un máximo de 4 claves.

Pregunta 7: Calcule el código de dispersión de cada uno de sus nombres, utilizando los códigos ASCII de las letras mayúsculas sin acentos, división en bloques de 8 bits y el número primo 251. Hágalo haciendo primero la suma y luego el residuo.

Pregunta 8: Suponga que tiene N claves y 4N posiciones de memoria disponibles. En cuál de los siguientes dos casos espera que ocurran menos colisiones: (a) Usando una función de dispersión donde a cada clave le toque una de las 4N posiciones de memoria disponibles. (b) Usando una función de dispersión donde a cada clave le toque un bloque de cuatro posiciones de memoria [recuerde que en este caso sólo ocurrirá una colisión cuando se tenga una quinta clave en ese bloque].