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 2008

$[\/]$

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]

/ a - - \       a          /// Imprime en \c std::cout todos los hijos de \c p.
| - b - |      /|\         template <class E>
| - c - |     / | \        void imprimeHijos( const Nodo<E> * p ) {
| - - e |    b  c  d           const Nodo<E> * it;
| - - f |      / \   \         for ( it = p->begin(); it != p->end(); ++it ) {
| - d - |     e   f   g            std::cout << it->val() << std::endl;
\ - - g /                      }
                           }

Suponga que usted cuenta con un API (Application Program Interface) para manipular los nodos de los árboles usando iteradores como se muestra en la rutina imprimeHijos().

1.a) [11 pts] Implemente la rutina "arbolDicc( std::map<E,std::list<E>>& DDD , const Nodo<E> * p )" que almacena en el diccionario "DDD" la lista de hijos para todos los nodos del árbol cuya raíz es "p" (asuma que nunca hay valores duplicados en el árbol).

1.b) [11 pts] Especifique e implemente la función "arbolDim( int & m, int & n, const Nodo<E> * p )" que determina cuantas filas y columnas se requieren para almacenar el árbol de raíz "p" en una matriz chirrisquitica.

1.c) [11 pts] Implemente la rutina "arbolMatriz()" que toma un árbol y lo almacena en una matriz chirrisquitica, de manera que la estructura jerárquica del árbol se mantenga en el contenido de la matriz, como se muestra en el diagrama al principio de este enunciado.

2) [33 pts] Implemente un programa completo que lea de un archivo un conjunto de palabras clave, todas escritas en letras minúsculas. El segundo argumento de su programa es un archivo lleno de renglones en los que usted buscará las palabras mencionadas en el archivo de palabras clave (ignore las diferencias entre minúsculas y mayúsculas). Después de examinar cada renglón, su programa debe imprimir, para cada palabra clave, todos los renglones del segundo archivo en donde esa palabra aparece. Evite leer más de una vez cualquiera de los archivos. Use los contenedores adecuados que le permitan lograr buena eficiencia en tiempo de ejecución.

3) [33 pts] El programa "Nmbag.cpp" sirve para leer números y contar cuántas veces aparece cada uno. Implemente la parte de la clase "Nmbag" que se necesita para que este programa funcione.

int main() { Nmbag B; // la mega-bolsota long n; // lee todos los valores while (cin >> n) { B.Inc(n); } for (n=0; n<LONG_MAX; ++n) { if (0 != B[n]) { cout << n << " está " << B[n]; cout << " veces en la bolsa" << endl; } } return 0; } // main()

3.a) [7 pts] Defina el Rep para la clase. Suponga que nunca ocurrirá que necesite almancenar más de 4096 valores diferentes en su "Nmbag".

3.b) [1 pts] Implemente el constructor y el destructor para la clase.

3.c) [11 pts] Especifique e implemente la operación examinadora "B[n]".

3.d) [14 pts] Especifique e implemente la operación mutadora "B.Inc(n)".

3.e) [0 pts] Mejore la eficiencia de la operación "B[n]" usando búsqueda binaria. Explique por qué esto no mejora la implementación de "B.Inc(n)".

Soluciones

$[/\]$