Cátedra: Saubidet

1. Primer Cuatrimestre de 2007. Examen parcial, primera oportunidad: 10/05/2007.
   1) Se tiene un archivo indexado con información sobre la performance de distintos atletas. El formato de registro es: (código, apellido y nombre, tiempo 40 yardas, peso, altura, tiempo 100 yardas). Se desea obtener un listado, de los 10 atletas que mejor posicionados estén en tanto las 40 como las 100 yardas de la siguiente forma: si un atleta esta primero en las 40 yardas y cuarto en las 100 yardas entonces 1+4 = 5 : 5/2 = 2.5. En el listado se quieren los 10 atletas para los cuales este calculo sea el menor. Programar en lenguaje “C” usando las primitivas correspondientes un programa que genere el listado pedido en un archivo de texto. (* * * *) (15 pts)
   
   Criterio: Ejercicio 1: Es fundamental evitar recorrer todos los registros del archivo. Si por ejemplo los 10 primeros en cada categoría fueran los mismos atletas pero en distinto orden es claro que leyendo solo los 10 primeros registros del archivo se puede emitir el listado sin leer miles de registros innecesarios. Para lograr esto hay que usar un índice secundario por cada uno de los tiempos e ir haciendo una especie de apareo del archivo consigo mismo. Llega un punto en el cual se sabe que nada que se lea del archivo puede superar al décimo promedio actual con lo cual se puede terminar de procesar.
   Las soluciones basadas en usar los dos índices secundarios y la condición de corte valen hasta 15 puntos independientemente de como se procesen los datos leídos hasta el momento, puede ser en memoria, en un archivo auxiliar (descuento de 1 punto), etc.
   Las soluciones que leen todos los registros del archivo valen como máximo 8 puntos.
   Hay una solución que es particularmente ineficiente que es aquella en la cual se lee todo el archivo por un tiempo, se vuelca esto a un archivo auxiliar y luego se lee por el otro tiempo para hacer el promedio, esta solución lee dos veces todos los registros y además usa un archivo auxiliar por lo que se califica con un máximo de 5 puntos.
   No es necesario hacer validaciones de existencia del archivo y cosas por el estilo. No hay descuento por esto.
   Las soluciones que hacen promedio de tiempos y no de posiciones valen 0 puntos (el enunciado es claro y además se aclaró en el parcial).
   
   
2. (2_2006_1P) Primer Cuatrimestre de 2006. Examen parcial, primera oportunidad: 8/5/2006.
   1) Un servidor de chat almacena la información de sus sesiones en un archivo indexado con el siguiente formato de registro (timestamp, usuario, mensaje). (Timestamp en formato cantidad de segundos desde EPOCH, es decir una fecha fijada por el servidor). Se pide construir una función que reciba como parámetros dos fechas y un array a nombres de usuarios y genere un archivo de texto “chat_dump.txt” con la transcripción del chat de dichos usuarios en la fecha indicada. (* * *) (15 pts)
   
   Criterio: Ejercicio 1) La solución mas trivial consiste en crear un índice por fecha y luego al ir procesando filtrar que los usuarios sean los pedidos. Esto tiene como inconveniente que hay que saltear todos los mensajes de todos los usuarios que no interesan y que potencialmente pueden ser muchos, a los que usen este método se le descontaran 3 puntos. Una solución muy buena seria crear un indexado auxiliar y luego usando un índice por usuario-fecha buscar los mensajes de los usuarios pedidos, finalmente recorrer el indexado auxiliar ordenado por fecha para hacer el vuelco final. Si el vuelco del chat no es una transcripción del chat el descuento MÍNIMO es de 10 puntos ya que no hace lo pedido en el enunciado.
   
   
