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 2011

$[\/]$

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] Un árbol es un caso específico del grafo pues cada grafo contiene nodos y vértices que están conectados mediante aristas. En un árbol siempre existe un único camino entre cualesquiera 2 nodos, pero en un grafo puede haber más de uno, y también puede ocurrir que el grafo tenga partes desconectadas.

1.a) [4 pts] Discuta la abstracción para esta implementación y compárela con la que ha usado durante el curso.

1.b) [7 pts] Use una matriz cuadrada para representar los enlaces entre los nodos del grafo. Explique cómo proceder si el valor almacenado en el nodo no es un número entero, sino que es otro tipo de objeto. Declare la clase grafo junto con sus operaciones e incluya el Rep.

1.c) [6 pts] Especifique las operaciones que permiten pasar de un nodo a otro en el grafo. Implemente solo una de ellas.

1.d) [4 pts] Especifique un iterador que sirva para visitar una vez cada uno de los nodos del grafo conectados con el nodo de inicio. ¡No se le meta al Rep!

1.e) [12 pts] Implemente su iterador. ¡No se le meta al Rep!

2) [33 pts] Especifique e implemente un iterador que recorre el perímetro de cualquier sección rectangular definida dentro de una matriz. Por ejemplo, debe servir para recorrer la parte marcadas con 8's de estas matrices de caracteres (sin pasar por ninguno de los '.'). Incluya datos de prueba BUnit.h. Suponga que la matriz incluye una sobrecarga de operator()(i,j).

. . . . . . .
. . 8 8 8 8 8    8 8 8 8 8 8 .
. . 8 . . . 8    8 8 8 8 8 8 .    . . . 8 8 8 .
. . 8 . . . 8    . . . . . . .
. . 8 8 8 8 8

3) [33 pts] En un conjunto se pueden almacenar valores con la ventaja de que luego es posible constatar si el conjunto contiene o no contiene un valor específico. Además, el conjunto también tiene varias operaciones muy usadas en matemática.

3.a) [2 pts] Dibuje el modelo (diagrama) para la clase Set si en el Rep se usa una implementación de listas.

3.b) [3 pts] En el caso de una pila, las operaciones que le caracterizan son Push() y Pop(). Explique cuáles son las operaciones que caracterizan a la clase Set.

3.c) [5 pts] Escriba las declaraciones C++ para la clase Set. Incluya el 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) [10 pts] Sobrecargue el operador "*" e implemente la intersección de conjuntos.

3.e) [7 pts] Implemente en C++ la operación que sirve para cargar los valores de Set.

3.f) [6 pts] Implemente los constructores y destructores para la clase Set.

Soluciones

$[/\]$