CI-1201 Examen #3


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1201
II Semestre 2007

$[\/]$

CI-1201 Programación II

Examen #3 [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 todas las preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] Un Grafo G(V,A) tiene 2 componentes principales: V, que es un conjunto de vértices, y A, el conjunto de arcos o aristas, que es un conjunto de enlaces entre los vértices (en este caso, los enlaces sí tienen dirección). Si los valores de los arcos son números y los vértices son hileras, una manera de representar el grafo es utilizar una tabla como la siguiente:

Fuente->Base(1) == 12   Medio->Fin(1) == 13   Fuera->Adentro == 13
Fuente->Medio   ==  6   Medio->Fin(2) == 23   Adentro->Fuera == 13
Fuente->Base(3) == -3   Medio->Fin(3) == -7

Base(1)->Medio == -3    Fin(1)->Destino == 1
Base(2)->Medio == 10    Fin(2)->Destino == 0
Base(3)->Medio == 20    Fin(3)->Destino == 1

1.a) [0 pts] Haga el dibujo del grafo descrito por esta tabla.

1.b) [3 pts] Explique cómo implementar un grafo usando un diccionario std::map<>.

1.c) [6 pts] Programe el Rep de la clase Grafo. Incluya la especificación de las operaciones relevantes a esta solución.

1.d) [6 pts] Especifique el método booleano conectado() que retorna "true" si existe una secuencia de aristas que permiten ir desde un vértice hasta otro. Además, conectado() también debe calcular y retornar la lista de nodos que hay que visitar para llegar de un nodo a otro. Por ejemplo, conectado() debe producir la lista ( "Base(1)" , "Medio" , "Fin(2)" ) que es el camino de ir desde "Base(1)" hasta "Fin(2)" a un costo de 20==(-3+23).

1.e) [18 pts] Implemente conectado(). Recuerde que si usa algún método o función, también debe implementar esa rutina (aunque sí puede usar con libertad los contenedores de la biblioteca estándar).

2) [33 pts]

2.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 booleano std::vector< bool > de longitud arbitraria (pero fija) para almacenar los bits del número binario.

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

2.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).

3) [33 pts] Una Escalera_Vuelta es un contendor que en cada posición contiene un valor adicional a la cantidad de valores almacenados en la posición anterior. Por ejemplo, si la escalera contiene letras, al construir la escalera a partir de la hilera "ijos4", el valor almacenado sería este:

[0] i           [0] 4
[1] jj          [1] ss
[2] ooo         [2] ooo
[3] ssss        [3] jjjj
[4] 44444       [4] iiiii

3.a) [4 pts] Diseñe el contenedor Escalera_Vuelta. Escriba la declaración del Rep. Use plantillas. Recuerde: toda especificación deb incluir ejemplos de uso "assertTrue()".

3.b) [8 pts] Especifique e implemente la operación flip() que le da vuelta a todos los elementos de la Escalera_Vuelta. Diseñe el contenedor de manera que sea posible darle vuelta rápidamente a los valores contenidos, usando un esfuerzo que no dependa de la cantidad de valores almacenados. Esto quiere decir que su clase Escalera_Vuelta no necesita tocar ni copiar ninguno de los elementos almacenados, sean estos sólo 2 o 2 mil millones.

3.c) [8 pts] Especifique e implemente la operación flop(i) que hace que el primer valor del su Escalera_Vuelta no sea el que estaba en la posición [0] sino que sea el de posición [i]. Por ejemplo, si el valor almacenado era [0,11,222,3333,44444,555555], después de flop(2) el valor almacenado será [2,33,444,5555,00000,111111], porque el primer valor del vector será el que estaba en la posición [2]. En su implementación no copie ninguno de los valores almacenados en el contenedor.

3.d) [8 pts] Especifique e implemente la operación push_front() para la Escalera_Vuelta.

3.e) [5 pts] Implemente la operación pop_back() para la Escalera_Vuelta. Para economizar código, use push_front() en su implementación.

3.f) [400 pts] Implemente Escalera_Vuelta de manera que el tiempo de ejecución de las siguientes operaciones sea siempre constante: flip(), flop(), at(), push_front() y pop_back().

Soluciones

$[/\]$