CI-1201 Examen Final


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1201
II Semestre 2010

$[\/]$

CI-1201 Programación II

Examen Final [solución]

Duración: Ciento veinte minutos. Lea bien el examen antes de hacerlo. El examen es a libro abierto. Cuenta la documentación. Cuenta la redacción y la ortografía. Puede hacer el examen con lápiz. Resuelva todas las preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] A diferencia de las listas del lenguaje lisp, las listas C++ no permiten obtener fácilmente una sublista, pues están definidas como secuencias de valores y no como una cabeza que viene seguida de una cola que también es una lista. La ventaja de las listas C++ es que sí tienen iteradores que permiten marcar pedazos de cualquiera de los contenedores construidos de acuerdo a los lineamientos de la biblioteca estándar, pues se pueden usar 2 iteradores para definir el rango que cubre una sublista.

1.a) [11 pts] Defina el Rep para la clase subrange que permite definir un rango de valores para cualquier contenedor C++, especialmente para los de la biblioteca STL. Incluya la implementación de la función que verifica la invariante de la clase.

1.b) [11 pts] Escriba la parte de la especificación de la clase subrange en los que muestre los inconvenientes que hay que enfrentar cuando se usan contenedores mutables. Incluya datos de prueba BUnit en el formato Doxygen.

1.c) [11 pts] Implemente sendas funciones que permitan usar su clase subrange para ordenar una secuencia y para eliminarle algún valor. Use los algoritmos STL en su implementación.

2) [33 pts] Escriba un programa completo que lea un archivo y extraiga todas las direcciones internet que contenga. Usted puede identificar de 2 formas estas direcciones:

http://ecci.ucr.ac.cr: La hilera comienza con "http://".
www.ucr.ac.cr: La hilera incluye "www.".

Recuerde que no todos los caracteres son válidos en una dirección internet. Su programa debe ser "inteligente", pues debe agregarle el encabezado "http://" a las hileras que no lo contengan. Además, no debe grabar hileras duplicadas y evitar casos límite como "EsteWWW.no.se.vale". Grabe en la salida estándar las hileras encontradas. Permita extraer direcciones aún de archivos que no son de texto, como ocurre con los archivos que contienen programas ejecutables. En su implementación, incluya datos de prueba BUnit en el formato Doxygen.

3) [33 pts] La clase fastFlap es una implementación de una matriz que es muy rápida para intercambiar filas y columnas. Las 2 operaciones importantes de la clase son flip() y flop() que sirven para hacer los intercambios.

/// ¿Mleft == Mrigth? Compara 2 matrices por igualdad. template <class Mleft , class Mrigth > bool operator==( const Mleft mL , const Mrigth mR ) { if ( mL.NFILS() != mR.NFILS() ) { return false; } if ( mL.NCOLS() != mR.NCOLS() ) { return false; } for ( int i=0; i<mL.NFILS(); ++i ) { for ( int j=0; j<mL.NCOLS(); ++j ) { if ( mL.get(i,j) != mR.get(i,j) ) { return false; } } } return true; }

3.a) [11 pts] Declare la clase fastFlap junto con sus métodos principales. La matriz mantiene sus valores almacenados en la memoria dinámica y en el Rep se usa el truco de los vectores indirectos para que los operaciones de intercambio se puedan implementar sin copiar los valores de la matriz.

Recuerde que la diferencia entre "definir" y "declarar" un objeto en C++ es que las declaraciones se ponen en los archivos de encabezados <*.h> y <*.hpp>, mientras que las definiciones están en los archivos de implementación <*.c> y <*.cpp>.

Las declaraciones corresponden a la especificación.
Las definiciones corresponden a la implementación. Para facilitarle memorizar este hecho, asocie la palabra "definición" con la directiva #define que sirve para implementar macros en C++:
#define max(a,b) ( (a)>(b) ? (a) : (b) )

3.b) [11 pts] Haga un programa BUnit que utilice el operador de comparación == para cotejar el resultado de usar una matriz tradicional slowFlap en lugar de la matriz rápida fastFlap. Su programa debe intercambiar todas las filas y todas las columnas de una matriz rectangular de tamaño NxM, en donde siempre ocurre que M==2xN y N es alguno de los número { 1, 2, 25, 100, 1000, 1024 }.

3.c) [11 pts] Implemente el constructor fastFlap(n,m) que deja la matriz inicializada en ceros. También implemente la operación flip() para la matriz acelerada fastFlap y para una matriz tradicional slowFlap.

3.d) [0 pts] Determine la cantidad de asignaciones que se necesita realizar en una matriz fastFlap y compárelo con la cantidad de asignaciones necesarias en una matriz tradicional slowFlap. Concluya cuál es la diferencia de velocidad de ambas implementaciones.

Soluciones

$[/\]$