3. Segundo Cuatrimestre de 2006. Examen parcial, segunda oportunidad: 16/11/2006.
   1) Se tiene un archivo indexado con información sobre las ventas de cadena de supermercados. Los registros tienen el siguiente formato: cod_sucursal, fecha, facturación) Se quiere programar una rutina que dadas sucursales imprima un listado ordenado por fecha comparando la facturación de ambas sucursales. Cada linea del archivo de texto tendrá el formato: Suc1 $NNN.NN Suc2 $NNN.NN (Si no hay registros de facturación para de las sucursales para una de las fechas considerar $0. (* * * *) (15 pts)
   
   Criterio: Ej 1: Hay que tener un índice secundario por sucursal-fecha y hacer 2 I_starts, una por cada sucursal, luego simplemente hacer el merge entre los resultados y generar la salida. Soluciones que generen archivos auxiliares y luego hagan el merge entre los dos resultados reciben un descuento de 5 puntos.
   
   
4. Primer Cuatrimestre de 2006. Examen parcial, segunda oportunidad
   1) TSP, empresa dedicada a procesos de alto riesgo cuenta con un sistema de facturación de clientes en el cual los datos del cliente se guardan en un archivo indexado con (código, apellido y nombre, teléfono,#arch) donde #arch es el numero de registro de un archivo relativo donde los registros tiene la estructura (fecha, importe, detalle, #siguiente), donde #siguiente si es >0 indica el siguiente registro del relativo. Se pide programar usando las primitivas correspondientes a las organizaciones mencionadas una rutina que reciba un código de cliente, fecha, importe y detalle y de de alta el pago. (* *) (15 pts)
   
   Criterio: Ej 1) Básicamente hay que acceder al indexado y ver si #arch es cero en cuyo caso se debe buscar un registro libre en el relativo (cualquiera) y guardar los datos allí actualizando el indexado con el numero de registro usado. Si el #arch no es 0 hay que recorrer el relativo hasta encontrar el ultimo elemento de la cadena, luego buscar un registro libre y actualizar el encadenamiento. Errores de lógica descuentan entre 5 y 10 puntos.
   
   
5. Primer Cuatrimestre de 2006. Examen parcial, primera oportunidad: 8/5/2006.
   1) Se tiene un archivo indexado con información sobre los clientes de una empresa (_ _ cod_cliente_ _ , apellido_y_nombre, email, teléfono). Se pide crear un archivo relativo ordenado por apellido_y_nombre a partir del archivo indexado original. (* *) (15 pts)
   
   Criterio: Ejercicio 1) Básicamente hay que crear un índice por apellido_y_nombre, recorrer el archivo usando dicho índice y contar cuantos registros hay guardando los resultados en un secuencial. Luego se crea un relativo del tamaño necesario y se van almacenando los registros que se leen del secuencial. Se descuentan 5 puntos por leer 2 veces el indexado en lugar de crear el secuencial ya que leer 2 veces el indexado es menos eficiente que leerlo una sola vez y luego leer un secuencial. Si crean el relativo sin conocer la cantidad de registros a guardar el ejercicio vale entre 0 y 5 puntos.
   
   
6. Primer Cuatrimestre de 2006. Examen parcial, tercera oportunidad
   1) Dado un archivo relativo con capacidad para N registros se desea implementar acceso directo sobre el mismo usando direccionamiento abierto, lineal y cíclico, en base a lo planteado se pide programar la primitiva D_READ. (* *) (15 pts)
   
   
