Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
Profesor Adolfo Di Mare
CI-1201
I Semestre 2007
[<=] [home] [<>] [\/] [=>]
CI-1201 Programación II

Examen Final [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]
/           \     +--+
| 1 0 4 3 5 |     |  | \
| 1 0 4 3 5 |     |  |  > [ 1 0 4 3 5 ]  
| 1 0 4 3 5 | ==\ |__| /
| 2 2 7 8 1 | ==/ |  | \
| 2 2 7 8 1 |     |  |  > [ 2 2 7 8 1 ]
| 2 2 7 8 1 |     |  | /
\           /     +--+
      Suponga que usted necesita almacenar en la clase MatrizRepetidora los valores de una matriz bidimensional de enorme tamaño, en donde ocurre que muchas de las filas están repetidas. Para ahorrar espacio, la idea es almacenar la matriz usando punteros o referencias a las filas comunes.

1.a) [3 pts] Dibuje el modelo de la clase MatrizRepetidora y muestre la relación entre todos los valores almacenados en el Rep.

1.b) [6 pts] Declare la clase RenglonSote que contiene los valores numéricos de una fila de la matriz. Esta es una clase interna, usada para implementar el Rep de la MatrizRepetidora. Declare también la matriz.

1.c) [5 pts] Especifique la operación quitaDup() que sirve para eliminar todas las filas duplicadas de la MatrizRepetidora sustituyéndolas por un único RenglonSote que es compartido por todas esas filas. Argumente en favor y en contra de que esta operación sea pública o privada.

1.d) [8 pts] Implemente quitaDup(). No olvide que los renglones pueden estar compartidos entre varias filas de la matriz.

1.e) [6 pts] Especifique e implemente la operación swap() que permite intercambiar 2 renglones de la MatrizRepetidora.

1.f) [5 pts] Es bien sabido que una matriz siempre se puede multiplicar por su propia matriz traspuesta. Especifique e implemente el método multiTras() que retorna el valor almacenado en la posición [i,j] de la matriz que resulta de multiplicar la matriz por su propia traspuesta.

1.g) [0 pts] Implemente la función que verifica la invariante para la clase MatrizRepetidora.

 

2) [33 pts] Suponga que usted está implementando una lista doblemente enlazada similar a la de la biblioteca estándar C++ en la que se usa un nodo centinela.

2.a) [0 pts] Declare el Rep de la lista y de su nodo. Use plantillas.

2.b) [5 pts] Especifique e implemente el método "unoOdos()" que retorna "true" cuando la cantidad de valores almacenados en la lista es "1" o "2". Use dos o menos comparaciones de punteros en su implementación; no use ciclos.

2.c) [6 pts] Especifique e implemente el método "swap()" que recibe un iterador como argumento e intercambia ese nodo con el siguiente. Use cirugía de punteros.

2.d) [11 pts] Utilice únicamente su método "swap()" para especificar e implementar la función "trasladeMayor()"que recibe a una lista y traslada al final el elemento más grande de la lista pero nunca los copia. ¡No se le meta al Rep!

2.e) [11 pts] Suponga que usted cuenta ya con un método "splice(list& L)" que toma el último nodo de la lista "L" y lo pone de primero en la lista "*this". Implemente la función "Burbuja(list& L)" que ordena de menor a mayor los valores almacenados en la lista. En su respuesta utilice únicamente"splice()" o lo que usted ha implementado en el examen. ¡No se le meta al Rep!

 

3) [33 pts] Considere la siguiente rutina:
typedef unsigned q;typedef q w;
w Yin(w n){return --n;}w
#define DOS 0
Yan(w n){return ++n;};;;;;;;;;;w YinYan
(w a,w CERO){j(a,CERO)if(a>DOS){return
Yan(YinYan(Yin(a),CERO));}else if(CERO>DOS){return
Yan(YinYan(DOS,Yin(CERO)));}else{return DOS;}}

3.a) [8 pts] Escriba de nuevo el programa. No cambie los identificadores, pero use un espaciado que sea congruente con las buenas prácticas de programación.

3.b) [11 pts] Muestre los valores que el programa graba si se invoca la función recursiva con los valores (0,5), (3,0) y (3,5). Suponga que la macro está definida así:
#define j(q,w) cout<<"n"<<q<<" m"<<w<<endl;

3.c) [14 pts] Reescriba el programa. Incluya las especificaciones y la documentación interna adecuada. Use identificadores apropiados. Luego implemente eficientemente la función para el caso en que la macro está definida así:
#define j(q,w)

3.d) [0 pts] Explique qué ocurre si se usan los argumentos (-1,0) o (0,-1).

 

Soluciones

[mailto:] Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2007
Derechos de autor reservados © 2007
[home] <> [/\]