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 2000

$[\/]$

CI-1201 Programación II

Examen Final [solución]

1) [25 pts]

 L->last ───────────────────────────────────────┐
                                                │
┌────────────┐   ┌────────────┐   ┌───────────┐ │
│            v   │            v   │           v v
│ ┌────────┬───┐ │ ┌────────┬───┐ │ ┌────────┬───┐
│ │ elem_1 │ ├─┼─┘ │ elem_2 │ ├─┼─┘ │ elem_3 │ ├─┼─┐
│ └────────┴───┘   └────────┴───┘   └────────┴───┘ │
│            ^               next              ^   │
│            │                                 │   │
│          first                             last  v
└───────<───────────────<────────────────<─────────┘

clist
La clase clist es una lista circular, en que el último nodo apunta al primero. A diferencia de una lista tradicional, en que en el Rep hay un puntero al primer nodo, en una lista circular el puntero del Rep apunta al último nodo, de manera que se pueden hacer inserciones eficientemente tanto al principio como al final de la lista.

1.a) [5 pts] Haga la declaración mínima de la clase clista.

1.b) [20 pts] Implemente el método clist::Reverse() que Invierte los valores la lista de forma que sus últimos elementos pasen a ser los primeros. En su implementación no copie valores ni nodos; hágalo todo cambiando punteros.

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

2.a) [5 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) [15 pts] Implemente el método RMatriz::Traspuesta(). Evite copiar los nodos de las listas que contienen las filas de la matriz.

3) [25 pts] Escriba un programa que lea un archivo de texto que contenga parejas de nombres, en la forma "hijo padre", y que luego liste para cada padre a todos sus hijos. En su implementación, use los diccionarios (map<>) de la biblioteca STL de C++.

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

4.a) [3 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) [4 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

$[/\]$