Examen #2 [solución]

      Duración: Ciento veinte minutos. 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 todas las preguntas. ¡No haga más de lo que se le pide!

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

      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,3,2,1).

1.b) [33 pts] Implemente el método clist::Orden_4321() 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 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_4321()?

3.a) [6 pts] Especifique la función swap( list&, i ) que sirve para intercambiar los valores que es encuentran en la posición "*i" y "*(++i)" de la lista. Recuerde usar siempre el formato Doxygen e incluir los datos de prueba BUnit.

3.b) [6 pts] Especifique particion() que separa una lista en dos listas, de manera que los valores que quedan en la primera lista son mayores que el parámetro "pivote" de particion(), y los de la segunda son los demás valores almacenados en la lista original. Use el formato Doxygen e incluya los datos de prueba BUnit.

3.c) [18 pts] Implemente particion(). Como esta función no es amiga (friend) de la clase lista, al escribir su implementación use la operaciones lista::splice() y su función lista::swap( list&, i ). Su implementación no debe copiar, directa o indirectamente, ninguno de los valores almacenados en la lista.

3.d) [3 pts] Implemente el algoritmo de ordenamiento de la Burbuja() usando su función lista::swap( list&, i ), de manera que nunca se copie ninguno de los valores almacenados en la lista. Explique si es necesario usar lista::swap() en la implementación o si, por el contrario, basta con las otras operaciones de la lista.

Soluciones

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