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 2012

$[\/]$

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 las tres preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] Además de las 2 operaciones que caracterizan a cualquier iterador Java, es cómodo contar con otra para recorrer una matriz rectangular de varias maneras:

         O                  o                  /                  \
+----------------+ +----------------+ +----------------+ +----------------+
| 01 02 03 04 05 | | 01 16 15 14 13 | |             05 | | 01             |
| 16          06 | | 02          12 | |          04    | |    02          |
| 15          07 | | 03          11 | |       03       | |       03       |
| 14          08 | | 04          10 | |    02          | |          04    |
| 13 12 11 10 09 | | 05 06 07 08 09 | | 01             | |             05 |
+----------------+ +----------------+ +----------------+ +----------------+

1.a) [15 pts] Implemente un programa de ejemplo en que usa su iterador para recorrer una matriz de enteros y otra matriz que contiene hileras de menos de 3 letras.

1.b) [18 pts] Escriba la implementación completa de su iterador en el archivo de encabezado itrMatrix.h. Use plantillas y ejemplos BUnit.

2) [33 pts] Un polinomio se puede implementar usando un vector de números reales que contiene, en su entrada "i", el coeficiente del i-ésimo término del polinomio. El campo "m_grad" del Rep indica el grado del polinomio. Los términos superiores a "m_grad" no están inicializados en cero. El polinomio cero se representa con un cero en el coeficiente y con el grado() = 0. Por ejemplo, el polinomio x^3 + 2x^2 se ve así:

  polinomio               grado
   2x^2 + x^3               3

    0   1   2   3   4   5   6   7   8   9  ....
  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 0 | 0 |2.0|1.0| $ | ! | % | % | % | ( | = |   |   |   |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
                ^
                |
                +------------- grado() == 3

2.a) [6 pts] Haga la declaración de las clases poli_VEC y poli_DEQUE usando dos tipos diferentes de vector en el Rep: un vector y la clase std::deque<> de la biblioteca STL de C++. Escriba declaraciones resumidas, incluyendo apenas lo suficiente.

2.b) [6 pts] Especifique el método fromString() que toma una hilera de la forma "x^3 + 2x^2" y produce un polinomio. Luego especifique el operador suma para polinomios. Recuerde incluir suficientes ejemplos BUnit.

2.c) [16 pts] Implemente el operador suma para polinomios. Su implementación debe estar hecha de manera que sirva para cualquiera de las dos escogencias del Rep (tenga cuidado cuando el resultado es cero).

2.d) [5 pts] Explique por qué su implementación del operador suma es independiente del Rep de su clase poli.

2.e) [0 pts] Explique cómo declarar la clase poli de manera que quien la use pueda escoger si usar un vector o un deque para los coeficientes del polinomio. Además, indique cómo generalizar esta solución para usar en la implementación el diccionario std::map<> de la biblioteca estándar.

3) [33 pts] La función booleana obtieneMasa() retorna "false" cuando termina de proveer datos (los que obtiene leyéndolos de archivos o de la red). De otra forma, retorna "true" y un contenedor "Masa" lleno de valores de tipo "Token". En cada invocación, obtieneMasa() retorna un contenedor "Masa" completo.

3.a) [0 pts] Haga un diagrama que muestre cómo están organizadas las clases "Masa" y "Token".

3.b) [5 pts] Especifique la función obtieneMasa(). El contenedor "Masa" debe estar diseñado de manera que pueda ser recorrido con iteradores, de manera similar a como se recorren los contenedores de la biblioteca estándar. Recuerde incluir suficientes ejemplos BUnit.

3.c) [3 pts] Escriba la declaración de las clase "Masa". Incluya los métodos que usa en las implementaciones. Recuerde: ¡No se le meta al Rep!

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.d) [3 pts] Escriba la declaración de la clase "Token". Incluya los métodos que usa en las implementaciones. Recuerde: ¡No se le meta al Rep!

3.e) [6 pts] La clase "Token" incluye el método booleano "estaMarcado()" que retorna "true" para los tokens que están marcados. Implemente una función que recorra el contenedor "Masa" y almacene sus tokens marcados en una lista.

3.f) [11 pts] Escriba un programa que utilice "obtienMasa()" y un contenedor std::map<> para almacenar en él todos los contenedores "Masa" que corresponden a cada uno de los tokens marcados, de manera que cada token marcado sirva como llave para obtener la lista de contenedores "Masa" en los que aparece ese token (si un contenedor "Masa" contiene varios tokens marcados, ese contenedor "Masa" deberá aparecer en varias listas). Suponga que es posible copiar objetos de tipo "Masa" y de tipo "Token" usando sus respectivos métodos de copia (recuerde: pierde el 33% de los puntos si no usa std::map<>).

3.g) [5 pts] Suponga que tanto la clase "Token" como "Masa" ya tiene definido el operator<<() para grabar el valor del token en un flujo de salida. Modifique el programa que escribió en el punto anterior para que también imprima, para cada token, todas las "masas" en que aparece.

3.h) [0 pts] Use "Masa" y "Token" para escribir un programa similar al definido para spamTico.com.

Soluciones

$[/\]$