7. Segundo Cuatrimestre de 2005. Examen parcial, tercera oportunidad
   1) Una empresa decidió hace un tiempo usar un archivo directo para almacenar datos sobre sus clientes, los mismos se identifican por un numero de 6 caracteres, originalmente el archivo directo fue creado para una capacidad de 20.000 clientes pero las cosas no han marchado también como se esperaba y se sabe que la cantidad de clientes reales es mucho menor. A efectos de no desperdiciar tanto espacio se quiere reorganizar el archivo directo de forma tal que la capacidad del mismo sea solamente un 25% mayor a la cantidad de clientes que actualmente tiene la empresa. Sabiendo que para cada cliente se almacena (id, nombre, apellido, dirección1, dirección2, código_postal, teléfono, ciudad, país, notas) se pide programar en lenguaje “C” un programa que realice la reorganización pedida haciendo uso de las primitivas correspondientes a las organizaciones a utilizar. (* * *) (15 pts)
   
   Criterio: Ejercicio 1: Es necesario probar con todas las claves posibles del 0 al 999.999 y verificar si están o no en el archivo directo, contando cuales son las claves que están y además grabando los registros existentes en un auxiliar de forma tal de no tener que probar el millón de claves nuevamente. Una vez que se tiene la cuenta de la cantidad de registros se crea un directo con un 25% mas de espacio y se pasan todos los registros del archivo auxiliar al nuevo directo.
   Si no crean un archivo auxiliar es decir si prueban innecesariamente 2 veces el millón de claves el ejercicio vale como máximo 5 puntos, sin excepciones. Si intentan leer secuencialmente el directo o usan primitivas que no existen vale 0 puntos.
   Si hacen “mas” de lo pedido es decir tratar de mejorar la forma en que se dan de alta las claves o cosas por el estilo no se descuentan ni se agregan puntos ya que esto de ninguna manera era parte del ejercicio.
   Si suponen que las claves van de 0 a 20.000 se descuentan 2 puntos.
   
   
8. Segundo Cuatrimestre de 2005. Examen parcial, segunda oportunidad
   1) Se tiene un archivo indexado con información sobre compras realizadas en una tienda comercial (día, mes, año, tipo_pago, importe, código_producto, cantidad). A su vez se tiene un archivo secuencial con información del stock por producto (cod_producto, cantidad_en_stock) ordenado por cod_producto. Es necesario a partir del archivo indexado actualizar el archivo secuencial para que el mismo refleje el stock actualizado. Programar en lenguaje C utilizando las primitivas correspondientes a cada organización un programa que realice lo pedido. (* *) (15 pts)
   
   Criterio: Ejercicio 1: Se trata de un apareo simple en donde el indexado puede tener varios registros con el mismo código de producto pero el secuencial solo tiene uno. Es necesario crear un índice en el indexado por código de producto y luego hacer el apareo generando un nuevo secuencial. Cualquier intento de “actualizar” el secuencial lo cual es imposible usando las primitivas implica la anulación del ejercicio. Los errores de lógica en el apareo deben considerarse graves ya que lo único que requiere este ejercicio es hacer el apareo correctamente.
   
   
9. Segundo Cuatrimestre de 2005. Examen parcial, primera oportunidad: 17/10/2005.
   1) Una empresa tiene la información de sus clientes en un archivo indexado con la siguiente estructura: (cod_cliente, nombre, apellido, teléfono, dirección, email). Desde hace ya un tiempo que la empresa ha dejado de agregar clientes y solamente realiza consultas al archivo por lo que desea construir a partir del archivo indexado un archivo directo. Se sabe que el archivo directo usara direccionamiento cerrado sin área de overflow independiente. Teniendo en cuenta de que el objetivo de la empresa es realizar consultas rápidas sobre el archivo directo se pide programar en lenguaje “C” un programa que a partir del archivo indexado construya el archivo directo. Tener en cuenta que las características del archivo directo influyen en la forma en que se debe construir el mismo. (* * * * *) (15 pts)
   
   Criterio: Ejercicio 1: Al no tener área de overflow independiente el archivo directo, cuando un alta produce una colisión el registro se almacena en algún registro libre del archivo, al realizar una búsqueda puede entonces ocurrir que el registro apuntado por la función de hashing no sea el buscado ni tampoco sea la cabecera de la lista de sinónimos por lo que no quedara otra opción que buscar secuencialmente en todo el archivo. El objetivo de este programa es evitar o minimizar este problema. Una forma de hacerlo es realizar el alta en 2 pasadas, en la primera ignorando los registros que producirían colisiones. Crear un archivo directo con tamaño algo mayor a la cantidad total de registros también es recomendable.
   A efectos de la corrección las soluciones que lean directamente todos los registros del indexado y los almacenen en el directo sin hacer nada en particular valen 0 puntos ya que en el parcial mismo se dijo que eso estaba mal. Las demás soluciones se evalúan en función de si han detectado correctamente cual es el problema y si lo que plantean sirve para solucionarlo.
   
   
