CI-1201 Examen #3


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1201
I Semestre 2007

$[\/]$

CI-1201 Programación II

Examen #3 [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] La función "sinalea()" recibe 2 hileras y determina si al reacomodar letras de la primera es posible obtener la segunda. Para hacer esta transformación se usan 2 pilas conectadas una con otra para, de manera que las letras entran a la primera y cuando salen de la primera caen en la segunda. Finalmente, si una letra sale de la segunda es porque sale completamente de la pareja de pilas.

1.a) [3 pts] Declare el Rep para el contenedor "Kush". Incluya un diagrama explicativo.

1.b) [6 pts] Especifique en formato Doxygen las operaciones "push()", "kush()" y "pop()". No olvide incluir ejemplos en sus especificaciones.

1.c) [12 pts] Suponga que ya usted cuenta con la clase "deque" que usó en la tercera tarea programada. Usela para implementar las operaciones "push()", "kush()" y "pop()" de las pilas interconectadas.

1.d) [6 pts] Use las letras U→push() K→kush() y P→pop() para representar las 3 operaciones principales de la clase "Kush". Especifique en formato Doxygen el método ""ejecute()" que usa una hilera compuesta de estas 3 letras para obtener el resultado de aplicar las operaciones a su argumento principal.

1.e) [6 pts] Use la clase "Kush"como base para implementar la función booleana "palindromo()" que determina si una hilera se lee igual de adelante hacia atrás que de atrás hacia adelante (ignore los espacios en blanco).

1.f) [0 pts] Muestre 1 pareja de hileras compuestas de exactamente las mismas letras para las que "sinalea()" retornaría "false".

2) [33 pts] La clase Fecha permite almacenar el día, mes y año de una fecha.

2.a) [5 pts] Especifique "esBisiesto()". Recuerde que todos los años bisiestos son divisible por 4, pero los únicos múltiplos de 100 que son bisiestos también son múltiplos de 400.

2.b) [6 pts] Implemente "esBisiesto()".

2.c) [5 pts] Cuando se restan 2 fechas el resultado es el número de días entre las 2 fechas. Especifique el método "diferencia()".

2.d) [6 pts] Implemente "diferencia()". Recuerde usar "esBisiesto()" en su implementación.

2.e) [11 pts] Implemente el constructor "Fecha(int)" que determina la cantidad de años meses y días a partir de un número entero.

3) [33 pts] Una pareja de árboles binarios son homomorfos si tienen la misma raíz y si, recursivamente hablando, ambos subárboles son homomorfos a uno de los hijos del otro árbol (aunque no se vale que dos hijos sean homomorfos al mismo hijo del otro árbol). En otras palabras, cuando 2 árboles son homomorfos existe un reordenamiento de los hijos del primer árbol que resulta en el segundo árbol.

3.a) [9 pts] Escriba en formato Doxygen la especificación de la rutina "homomorfo()". Incluya varios ejemplos de árboles que son y no son homomorfos.

3.b) [24 pts] Implemente "homomorfo()". Debe usar recursividad. Recuerde: ¡No se le meta al Rep del árbol binario!

3.c) [0 pts] Use la función "Mirror()" para implementar "homomorfo()".

Soluciones

$[/\]$