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 2001

$[\/]$

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

1) [33 pts] El CASI_Barbol<T> es la plantilla de un árbol cuyos nodos tienen un máximo de 2 * CASI_Barbol<T>::N hijos. Si la raíz del árbol tiene hijos, debe tener como mínimo dos hijos. Si el nodo no es un nodo hoja, también debe tener un mínimo de CASI_Barbol<T>::N nodos hijos. Además, los hijos de cada nodo deben estar ordenados ascendentemente.

1.a) [5 pts] Dibuje el modelo (diagrama) que corresponde a la clase CASI_Barbol<T>. Explique cómo está hecho su árbol.

1.b) [6 pts] Declare la clase CASI_Barbol<T>. Debe usar clases anidadas.

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.c) [7 pts] Defina la invariante para la clase CASI_Barbol<T>.

1.d) [15 pts] Especifique e implemente el método CASI_Barbol<T>::OK() que retorna true si la instancia del árbol cumple con su invariante. Suponga que la clase "T" almacenada en el árbol cuenta con la operación T::OK().

1.e) [0 pts] Explique cómo se puede recorrer el CASI_Barbol<T>::OK() para determinar si un valor se encuentra o no almacenado en el árbol.

2) [33 pts] Haga un programa C++ que lea un archivo y cuente, para cada letra del alfabeto, la cantidad de letras mayúsculas, minúsculas y números e imprima los totales, para cada una de las letras del alfabeto y cada uno de los dígitos decimales. Recuerde que, en Costa Rica, la pareja "CH" es una letra, y que también el alfabeto incluye a la letra "Ñ". En su implementación no use "multiset<>": use un contenedor que le permita no repetir cada una de las letras.

3) [33 pts] Un grafo G = (V, A) tiene dos partes: "V" es un conjunto de vértices o nodos y "A" contiene arcos. Es usual que los arcos o aristas tengan un valor numérico asociado.

3.a) [0 pts] Dibuje un grafo de 10 nodos y bastantes vértices. Llame a uno de ellos "COMIENZO" y a otro "DESTINO". Para los demás vértices puede usar nombres propios de personas. No hace falta que desde cualquier nodo se pueda llegar a otro saltando por los arcos.

3.b) [6 pts] Declare la clase Grafo. Use en el Rep la clase diccionario ("map<>") de la biblioteca STL para representar los arcos. Además, permita que cada arco tenga un valor asociado, de tipo numérico. Use clases anidadas en el Rep.

3.c) [6 pts] Especifique el método Grafo::Conectado() que sirve para determinar si se puede llegar de un nodo a otro, en caso de de que exista un camino que conecta a los nodos (no puede haber nodos repetidos). Para eso, como argumento su método puede recibir un conjunto, de tipo ("set<>"), que tiene todos los nodos que ya fueron visitados; para calcular la ruta entre dos nodos, en caso de que exista, habría que invocar Grafo::Conectado() con un conjunto vacío.

3.d) [14 pts] Implemente el método Grafo::Conectado(). Use recursividad.

3.e) [7 pts] Implemente la función Graba_Camino() que recibe estos parámetros:

ostream & OUT; // flujo en donde grabar
const STRING & desde;
const STRING & hasta;
const set<> & CAMINO;

Esta función sirve para grabar en "OUT" la lista de nodos que llevan desde el nodo "desde" hasta el nodo "hasta" pasando por nodos del conjunto "CAMINO". Junto a cada nodo grabe también el peso del arco, y al final grabe el peso total acumulado, que representa el costo del camino. Recuerde que el conjunto CAMINO está en orden alfabético, no en el orden en que debe grabar el camino.

Soluciones

$[/\]$