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

Examen #1 [solución]

      Duración: dos horas. Lea bien el examen antes de hacerlo. 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] 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.

1.a) [0 pts] Dibuje el modelo para la lista circular L=(2,1,4,3).

1.b) [33 pts] Implemente el método Lista::Orden_2143() que reacomoda los nodos de la lista L de manera que queden ordenados usando únicamente instrucciones de asignación. No use otro tipo de sentencias; tampoco trate de escribir un algoritmo general: basta que las 6 asignaciones funcionen para esta lista L. Use 6 o menos asignaciones de punteros, para que los nodos de la lista L queden en orden ascendente (1,2,3,4). En su solución usted puede usar sólo un puntero como variable temporal. Al hacer su solución debe mostrar el diagrama de la lista después de que se ejecuta cada instrucción.

1.c) [0 pts] Si usara 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, ¿cambia mucho el algoritmo que debe usar para clista::Orden_2143()?

 

2) [33 pts] Una hilera es una colina o un valle si los valores de sus letras crecen y luego decrecen, o viceversa. Por ejemplo, las hileras "35764321" es una colina, mientras que "9864125" es un valle.

2.a) [5 pts] Especifique la función bool Colina_Valle(const Lista& L); que regresa true si al recorrer la lista "L" hacia adelante sus valores forman una colina o un valle.

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

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

 

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

3.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: ( ) [ ] { } < > .

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

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

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

 

4) [33 pts] El método de ordenamiento de la burbuja intercambia valores en un vector hasta que todo queda ordenado. 

A[0].key =  -∞;
for (i=2; i<n; ++i) {
     j = i;
     while (A[j] < A[j-1]) {
         swap(A[j], A[j-1]);
         j = j-1
     }
}

void ADH_list::swap(ADH_list& L) {
/*  resultado
    Intercambia *this <==> L
*/
    nodo *tmp = L._prm;
    L._prm = _prm;
    _prm = tmp;
}

4.a) [7 pts] Especifique el método Lista::Ordena_Burbuja() para la clase Lista.

4.b) [26 pts] Implemente Lista::Ordena_Burbuja(). Use únicamente los métodos de la lista que fueron definidos como públicos en la tercera tarea programada, evitando de esta forma acceder al Rep de la lista [operator=(), push_front(), push_back(), pop_front(), pop_back(), empty(), first()]. No hace falta que su solución sea eficiente, por lo que puede usar varias listas temporales para hacer su trabajo. También puede copiar los valores de la lista.

Soluciones

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