Examen #1 [solución]

      Duración: tres 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. ¡No haga más de lo que se le pide! ¡Conteste todas las preguntas!

1) [25 pts] Para implementar el ADT conjunto, suponga usted que ha usado la clase C++ ListC que usted creó en la Tarea #1 usando como base el módulo escrito en lenguaje C clist.h, descrita en el artículo:

Di Mare, Adolfo

C Parametrized Lists, Reporte Técnico ECCI-98-01, Escuela de Ciencias de la Computación e Informática, Universidad de Costa Rica, Abril, 1999.
      http://www.di-mare.com/adolfo/p/c-list.htm

      Además, asuma que el ligador que ha usado (al invocar las operaciones definidas en binder.h) incluye las dos operaciones EQUAL() y LESS(), que se usan para almacenar los valores en el conjunto en orden ascendente y también para determinar si dos valores almacenados en el conjunto son iguales, en la implementación de la operación:
      bool Conjunto::Member(sk & Conjunto::sl_link, const binder *BINDER);

1.a) [5 pts] Declare la clase Conjunto. Incluya las operaciones más importantes y los campos que forman el Rep. Suponga que los valores del conjunto se almacenan ordenados.

1.b) [5 pts] Especifique la operación UNION(otro) que al valor actual de *this le agrega al otro conjunto (pero sin vaciarlo).

1.c) [15 pts] Implemente Conjunto::UNION().

                               M2[6 x 4] [Sup:0]
M1[4 X 7] [Inf:0]                    1 2 3 4
   1 . . . . . .                     . 5 6 7
   2 3 . . . . .                     . . 8 9
   4 5 6 . . . .                     . . . 0
   7 8 9 0 . . .                     . . . .
                                     . . . .

      La matriz M1 es una matriz triangular inferior [4 x 7], y todos los valores que aparecen sobre la diagonal son 0 (cero). La matriz M2 es una matriz triangular superior [6 x 4], y bajo la diagonal hay 14 ceros. Asuma que los valores de la matriz son de tipo float.

2.a) [5 pts] Escriba la definición de tipos para el objeto MatrizTrng, que sirve para implementar matrices triangulares. Incluya todos los tipos auxiliares que necesite. Defina también los métodos que necesite. No almacene en el vector los valores cero que aparecen repetidos bajo (o sobre) la diagonal.

      Suponga que usted usará un vector unidimensional "_val" con índices en el rango [0..MatrizTrng::MxDim-1], para almacenar los valores de la matriz. Almacene los valores de la matriz AL FINAL del vector, y no al principio. Incluya diagramas en su respuesta.

2.b) [10 pts] Derive una fórmula que sirva para transformar dos índices (i,j) en la posición dentro del vector "_val" en que está almacenado el valor M[i,j]. Recuerde que los valores quedan almacenados desde la parte de atrás del vector hacia adelante. Defina las restricciones que necesite sobre los valores (i,j). Tome en cuenta que los valores de la matriz están almacenados AL FINAL del vector, y no al principio.

2.c) [10 pts] Use la fórmula que usted derivó en el punto anterior para implementar el método
      float MatrizTrng::operator()(int i, int j);
que devuelve el valor almacenado en la posición (i,j) de la matriz triangular. Genere un error en tiempo de ejecución si (i,j) está fuera de rango.

FUNCTION Recursive (n: INTEGER ) : INTEGER;
BEGIN
  IF n <= 1 THEN
     RETURN(1);
  ELSE
     RETURN (Recursive(n-1) + Recursive(n-1) - 1);
  END;
END

3.a) [10 pts] Muestre que la complejidad de esta función es exponencial.

3.b) [10 pts] Explique un método que permita determinar, con exactitud, la cantidad de tiempo que utiliza esta función en un ambiente específico.

3.c) [5 pts] Explique por qué hace falta modificar la implementación del algoritmo para determinar, con relativa exactitud, la cantidad de espacio que utiliza esta función en un ambiente específico.

4.a) [0 pts] Haga un diagrama de un árbol binario con 15 nodos. Como etiquetas use las primeras letras del alfabeto.

4.b) [3 pts] Recorra su árbol de izquierda a derecha, usando los tres métodos recursivos clásicos.

4.c) [2 pts] Recorra su árbol por niveles de izquierda a derecha. Primero debe visitar la raíz, luego todos los nodos de profundidad uno (hijos de la raíz), luego los de profundidad dos (los nietos de la raíz), hasta llegar a los de último nivel.

4.d) [5 pts] Suponga ahora que puede usar un contenedor para almacenar punteros a las etiquetas del árbol binario. Diga qué contenedor sirve para recorrer por niveles un árbol. Explique cómo usar el contenedor.

4.e) [15 pts] Implemente el algoritmo de recorrido BF(const BinTree &T) [BF:Breadth First, "anchura primero"]. Para simplificar su trabajo, invoque en cada nodo recorrido la función:
      PROCESE(const BinTree::link *lk, const binder *B);

Soluciones

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 1999
Derechos de autor reservados © 1999