CI-1201 Examen #2


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1201
II Semestre 2000

$[\/]$

CI-1201 Programación II

Examen #2 [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] Un palíndromo es una palabra que se lee igual al derecho que al revés.

1.a) [10 pts] Especifique la función bool Palindromo(const Contenedor& C); que regresa true si al recorrer el contenedor "C" hacia adelante se obtiene el mismo resultado que al recorrerlo hacia atrás. Por ejemplo:

Palindromo([1 2 3 2 1]) ==> true
Palindromo([1 2 3 2 0]) ==> false
Palindromo([r a d a r]) ==> true
Palindromo([M A J E M]) ==> false

1.b) [15 pts] Implemente Palindromo(). En su implementación debe utilizar iteradores, de tipo Contenedor::iterador.

1.c) [8 pts] Implemente Palindromo() usando plantillas.

2) [33 pts] En esta pregunta usted trabajará con matrices ralas, o sea, con matrices que tienen una gran cantidad de valores iguales.

2.a) [8 pts] Escriba la declaración de la clase RMatriz que tiene las operaciones básicas para manejar matrices ralas. Use un vector de listas para representar los valores almacenados en cada fila de la matriz rala.

2.b) [5 pts] Especifique el método RMatriz::Traspuesta() que traspone la matriz.

2.c) [20 pts] Implemente el método RMatriz::Traspuesta(). Evite copiar los nodos de las listas que contienen las filas de la matriz.

3) [33 pts] Números binarios enteros de longitud arbitraria.

3.a) [10 pts] Escriba la declaración de la clase Binario que tiene las operaciones aritméticas básicas para manejar números binarios sin signo. Use un vector de longitud arbitraria (pero fija) para almacenar los bits del número binario.

3.b) [5 pts] Especifique opertor+() para la clase Binario.

3.c) [18 pts] Implemente opertor+() para la clase Binario (si lo necesita, cambie el Rep de su clase para que le sea más cómodo escribir su implementación).

4) [33 pts] Manipulación recursiva de árboles.

4.a) [10 pts] Declare la clase Arbol que sirve para almacenar los valores de un árbol n-ario, en que cada nodo puede tener "n" nodos hijos (use un vector de "n" punteros a los nodos hijos).

4.b) [5 pts] Especifique el método Arbol::Homomorfo(), que sirve para determinar si existe un reordenamiento de los nodos del árbol que resulta en el segundo árbol. Por ejemplo, los árboles T1 y T2 son homomorfos:

      T1                           T2
      a                            a
     /|\                          /|\
   / / \ \                      / / \ \
  b  c d  e                    e  d c  b
 /|\     /|\                  /|\     /|\
f g h   i j k                k j i   h g f
         / \                  / \
         l m                  m l

4.c) [18 pts] Implemente Arbol::Homomorfo(). En su implementación, debe usar recursividad.

Soluciones

$[/\]$