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 2001

$[\/]$

CI-1201 Programación II

Examen Final [solución]

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

1) [33 pts] Considere la clase Arbol, en que cada nodo tiene un vector que apunta a sus hijos:

class Arbol {
    class nodo {
        nodo *h[33];  // hasta 33 punteros a los hijos 
        long _val;    // valor almacenado en el nodo
    }; // nodo
    friend bool Es_Binario(const Arbol & T);
    nodo * _raiz;
}; // Arbol

1.a) [0 pts] Dibuje el modelo (diagrama) que corresponde a la clase Arbol.

1.b) [11 pts] Especifique la función Es_Binario() que sirve para determinar si cada nodo tiene un máximo de dos hijos.

1.c) [11 pts] Defina la invariante para la clase Arbol.

1.d) [11 pts] Implemente Es_Binario().

2) [33 pts] Considere la clase lista que usted ya ha usado y suponga, además, que la lista cuenta con el iterador lista::iter que sirve para recorrerla desde principio a fin.

2.a) [5 pts] Declare el iterador lista::ordenado que sirve para obtener los elementos almacenados en la lista en orden de menor a mayor.

2.b) [28 pts] Implemente las operaciones de su iterador lista::ordenado usando como base el iterador lista::iter. Su iterador debe hacer un muy eficiente uso de la MEMORIA, aunque sea muy lerdo; por eso, en su implementación no use listas ni vectores, ni cualquier tipo de contenedor. Explique cómo funciona su implementación.

3) [33 pts] Considere la clase lista que cuenta con las operaciones lista::intercambie(i), lista::pop() y lista::push(v). La primera intercambia los valores que es encuentran en la posición "*i" y "*(++i)" de la lista, la segunda remueve de la lista el primer valor y luego lo retorna y la tercera agrega un valor al principio de la lista.

3.a) [3 pts] Especifique lista::intercambie(i). Recuerde usar siempre el formato Doxygen e incluir los datos de prueba BUnit.

3.b) [3 pts] Especifique lista::push(v) y lista::pop().

3.c) [7 pts] Especifique Particion() que separa una lista en dos listas, de manera que los valores que quedan en la primera lista son mayores que el parámetro "pivote" de Particion(), y los de la segunda son los demás valores almacenados en la lista original.

3.d) [20 pts] Implemente Particion(). Como esta función no es amiga (friend) de la clase lista, al escribir su implementación use la operaciones lista::push(v) y lista::pop() y alguna de lista::intercambie(i) o lista::isEmpty().

4) [33 pts] Usted trabaja con un programa que lee un archivo de texto que contiene parejas de nombres, en la forma "padre hijo", y almacene la relación (Hijo, Padre). En la implementación, se usan los diccionarios (map<>) de la biblioteca STL de C++.

4.a) [0 pts] Haga las declaraciones de los diccionarios usados en su programa.

4.b) [18 pts] Escriba un bloque de código para que su programa lea un nombre y liste los ancestros que corresponden a ese nombre (padre, abuelo, bisabuelo, tatarabuleo, etc.).

4.c) [15 pts] Escriba un bloque de código para que su programa lea un nombre y liste los descendientes que corresponden a ese nombre (hijo, nieto, bisnieto, tataranieto, etc.).

5) [33 pts] La función Rotacion(L,n) para la clase Lista es una función amiga que sirve para rotar circularmente sus valores alrededor del n-ésimo valor:

(a b c d e f) ==> (a b c d e f)  (0)  (6)
                  (b c d e f a)  (1)  (7)
                  (c d e f a b)  (2)  (8)
                  (d e f a b c)  (3)  (9)
                  (e f a b c d)  (4)
                  (f a b c d e)  (5)

5.0) [0 pts] Dibuje el modelo de la lista que usará en su implementación.

5.b) [11 pts] Especifique Rotacion(L,n) (no se limite a copiar el enunciado de esta pregunta).

5.c) [22 pts] Implemente Rotacion(L,n). No copie los valores de la lista; únicamente cambie los puntero de los nodos la lista. Puede usar una lista simple o doblemente enlazada.

Soluciones

$[/\]$