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 2007

$[\/]$

CI-1201 Programación II

Examen Final [solución]

Duración: Dos horas. 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]

/** Separa los valores de la lista \c "*this" de esta manera:
    - Los valores mayores a \c "pivote" quedan en \c "*this".
    - Los valores menores o iguales a \c "pivote" son
      trasladados a \c "L0".
    - El valor anterior de \c "L0" desaparece.

    \par Nota
    La implementación no copia valores, sino que los traslada
    usando cirugía de punteros.
*/
void lista::Particion( const T& pivote, lista & L0 );

1.a) [0 pts] Dibuje el modelo para la lista circular L=(4,1,3,2) en donde la lista es doblemente enlazada y en el Rep hay un puntero al nodo final de la lista que también representa la posición "end()" de la lista (los datos de ese nodo colero no son considerados valores almacenados en la lista).

1.b) [3 pts] Especifique el método Swap() para nodos que recibe 2 punteros a nodos de la misma lista y los intercambia usando cirugía de punteros.

1.c) [15 pts] Implemente lista::Particion(). En su implementación no use ningún otro método de la lista (tampoco Swap()).

1.d) [15 pts] Implemente el método Swap() para nodos de la lista. En su implementación no use ningún otro método de la lista.

1.e) [0 pts] Implemente lista::QuickSort() con base a lista::Particion().

2) [33 pts] En su libro "Graph Algorithms" (Computer Science Press, ISBN 0-914894-21-8), Shimon Even explica que para definir matemáticamente un árbol es necesario definir primero el concepto de Camino, que es una secuencia de aristas que conectan nodos, en que la arista siguiente en el camino comienza en el nodo en que termina la arista anterior. Un Circuito es un camino en el que el primer y último nodo son el mismo, y un Circuito simple es un circuito en que cada nodo aparece sólo una vez. Se dice que el grafo es Conectado si siempre existe un camino entre cualesquiera 2 nodos del grafo. Con base a estos conceptos son equivalente las siguientes definiciones matemáticas del árbol "T":

"T" es un grafo conectado que no tiene circuitos simples.
"T" no tiene circuitos simples, pero si a "T" se le agrega cualquier arista se forman un circuito.
"T" es un grafo cuyos nodos no están conectados consigo mismos en el que siempre existe un único camino entre cualesquiera 2 nodos.
"T" es un grafo conectado, pero si una arista de "T" es removida el resultado es que "T" queda desconectado.
"T" tiene "n" nodos y no tiene circuitos, y también tiene exactamente "n-1" aristas.
"T" es un grafo conectado de "n" nodos que tiene exactamente "n-1" aristas.

2.a) [6 pts] Suponga que usted cuenta con la clase Graph que usó en la sétima tarea programada. Especifique la función isCircuit() que determina si un camino del grafo G es o no un circuito.

2.b) [5 pts] Especifique la función isTree() que determina si el grafo G es o no un árbol.

2.c) [22 pts] Implemente isTree(). Utilice las operaciones del grafo para determinar si el grafo "G" es o no un árbol. Para eso, constate efectivamente que alguna de las condiciones arriba citadas se cumple. Incluya en su respuesta la implementación de los métodos que use si esos no estaban implementados en la clase Graph. ¡No se le meta al Rep!

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.

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

3.d) [6 pts] La clase "Token" incluye el método booleano "marcado()" 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.e) [11 pts] Escriba un programa que utilice 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.

3.f) [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.

Soluciones

$[/\]$