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 2001

$[\/]$

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 Arbol_2_3 es un árbol ternario en que cada nodo tiene por lo menos dos hijos y nunca más de tres, a menos que sea un nodo hoja. Además, los hijos de cada nodo deben estar ordenados ascendentemente.

1.a) [3 pts] Dibuje el modelo (diagrama) que corresponde a la clase Arbol_2_3. Explique cómo está hecho su árbol.

1.b) [4 pts] Declare la clase Arbol_2_3.

1.c) [11 pts] Defina la invariante para la clase Arbol_2_3.

1.d) [15 pts] Especifique e implemente el método Arbol_2_3::OK() que retorna true si la instancia del árbol cumple con su invariante.

2) [33 pts] Un polinomio se puede implementar usando un vector de números reales que contiene, en su entrada "i", el coeficiente del i-ésimo término del polinomio. El campo "m_grad" del Rep indica el grado del polinomio. Los términos superiores a "m_grad" no están inicializados en cero. El polinomio cero se representa con un cero en el coeficiente y con el grado() = 0. Por ejemplo, el polinomio x^3 + 2x^2 se ve así:

  polinomio               grado
   2x^2 + x^3               3

    0   1   2   3   4   5   6   7   8   9  ....
  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  | 0 | 0 |2.0|1.0| $ | ! | % | % | % | ( | = |   |   |   |
  +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
                ^
                |
                +------------- grado() == 3

2.a) [6 pts] Haga la declaración de las clases poli_VEC y poli_DEQUE usando dos tipos diferentes de vector en el Rep: un vector y la clase std::deque<> de la biblioteca STL de C++. Escriba declaraciones resumidas, incluyendo apenas lo suficiente.

2.b) [6 pts] Especifique el método fromString() que toma una hilera de la forma "x^3 + 2x^2" y produce un polinomio. Luego especifique el operador suma para polinomios. Recuerde incluir suficientes ejemplos BUnit.

2.c) [16 pts] Implemente el operador suma para polinomios. Su implementación debe estar hecha de manera que sirva para cualquiera de las dos escogencias del Rep (tenga cuidado cuando el resultado es cero).

2.d) [5 pts] Explique por qué su implementación del operador suma es independiente del Rep de su clase poli.

2.e) [0 pts] Explique cómo declarar la clase poli de manera que quien la use pueda escoger si usar un vector o un deque para los coeficientes del polinomio. Además, indique cómo generalizar esta solución para usar el diccionario std::map<> de la biblioteca estándar.

3) [33 pts] Un grafo G = (V, A) tiene dos partes: "V" es un conjunto de vértices o nodos y "A" contiene arcos. Es usual que los arcos o aristas tengan un valor numérico asociado.

3.a) [0 pts] Dibuje un grafo de 10 nodos y bastantes aristas. Llame a uno de ellos "COMIENZO" y a otro "DESTINO". Para los demás vértices puede usar nombres propios de personas. No hace falta que desde cualquier nodo se pueda llegar a todos los otros saltando por los arcos.

3.b) [10 pts] Declare la clase Grafo. Use en el Rep la clase diccionario ("map<>" o "multimap<>") de la biblioteca STL para representar los arcos. Además, permita que cada arco tenga un valor asociado, de tipo numérico.

3.c) [10 pts] Especifique el algoritmo Conectado() que imprime en un flujo de salida el camino que lleva desde un nodo a otro, si tal camino existe. Debe definir la función de manera que se pueda usar cualquier flujo para grabar el resultado.

3.d) [13 pts] Implemente Conectado(). Si lo necesita, puede usar recursividad en su algoritmo.

4) [33 pts] Explique una manera de simular el efecto de usar plantillas en C++. No olvide incluir ejemplos en su explicación. Luego explique qué limitación tiene su técnica, por lo menos al compararla con el uso de plantillas (incluya un ejemplo en la que su técnica falla).

Soluciones

$[/\]$