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 2004

$[\/]$

CI-1201 Programación II

Examen #2 [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]

class Astring { private: char * _s; static char null; // "" == hilera nula // ... }; // Astring

Contador de referencias para la clase Astring

El Rep de la clase "Astring" contiene únicamente el puntero "_s" a la hilera que contiene el valor de la instancia. Su trabajo consiste en incorporarle a la clase la posibilidad de usar una cuenta de referencias, de manera que cuando se haga una asignación mediante el operador de copia Astring::operator =(), no sea necesario crear una copia de la hilera, sino que baste aumentar el contador de la instancia. Por eso, el destructor destruye la hilera "_s" sólo cuando el contador de referencias llega a cero.

1.a) [5 pts] Haga un diagrama y explique cómo es rel Rep para la clase "Astring" si se usa un contador de referencias para compartir el valor almacenado de las hileras.

1.b) [10 pts] Defina en español la invariante para la clase "Astring". También hágalo programáticamente implementando la operación Astring::OK().

1.c) [3 pts] Indique cuáles operaciones de la clase "Astring" necesitan acceder al contador de referencias. Justifique su respuesta.

1.d) [15 pts] Implemente las operaciones que escogió en el punto anterior.

2) [33 pts] Es fácil reconocer cuáles son las direcciones de correo electrónico que contiene un archivo, porque todas tienen palabras compuestas de guiones ('-'), números o letras, separadas por puntos y con el símbolo de arrobas '@' en el medio (lo importantes es encontrar el '@' que está en el medio de la dirección de correo electrónico). Por ejemplo, las siguientes son direcciones de correo electrónico válidas:

Escriba un programa que reciba una lista de archivos en la línea de comandos, y que extraiga de ellos todas las direcciones de correo electrónico que contengan. Especifique bien cada módulo cuando escriba la implementación. Use la clase diccionario. Asuma que los iteradores de la clase diccionario le permiten obtener en orden ascendente los valores almacenados. También haga que su programa reporte la cantidad de veces que aparece cada dirección de correo electrónico, pero para eso convierta a minúsculas todas las letras, usando la función tolower() declarada en el archivo de encabezado estándar "ctype.h".

3) [33 pts]

 L->last ───────────────────────────────────────┐
                                                │
┌────────────┐   ┌────────────┐   ┌───────────┐ │
│            v   │            v   │           v v
│ ┌────────┬───┐ │ ┌────────┬───┐ │ ┌────────┬───┐
│ │ elem_1 │ ├─┼─┘ │ elem_2 │ ├─┼─┘ │ elem_3 │ ├─┼─┐
│ └────────┴───┘   └────────┴───┘   └────────┴───┘ │
│            ^               next              ^   │
│            │                                 │   │
│          first                             last  v
└───────<───────────────<────────────────<─────────┘

clist

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 clist.

3.b) [7 pts] Especifique el iterador clist::reverse_iterator que sirve para recorrer la lista de atrás hacia adelante.

3.c) [7 pts] Explique cuáles campos es necesario incluir en clist::reverse_iterator.

3.d) [7 pts] Implemente la operación que permite avanzar una instancia de clist::reverse_iterator.

3.e) [7 pts] Implemente las operaciones de comparación para clist::reverse_iterator.

4 [33 pts] En un conjunto se pueden almacenar valores con la ventaja de que luego es posible constatar si el conjunto contiene o no contiene un valor específico. Además, el conjunto también tiene varias operaciones muy usadas en matemática.

4.a) [2 pts] Dibuje el modelo (diagrama) para la clase Set si en el Rep se usa una implementación de árboles.

4.b) [3 pts] En el caso de una pila, las operaciones que le caracterizan son Push() y Pop(). Explique cuáles son las operaciones que caracterizan a la clase Set.

4.c) [5 pts] Escriba las declaraciones C++ para la clase Set.

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.d) [8 pts] Implemente los constructores y destructores para la clase Set. Suponga que cuenta con la clase árbol usada en la tarea programada. Su implementación debe ser eficiente.

4.e) [5 pts] Implemente en C++ la operación que sirve para cargar los valores de Set. Su implementación debe ser eficiente.

4.f) [10 pts] Sobrecargue el operador "*" e implemente la intersección de conjuntos.

Soluciones

$[/\]$