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 (Reposición) [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 *m_ptr[33];  ///< hasta 33 punteros a los hijos 
        long m_val;    ///< valor almacenado en el nodo
    }; // nodo
    friend bool Es_Binario(const Arbol & T);
    nodo * m_raiz;  ///< Puntero a la raíz de árbol
}; // 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 con palabras la invariante para la clase Arbol. Impleméntela.

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

2) [33 pts] Considere la clase lista que cuenta con las operaciones públicas 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.

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

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

2.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.

2.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().

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

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

3.b) [11 pts] Especifique rotacion(L,n) (no se limite copiar el enunciado de esta pregunta). Incluya los datos de prueba BUnit.

3.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

$[/\]$