10. Primer Cuatrimestre de 2005. Examen parcial, primera oportunidad: 12/5/2004.
    1) Se tiene un archivo indexado que contiene información sobre libros que se venden en un negocio. (ISBN, titulo,autores, precio, stock). Se quiere pasar la información a un archivo relativo en el cual los libros queden ordenados por título. Se pide un programa eficiente en lenguaje C que realice lo pedido. (* *) (15 pts)
    
    Criterio: Ej 1: Simplemete hay que agregar el índice secundario por título y luego usarlo para generar un archivo secuencial y a la vez determinar la cantidad de registros del archivo. Luego se crea el relativo y se recorre el secuencial para pasar los registros. La opción de realizar dos pasadas al archivo indexado si bien funciona es claramente menos eficiente por lo que tendrá un valor máximo de 10 puntos.
    Opciones que “inventen” la cantidad de registros del archivo o similares valen 0 puntos.
    
    
11. Primer Cuatrimestre de 2004. Examen parcial, primera oportunidad: 10/5/2004.
    1) (15 pts) (* *) Se tiene un archivo indexado con información sobre los productos que vende una determinado cadena de comercios: (_ _ _ código_producto_ _ _, nombre, descripción, precio, stock). A fin de crear una campaña publicitaria se pide crear un archivo relativo que contenga la información de todos los productos cuyo precio este entre dos valores fijos dados y para los cuales el stock sea mayor a una cierta cantidad descartando aquellos productos cuya descripción contiene la palabra “oferta”. A este archivo relativo se lo quiere construir ordenado por precio (de mayor a menor). Utilizando las primitivas correspondientes programar en lenguaje “C” una rutina que cree el archivo relativo a partir del indexado.
    
    Criterio: 1) Se deben usar dos índices secundarios, uno por precio y uno por stock. Se puede suponer que el índice por precio va de mayor a menor en lugar de menor a mayor. Es necesario realizar 2 (dos) pasadas al archivo indexado, ya que en la primera se debe calcular el numero de registros que se guardaran en el archivo relativo mientras que en la segunda pasada se creará el archivo propiamente dicho, en vistas de esto es conveniente almacenar los registros a almacenar en el archivo relativo en un archivo secuencial el cual luego se recorre para crear el relativo, de esta forma se evita hacer dos veces el recorrido del indexado mediante sus índices. Los registros a almacenar surgen de hacer la intersección entre los registros que se obtienen del indexado al usar el índice por precio y el índice por stock.
    Si “supone” una longitud del relativo y no hace dos pasadas se descuentan 5 puntos.
    Mal uso de primitivas al leer del indexado o escribir en el relativo se descuentan 5 puntos.
    Si usan un secuencial como resultado intermedio bonus de 5 puntos si directamente hacen dos veces el recorrido no hay descuento.
    Si para hacer dos veces el recorrido repiten el código dos veces descuento de 5 puntos (error grave de programación). Errores de programación o mal uso del C a criterio de quien corrige hasta un máximo de 10 puntos. Los errores de lógica son mas graves que los errores de sintaxis o manejo de estructuras del lenguaje.
    
    
