Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
Profesor Adolfo Di Mare
CI-1201
I Semestre 2005
[<=] [home] [<>] [\/] [=>]
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] 

 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.

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

1.b) [33 pts] Implemente el método clist::Orden_4132() 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, ¿cómo quedaría implementado el algoritmo que debe usar para clist::Orden_4132()?

 

2) [33 pts] 

Lista& Lista::copy(const Lista& LO) { // *this = LO
    if (&LO == this) { // evita autocopia
        return *this;
    }

    while ( _prm != 0 ) {    // borra todo
        nodo *p = _prm;
        _prm = _prm->next;
        delete p;
    }

    nodo *p = LO._prm;       // copia
    while (p != 0) {
        push_back( p->_val );
        p = p->next;
    }
    return *this;
} // Lista::copy()

2.a) [2 pts] Dibuje el modelo de la clase Lista.

2.b) [14 pts] Implemente el método Lista::copy() sin acceder al Rep de Lista. Use únicamente los métodos públicos de Lista.

2.c) [14 pts] Implemente Lista::push_front() sin acceder al Rep. Puede copiar los valores de la lista, o la lista completa si lo desea.

2.d) [3 pts] Explique qué ventaja se deriva de implementar los métodos de Lista sin acceder al Rep.

 

3) [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;
}

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

3.b) [26 pts] Implemente Lista::Ordena_Burbuja(). Use únicamente los métodos de la lista que fueron definidos como públicos en la cuarta 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.

 

4) [33 pts] Una manera de lograr que un contenedor sea polimórfico es derivar el objeto contenido de una clase base común, Chunche.

4.a) [4 pts] Declare la clase Chunche que tiene algunas de las operaciones básicas de una clase.

4.b) [3 pts] Dibuje la jerarquía de chunches que usted almacenará en la lista porlimórfica: puntos, cuadrados, círculos, autos, casas, animales, perros y gatos.

4.c) [3 pts] Los nodos de una la lista polimórfica ListaPoli contienen dos punteros: el puntero "next" hacia el siguiente nodo, y un puntero al Chunche que corresponde al nodo. Dibuje el modelo de la clase ListaPoli.

4.d) [8 pts] Escriba la declaración del Rep de ListaPoli, de su nodo y de su iterador. Para el iterador ListaPoli::iterador use un Rep que contenga únicamente un puntero hacia el nodo.

4.e) [4 pts] Implemente los dos operadores de incremento del iterador (++ avanza y -- retrocede).

4.f) [4 pts] Implemente el operador de derreferencia de ListaPoli::iterador.

4.g) [7 pts] Suponga que en la clase Chunche usted definió el método virtual Grabe(iostream &). Úselo para implementar una operación que graba toda la lista. No puede acceder al Rep de la lista.

 

Soluciones

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