CI-1201 Examen #3


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1201
II Semestre 2006

$[\/]$

CI-1201 Programación II

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

1) [33 pts] La función Brincolina(L,n) para la clase Lista es una función amiga que sirve para invertir el orden de varias sublistas de tamaño "n" en una lista:

(a b   c d   e f) ==> (b a   d c   f e)   (2)
(a b c     d e f) ==> (c b a     f e d)   (3)
(a b c d     e f) ==> (d c b a     f e)   (4)

(a b c d e f)   ==> (a b c d e f)     (1)

1.a) [5 pts] Dibuje el modelo de la lista que usará en su implementación.

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

1.c) [23 pts] Implemente Brincolina(L,n). No copie los valores de la lista; únicamente cambie los punteros de los nodos la lista. Puede usar una lista simple o doblemente enlazada.

2) [33 pts] Las listas permiten trasladar grupos de los valores que contienen sin copiarlos, usando cirugía de punteros.

2.a) [6 pts] Especifique en formato "Doxygen" la función Splice() para la lista, que sirve para trasladar valores de una lista a otra usando cirugía de punteros.

2.b) [5 pts] Especifique en formato "Doxygen" la operación L.Merge(LL) que funciona intercalando en orden los valores de "L" y "LL" cuando ambas listas están ordenadas.

2.c) [22 pts] Implemente L.Merge(LL). Utilice su Splice() para evitar accesar el Rep de la lista. Puede usar los métodos de la lista pero evite copiar cualquiera de los valores que la lista contiene. Debe implementar el algoritmo de intercalación.

2.d) [0 pts] Especifique el método list::size() que retorna la cantidad de valores almacenados en la lista.

3) [33 pts] En un conjunto se pueden almacenar valores con la ventaja de que luego es posible constatar si el conjunto contiene o no contiene un valor específico. Además, el conjunto también tiene varias operaciones muy usadas en matemática.

3.a) [2 pts] Dibuje el modelo (diagrama) para la clase Set si en el Rep se usa una implementación de vectores ordenados.

3.b) [3 pts] En el caso de una pila, las operaciones que le caracterizan son Push() y Pop(). Explique cuáles son las operaciones que caracterizan a la clase Set.

3.c) [5 pts] Escriba las declaraciones C++ para la clase Set. Incluya el Rep.

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

3.d) [10 pts] Sobrecargue el operador "*" e implemente la intersección de conjuntos.

3.e) [7 pts] Implemente en C++ la operación que sirve para cargar los valores de Set.

3.f) [6 pts] Implemente los constructores y destructores para la clase Set.

4) [33 pts] En 1878 Samuel Loyd inventó el "Juego de los Quince" que se juega en una matriz 4x4 moviendo piezas a la casilla vacía hasta que queden ordenadas. Un ejemplo del comienzo y fin del juego es el siguiente:

15	2	3	4
5	6	7	8
9	10	11	12
13	14	1

→

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15

4.a) [0 pts] Dibuje el modelo para la clase "J15" que sirve para almacenar de una forma eficiente los números del Juego de los Quince. Indique si vale la pena usar un enum para los valores { up down left right }.

4.b) [5 pts] Defina la abstracción y explique cuáles operaciones son importantes para esta clase.

4.c) [20 pts] Escriba el archivo de encabezado con la especificación en formato "Doxygen" para la clase "J15". Incluya el Rep y los datos de prueba BUnit.h para la clase.

4.d) [8 pts] Use una lista en donde almacene valores de tipo "J15" para representar los movimientos del juego. Especifique e implemente una rutina que comience en una configuración del juego y genere la lista de los movimientos que resuelven el juego. Su algoritmo no tiene que ser eficiente. Puede usar una estrategia de prueba y error para obtener la solución del juego, por lo que es válido escribir y borrar de la lista configuraciones de juego de prueba. Recuerde que en algunos casos el juego no tiene solución. No se le meta al Rep de "J15".

4.e) [0 pts] Explique si es mejor usar las rutinas str2list.h para hacer los ejemplos de prueba de los métodos del juego "J15" o si más bien es mejor usar inicializaciones de matrices (pues ambas requieren de un método para cargar los valores a partir de una matriz cuadrada).

Soluciones

$[/\]$