12. Primer Cuatrimestre de 2004. Examen parcial, segunda oportunidad: 4/11/2004.
    1) Tulio, coleccionista compulsivo de películas desea catalogar su frondosa compilación. A tal efecto nos solicita que ordenemos su catalogo por Genero, Titulo de la película y director. Actualmente cuenta con un archivo secuencial “películas” que cuenta con los siguientes campos por registro: (Titulo, Genero, Director, Año estreno, País Origen). Como pedido especial nos solicita que en el catalogo final no figuren las películas con genero “Adulto”. Se debe implementar el algoritmo Replacement Selection para realizar el sort.
    Teniendo en cuenta que en memoria entran 500 registros de películas y que las particiones de salida deben ser archivos de organización relativa y que se debe contar con toda la información necesaria para que en otro momento se pueda realizar un Optimal merge.(* * *) (15 pts)
    
    Criterio: 1) Se debe implementar un replacement selection correctamente. Uno de los detalles a observar es que como las particiones son archivos relativos se deben generar primero en un secuencial y luego pasarlas a un relativo ya que no se puede saber con anticipación el tamaño de cada partición. Obviar esto conlleva un descuento de 5 puntos. Se permite usar todo tipo de funciones auxiliares para buscar el mínimo, generar los nombres de las particiones etc. Siempre y cuando no hagan al problema en si.
    Dado que el ejercicio es largo los errores de “C” y errores menores de programación no deberían ocasionar descuentos.
    
    
13. Primer Cuatrimestre de 2004. Examen parcial, primer Recuperatorio: 31/5/2004.
    1) TSP, una empresa especializada en rescates de bajo riesgo, almacena información sobre sus operaciones usando un archivo relativo cuyos registros tienen: apellido, nombre, dirección, fecha, código de operación. Este archivo esta ordenado por apellido del cliente. El código de operación es unívoco. Se pide realizar una rutina, eficiente, que indique todos los códigos de operación para un determinado nombre y apellido de un cliente. (* * * *) (15 pts)
    
    Criterio: Ejercicio 1: Hacer una lectura secuencial desde el primer registro hasta encontrar el apellido, no califica como eficiente y anula el ejercicio.
    Mal uso de primitivas: descuento de 5 puntos.
    No utilizar algún método de Búsqueda binaria descuenta 5 puntos.
    No controlar la condición de corte: descuento de 5 puntos.
    Errores de programación: A criterio del ayudante.
    
    
14. Primer Cuatrimestre de 2004. Examen parcial, primera oportunidad: 10/5/2004.
    1) La policía de la provincia del Chaco almacena información sobre detenidos usando un archivo indexado con la siguiente estructura: (_ _ _DNI_ _ _ + nombre + edad + sexo + localidad). La clave primaria de este archivo es el DNI. Se desea programar una rutina buscar_sospechosos (char* localidad, char sexo, int edad_min, int edad_max) que busque a los sospechosos con las características indicadas mostrando un listado de los mismos. Cuando la edad no interesa se usa edad_min=0, edad_max=99. Se pide programar la rutina en lenguaje C utilizando las primitivas correspondientes de la organización indexada. El archivo tiene datos de 23000 personas, la provincia tiene 131 localidades distintas. (15 pts) (* * *)
    
    Criterio: Ejercicio 1: Se debe verificar que existan y/o crear los índices secundarios necesarios para resolver el problema. Al usar la primitiva I_START es fundamental controlar que se siga cumpliendo la condición dentro del ciclo. La solución mas oprima pasa por tener un índice por localidad y otro por edad, cuando la consulta es por localidad+edad se hace una intersección de los resultados, cuando es solo por localidad se usa únicamente el índice por localidad. No hace falta un índice por sexo ya que es dudoso que sea beneficioso.
    Solución óptima: 5 puntos extras.
    Soluciones no-óptimas bien resueltas: puntaje completo.
    Mal uso de primitivas: descuento de 5 puntos.
    No controlar la condición de corte: descuento de 5 puntos.
    No verificar la existencia de los índices secundarios o no crearlos, mal uso de los índices secundarios: 5 puntos.
    Errores de programación: A criterio del ayudante.