CI-1201 Examen #1


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1201
I Semestre 2002

$[\/]$

CI-1201 Programación II

Examen #1 [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] Considere el contenedor lista, con las implementaciones vistas en clase y el la segunda tarea programada.

1.a) [5 pts] Especifique una operación para eliminar un valor de toda la lista.

1.b) [14 pts] Implemente su método para una lista sencilla, en que el Rep tiene un puntero al primer nodo de la cadena de nodos, y en el último está el puntero nulo.

1.c) [14 pts] Implemente su método para una circular enlazada, en que el Rep tiene un puntero al último nodo de la lista.

2) [33 pts] Un palíndromo es una palabra que se lee igual al derecho que al revés.

2.a) [3 pts] Especifique la función bool Palindromo(const Lista& L); que regresa true si al recorrer el contenedor "L" hacia adelante se obtiene el mismo resultado que al recorrerlo hacia atrás. Por ejemplo:

Palindromo([1 2 3 2 1]) ==> true
Palindromo([1 2 3 2 0]) ==> false
Palindromo([r a d a r]) ==> true
Palindromo([M A J E M]) ==> false

2.b) [15 pts] Implemente Palindromo(). En su implementación debe usar punteros y acceder al Rep de la lista.

2.c) [15 pts] Implemente Palindromo(). En esta ocasión, use únicamente los métodos de la lista que fueron definidos como públicos en la segunda tarea programada, evitando de esta forma acceder al Rep de la lista.

3) [33 pts] La clase clist es una lista circular, en que el último nodo apunta al primero. A diferencia de una lista tradicional, en que en el Rep hay un puntero al primer nodo, en una lista circular el puntero del Rep apunta al último nodo, de manera que se pueden hacer inserciones eficientemente tanto al principio como al final de la lista.

3.a) [5 pts] Haga la declaración mínima de la clase clista.

3.b) [28 pts] Implemente el método clist::Reverse() que invierte los valores la lista de forma que sus últimos elementos pasen a ser los primeros. En su implementación no copie valores ni nodos; hágalo todo cambiando punteros.
(1, 2, 3, 4, 5) ==> (5, 4, 3, 2, 1)

4) [33 pts] Una pila se puede obtener a partir del contenedor lista implementando las operaciones Push() y Pop().

4.a) [5 pts] Especifique una función booleana Parentesis_Balanceados() que regresa el valor true si los paréntesis contenidos en la hilera que recibe como argumento están balanceados. Procese letra por letra la hilera, e ignore todas las letras en que no sean un paréntesis. Para que su función sea más flexible, permita que trabaje con los siguientes tipos de paréntesis: ( ) [ ] { } < >.

4.b) [11 pts] Use métodos inline para declarar y definir el contenedor pila, a partir de las operaciones de la lista de la segunda tarea programada. No se le meta al Rep.

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

4.c) [6 pts] Explique por qué es conveniente que todas las operaciones de la pila sean métodos inline.

4.d) [11 pts] Implemente Parentesis_Balanceados(). Al hacer su implementación use las operaciones definidas para la pila.

Soluciones

$[/\]$