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 2010

$[\/]$

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 es un conjunto de vértices etiquetados que están conectados mediante aristas. Una forma de representar el grafo es usar una matriz cuadrada, en donde la entrada G(i,j) indica que el vértice "i" está conectado al "j". La matriz del grafo es simétrica si cada vez que el grafo contiene la conexión i→j también la arista j→i aparece en el grafo. El grafo que se muestra aquí es un grafo dirigido.

1.a) [7 pts] Suponga que las etiquetes del grafo son hileras. Declare la clase "grafo" en la que las aristas son punteros almacenados en la lista de conexiones para cada etiqueta. Use el diccionario std::map<>.

Recuerde que la diferencia entre "definir" y "declarar" un objeto en C++ es que las declaraciones se ponen en los archivos de encabezados <*.h> y <*.hpp>, mientras que las definiciones están en los archivos de implementación <*.c> y <*.cpp>.

Las declaraciones corresponden a la especificación.
Las definiciones corresponden a la implementación. Para facilitarle memorizar este hecho, asocie la palabra "definición" con la directiva #define que sirve para implementar macros en C++:
#define max(a,b) ( (a)>(b) ? (a) : (b) )

1.b) [5 pts] Especifique el método booleano "esGrafo()" para la clase "grafo" que revisa que cada vez que aparece en el grafo la arista i→j también aparece la arista j→i. Use el formato Doxygen e incluya los datos de prueba BUnit.

1.c) [5 pts] Especifique el método "agregueArista()" para la clase "grafo". Use el formato Doxygen e incluya los datos de prueba BUnit.

1.d) [8 pts] Implemente "agregueArista()".

1.e) [8 pts] Implemente "esGrafo()".

2) [33 pts] Considere la clase lista cuyo modelo (diagrama) aparece en la figura de abajo.

 L ──>─┐
       │
       v
┌────────┬───┐   ┌────────┬───┐   ┌────────┬───┐
│ elem_1 │ *─┼──>│ elem_2 │ *─┼──>│ elem_3 │ *─┼─> NIL
└────────┴───┘   └────────┴───┘   └────────┴───┘

2.a) [7 pts] Haga las declaración para la clase lista. Incluya en el Rep apenas lo suficiente para implementar la operación lista::K_pase(L, k).

2.b) [7 pts] Especifique la operación lista::K_pase(L, k), que traslada de la lista todos los valores que está en una posición múltiplo de k, y los deja en la lista L. Evite copiar los nodos al trasladarlos de lista.

2.c) [19 pts] Implemente lista::K_pase(L, k).

2.d) [0 pts] Explique qué es la cirugía de punteros.

3) [33 pts] Una "escalera" es una clase que contiene una hilera de caracteres a la que se le pueden aplicar estas operaciones:

suba(E,n): Traslada el n-ésimo elemento hacia arriba una vez (si se puede).
Suba("!bcde",1) ==> "b!cde"
Suba("abcd!",5) ==> "abcd!"
aparea(E): Intercambia todas las parejas de elementos en la escalera (excepto el último si hay una cantidad impar).
Aparea("abcdefg") ==> "badcfeg"
caiga(E): Traslada el elemento del fondo.
Caiga("abcde!") ==> "!abcde"
cuenta(E): Función que regresa la cantidad de elementos de "E".
Cuenta("abcde") ==> 5
print(E): Imprime la escalera.

La rutina "circular()" corre circularmente el primer elemento de la "escalera", imprimiéndola antes de cada corrimiento. La invocación circular("!abcd") debería producir la siguiente salida:

!abcd
a!bcd
ab!cd
abc!d
abcd!
!abcd
a!bcd  etc...

3.a) [6 pts] Implemente la rutina "circular()" usando la "escalera", de forma que se produzca la salida arriba descrita. Use únicamente las operaciones arriba indicadas (No se le meta al Rep).

3.b) [0 pts] Se ha determinado que ninguna escalera será más grande que 2387 caracteres. Escriba las declaraciones de una implementación de la "escalera" en que se usen vectores de letras.

3.c) [5 pts] Indique cómo modificaría usted el procedimiento "circular()" de la parte a) para que trabaje adecuadamente en la nueva implementación usando arreglos.

3.d) [11 pts] Si la "escalera" inicial es "aicoca", indique cuáles de las siguientes escaleras pueden ser impresas usando las operaciones arriba indicadas:

"aicoca"
"iaocac"
"aocaci"
"aoccai"
"coacia"

3.e) [11 pts] ¿Es posible usar únicamente estas operaciones del Tipo de datos abstracto "escalera" para implementar un procedimiento que ordene [escaleras de caracteres]? Si se puede hacer, impleméntelo. De lo contrario... ¡explique!

Soluciones

$[/\]$