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 2009

$[\/]$

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] El Partido Estatal Democrático Organizado ha iniciado una campaña anti-corrupción para evitar que los familiares estén en las Juntas Directiva de las instituciones públicas. Para implementarlo es necesario contar con un programa de computadora que permita determinar si 2 personas son hermanos, hijos, primos o tíos.

1.a) [6 pts] Declare la clase "Viejillo" que tiene los datos de cada persona. No se le olvide incluir el número de cédula. Use punteros para registrar quién es el padre y la madre de cada viejillo.

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) )

1.b) [0 pts] Discuta si esta red familiar es o no un contenedor.

1.c) [5 pts] Las Juntas Directivas están compuestas de varios viejillos quienes no deben ser familiares. Declare el Rep para la clase "Junta_Directiva".

1.d) [5 pts] Especifique y e implemente el método "Agregar()" que sirve para agregarle otro viejillo a una Junta Directiva. Levante la excepción "CHORICERO" si se violenta la invariante de la clase.

1.e) [6 pts] Especifique e implemente el "check_ok()" para la clase "Junta_Directiva". No olvide definir la invariante de la clase.

1.f) [11 pts] Especifique e implemente el método "Es_Familia()" que sirve para saber si 2 viejillos pueden o no estar en la misma Junta Directiva. No olvide reportar qué tipo de familiaridad tienen.

1.g) [0 pts] Diga por cuánta plata implementaría usted un programa que lea el "padrón nacional" y determine cuáles son los choriceros que están nombrados ahora en las instituciones autónomas.

2) [33 pts]

           L
           |
           v
     +-------------+   +-------------+   +-------------+   +-------------+
     |   |     | *-+-->|   |     | *-+-->|   |     | *-+-->|   |     | *-+-> NIL
     |   | 2.2 |   |   |   | 4.5 |   |   |   | 2.2 |   |   |   | 1.3 |   |
NIL<-+-* |     |   |<--+-* |     |   |<--+-* |     |   |<--+-* |     |   |
     +-------------+   +-------------+   +-------------+   +-------------+

2.a) [0 pts] Escriba la declaración de las clases Arbol y Lista, que tienen la característica que usan el mismo tipo de nodo.

2.b) [7 pts] Especifique la función Arboleador() que toma una lista, similar a la de la figura de arriba, y la convierta en un árbol binario ordenado el que, al ser recorrido en inorden, tiene en orden creciente los nodos, aún si hay duplicados. Incluya un ejemplo de qué hace esta función. Si lo desea, puede basarse en la especificación genérica para la operación Move().

2.c) [26 pts] Implemente la función Arboleador(), pero evite copiar nodos en su implementación. Además, debe usar recursividad. Use los campos "m_izq" y "m_der" del nodo de la lista para crear el árbol, sin usar nuevos nodos. Como documentación interna, explique cómo funciona su implementación.

3) [33 pts] En esta pregunta usted trabajará con matrices ralas, o sea, con matrices que tienen una gran cantidad de valores iguales.

3.a) [8 pts] Escriba la declaración de la clase RMatriz que tiene las operaciones básicas para manejar matrices ralas. Use un vector de listas para representar los valores almacenados en cada fila de la matriz rala. Como valores almacenados en la lista puede usar elementos de la clase emplantillada "Trio<int,int,T>".

3.b) [5 pts] Especifique el método RMatriz::Traspuesta() que traspone la matriz.

3.c) [20 pts] Implemente el método RMatriz::Traspuesta(). Evite copiar los nodos de las listas que contienen las filas de la matriz.

Soluciones

$[/\]$