CI-1201 Examen Final


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1201
I Semestre 2008

$[\/]$

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] Jimmy Neutron ha estado muy ocupado descubriendo los secretos de la CIA, para lo que ha interceptado mucho archivos que contienen renglones. Para pre-procesarlos, necesita encontrar los 2 renglones más largos de cada archivo, y almacenarlos en un archivo de texto. Recuerde que si hay varios renglones de longitud máxima, el programa debe extraerlos todos. Por ejemplo, si ha 3 renglones de 155 letras y 4 de 154 letras, en donde la longitud máxima del renglón es 155, el programa deberá extraer un total de 7 renglones. Implemente el programa completo.

2) [33 pts] Jimmy Neutron descubrió que muchos de textos de los estudiantes de la ECCI contienen comandos maléficos que es necesario censurar. Para eso, construyó un módulo que recibe como entrada un flujo de datos y produce una lista de las palabras que contiene el texto, en donde cada palabra queda asociada con todas las formas en que esa misma palabra aparece escrita, con las mismas letras pero en mayúsculas o minúsculas, con o sin tildes. Por ejemplo, la lista podría contener algo similar a ésto:
(el → [el, El, eL, EL]) , (si → [sí, si, SI] ). // sí tildado

2.a) [3 pts]

+-------------------------------+ | ¿Cómo como? Como como COMO... | | Usted no nada NADA. | | Es que no traje TRAJE. | +-------------------------------+
Muestre el resultado de aplicar su rutina a un archivo que contiene los renglones que aquí se muestran. Use el formato BUnit en su respuesta.

2.b) [10 pts] Declare esta clase de "lista_listas" como una clase derivada de std::list<>. Incluya también la declaración de las otras clases que se necesita para implementar "lista_listas".

2.c) [10 pts] Especifique la función "jalaPalabras()" que sirve para obtener construir las palabras y sus listas. Asegúrese de que la palabra que encabeza a las demás siempre esté escrita en letras minúsculas y sin tildes. Incluya datos de prueba BUnit en su especificación.

2.d) [10 pts] Implemente "jalaPalabras()".

2.e) [0 pts] Implemente "jalaPalabras()" pero use el diccionario std::map<>.

3) [33 pts]

/           \     +--+
| 1 0 4 3 5 |     |  | \
| 1 0 4 3 5 |     |  |  > [ 1 0 4 3 5 ]  
| 1 0 4 3 5 | ==\ |__| /
| 2 2 7 8 1 | ==/ |  | \
| 2 2 7 8 1 |     |  |  > [ 2 2 7 8 1 ]
| 2 2 7 8 1 |     |  | /
\           /     +--+

Suponga que usted necesita almacenar en la clase MatrizRepetidora los valores de una matriz bidimensional de enorme tamaño, en donde ocurre que muchas de las filas están repetidas. Para ahorrar espacio, la idea es almacenar la matriz usando punteros o referencias a las filas comunes.

3.a) [3 pts] Dibuje el modelo de la clase MatrizRepetidora y muestre la relación entre todos los valores almacenados en el Rep.

3.b) [6 pts] Declare la clase RenglonSote que contiene los valores numéricos de una fila de la matriz. Esta es una clase interna, usada para implementar el Rep de la MatrizRepetidora. Declare también 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.c) [5 pts] Especifique la operación quitaDup() que sirve para eliminar todas las filas duplicadas de la MatrizRepetidora sustituyéndolas por un único RenglonSote que es compartido por todas esas filas. Argumente en favor y en contra de que esta operación sea pública o privada.

3.d) [8 pts] Implemente quitaDup(). No olvide que los renglones pueden estar compartidos entre varias filas de la matriz.

3.e) [6 pts] Especifique e implemente la operación swap() que permite intercambiar 2 renglones de la MatrizRepetidora.

3.f) [0 pts] Es bien sabido que una matriz siempre se puede multiplicar por su propia matriz traspuesta. Especifique e implemente el método multiTras() que retorna el valor almacenado en la posición [i,j] de la matriz que resulta de multiplicar la matriz por su propia traspuesta.

3.g) [5 pts] Implemente la función que verifica la invariante para la clase MatrizRepetidora.

3.h) [0 pts] Muestre cómo es posible implementar una matriz rala usando el truco del RenglonSote.

3.i) [0 pts] Escriba de nuevo todas las especificaciones, pero ahora compleméntelas con datos de pueban BUnit.

Soluciones

$[/\]$