Examen Final [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. Debe escribir con un bolígrafo de tinta. Resuelva tres de las cuatro preguntas. ¡No haga más de lo que se le pide!

<=====================================================>
|  prev next                                          |
|    +-+-+     +-+-+     +-+-+     +-+-+     +-+-+    |
<===>|*|*|<===>|*|*|<===>|*|*|<===>|*|*|<===>|*|*|<===>
     +-+-+     +-+-+     +-+-+     +-+-+     +-+-+
     | 1 |     | 2 |     | 3 |     | 4 |       L
     +---+     +---+     +---+     +---+       ^
       ^       m_val                 ^        /|\
       |                             |         |
   L.first()                      L.last()   L.end()

1.a) [3 pts] Declare el Rep para esta implementación de la lista STL, en la que en lugar de crear un nodo cabeza, el truco que se usó es poner los campos "next" y "prev" como los campos del Rep de la lista. Para hacerlo, se usó herencia, derivando de la clase "list_node_base<>" (por eso el Rep de la lista es un nodo cabeza que sólo contiene los punteros de enlace).

1.b) [3 pts] Especifique el método "list::swap(list<T>&)" que sirve para intercambiar los valores de listas.

1.c) [12 pts] Implemente "list::swap(list<T>&)". Use cirugía de punteros para evitar copiar los valores o los nodos. En su implementación no invoque ningún método de la lista.

1.d) [3 pts] Especifique el método "list::Move(list<T>&)" que permite quitarle los valores a una lista y ponerlos en otra.

1.e) [6 pts] Implemente "list::Move(list<T>&)". Use cirugía de punteros para evitar copiar los valores o nodos.

1.f) [6 pts] Implemente "list::swap(list<T>&)". Use su método "Move()" y evite accesar el Rep de la lista.

2.a) [4 pts] Especifique la función K_Splice() que sirve para trasladar varios valores del principio de una lista a otra.

2.b) [4 pts] Especifique la función Reverse() que deja al revés los valores de una lista.

2.c) [6 pts] Implemente su función Reverse(). Suponga que para su lista ha usado el Rep de la lista STL, en la que en lugar de crear un nodo cabeza, el truco que se usó es poner los campos "next" y "prev" como los campos del Rep de la lista. Debe usar cirugía de punteros.

2.d) [4 pts] Especifique Brincolina().

2.e) [15 pts] Implemente Brincolina(). No se le meta al Rep. Debe usar sus funciones K_Splice() y Reverse(). Su implementación debe trasladar los valores usando cirugía de punteros para evitar copiar cualquiera de los los valores o nodos de la lista. Puede usar los métodos y algoritmos de la biblioteca STL.

m_vec || \/ <1> <2>==m_front <6> +---+---+---+---+---+---+---+ | _ | _ | 3 | 9 | 5 | 6 | _ | +---+---+---+---+---+---+---+ <0> |-----------+ m_front---+ #2 #3 #4	m_vec || \/ m_front==<5> <6> +---+---+---+---+---+---+---+ | 5 | 6 | _ | _ | _ | 3 | 9 | +---+---+---+---+---+---+---+ +-------+ |-------+ | #3 #4 m_front---+ #2 | | | +-<-<-----------------------<-<-+ m_size == 4
m_size == 4 && m_capacity == 7

3.a) [0 pts] Explique cómo funciona esta implementación de la clase Lista, que tiene las mismas operaciones de la lista que usted usó en la octava tarea. Incluya la declaración del Rep que corresponde a este diagrama en que los valores de la lista "L" son (3,9,5,6).

3.b) [3 pts] Declare el Rep para la clase Lista_Vector que corresponde al modelo que se muestra acá. Debe usar plantillas.

3.c) [3 pts] Defina la invariante para esta clase Lista_Vector. Implemente la función check_Ok() que verifica la invariante de la clase.

3.d) [3 pts] Implemente el constructor y destructor para la clase Lista_Vector.

3.e) [24 pts] Implemente los métodos push_front(), push_back(), pop_front(), pop_back(). En su implementación evite copiar los valores almacenados en el vector hacia la derecha o hacia la izquierda (use el vector en "forma circular").

Soluciones

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2006
Derechos de autor reservados © 2006