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. Puede hacer el examen con lápiz. Resuelva tres de las cuatro preguntas. ¡No haga más de lo que se le pide!

/** Separa los valores de la lista \c "*this" de esta manera:
    - Los valores mayores a \c "pivote" quedan en \c "*this".
    - Los valores menores o iguales a \c "pivote" son
      trasladados a \c "L0".
    - El valor anterior de \c "L0" desaparece.

    \par Nota
    La implementación no copia valores, sino que los traslada
    usando cirugía de punteros.
*/
void lista::Particion( const T& pivote, lista & L0 );

1.a) [0 pts] Dibuje el modelo para la lista circular L=(4,1,3,2) en donde la lista es doblemente enlazada y en el Rep hay un puntero al primer nodo de la lista.

1.b) [3 pts] Especifique el método Swap() para nodos que recibe 2 punteros a nodos de la lista y los intercambia usando cirugía de punteros.

1.c) [15 pts] Implemente lista::Particion(). En su implementación no use ningún otro método de la lista (tampoco Swap()).

1.d) [15 pts] Implemente el método Swap() para nodos de la lista. En su implementación no use ningún otro método de la lista.

1.e) [0 pts] Implemente lista::QuickSort() con base a lista::Particion().

           L
           |
           v
     +-------------+   +-------------+   +-------------+   +-------------+
     |   |     | *-+-->|   |     | *-+-->|   |     | *-+-->|   |     | *-+-> NIL
     |   | 2.2 |   |   |   | 4.5 |   |   |   | 2.2 |   |   |   | 1.3 |   |
NIL<-+-* |     |   |<--+-* |     |   |<--+-* |     |   |<--+-* |     |   |
     +-------------+   +-------------+   +-------------+   +-------------+

2.a) [0 pts] Escriba la declaración de las clases Arbol y Lista, que tienen la característica que usan el mismo tipo de nodo.

2.b) [7 pts] Especifique la función Arboleador() que toma una lista, similar a la de la figura de arriba, y la convierta en un árbol binario ordenado el que, al ser recorrido en inorden, tiene en orden creciente los nodos, aún si hay duplicados. Incluya un ejemplo de qué hace esta función. Si lo desea, puede basarse en la especificación genérica para la operación Move().

2.c) [26 pts] Implemente la función Arboleador(), pero evite copiar nodos en su implementación. Además, debe usar recursividad. Use los campos "_izq" y "_der" del nodo de la lista para crear el árbol, sin usar nuevos nodos. Como documentación interna, explique cómo funciona su implementación.

2-0320-0028    02-0320-0028     02320028
2-320-0028     0203200028       020320028
2-0320-028     02 0320-0028     0203228
2-0320-28      2- 32028         0232028
2-320-28       02032028         etc.

      El primer dígito de la cédula indica la provincia, y luego siguen 2 números de hasta 4 dígitos. El problema se da cuando al escribir el número de cédula la gente omite los ceros que deben aparecer al principio de alguno de los 2 números de 4 dígitos que contiene el número de cédula, también cuando quedan pegados los números y no se sabe adónde comienza el primer grupo de números y adónde está el segundo.

3.a) [18 pts] Diseñe una biblioteca de programas que sirvan para procesar números de cédula. Por ejemplo, incluya un módulo que permita obtener todas las posibles formas en que puede ser escrito un número de cédula. Note, por ejemplo, que la hilera "2- 32028" puede corresponder a muchos números cédula válidos, entre los que se encuentran "2-0320-0028" y "2-0032-0028" (defina un conjunto completo de rutinas para la manipulación de hileras que representan números de cédula; no se limite únicamente a ésta). Escriba las especificaciones de los módulos de su biblioteca. Use C++ y el estilo de documentación Doxygen.

3.b) [15 pts] Haga los datos de prueba de caja negra para sus módulos.

Soluciones

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