CI-1201 Examen #2


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1201
I Semestre 2013

$[\/]$

CI-1201 Programación II

Examen #2 [solución]

Duración: Ciento veinte minutos. 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] Jimmy Trueno, el famoso físico loco, acaba de inventar un novedoso algoritmo de graficación que permite acelerar en más de 2 órdenes de magnitud la velocidad de los programas de juegos. Por eso, la función "Relampago()" requiere la matriz "Flippy_Matrix" que tenga las siguientes cualidades:

Siempre es una matriz rectangular de tamaño MxN, en donde N==2xM.
Como en toda matriz, es necesario accesar el valor "(i,j)".
Además, la matriz debe permitir "cambios de dirección" tanto verticales como horizontales.
Independientemente del tamaño de la matriz, el tiempo que debe tomar cualquier "cambio de dirección" debe ser siempre el mismo (tiempo constante).
Independientemente del tamaño de la matriz, el tiempo que debe tomar el acceso al valor "(i,j)" debe ser siempre el mismo (tiempo constante).
En el Rep está una bandera "m_hor" que indica si la matriz está al derecho o al revés en el sentido horizontal.
En el Rep está una bandera "m_ver" que indica si la matriz está al derecho o al revés en el sentido veritcal.

/             \                    /             \
| a b c d e f |                    | f e d c b a |
| 1 2 3 4 5 6 | ==> Horizontal ==> | 6 5 4 3 2 1 |
| A B C D E F |                    | F E D C B A |
\             /                    \             /

/             \                    /             \
| a b c d e f |                    | A B C D E F |
| 1 2 3 4 5 6 | ===> Vertical ===> | 1 2 3 4 5 6 |
| A B C D E F |                    | a b c d e f |
\             /                    \             /

Flippy_Matrix

2.a) [5 pts] Declare el Rep de "Flippy_Matrix". Use la matriz chisquirrisquititica.

2.b) [4 pts] Implemente el constructor de vector y el destructor para su matriz.

2.c) [5 pts] Especifique e implemente el operador para cambiarle las dimensiones a su matriz.

2.d) [8 pts] Especifique los 2 operadores para accesar el valor "(i,j)" de la matriz: tanto el mutador como el examinador.

2.e) [11 pts] Implemente el operador examinador para accesar el valor "(i,j)" de la matriz.

2.f) [0 pts] Especifique e implemente el método para voltear la matriz. Llámelo "Flip()".

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

$[/\]$