Examen #1 [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 únicamente las preguntas pares o las impares. Resuelva la mitad de 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()?

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.

2.a) [0 pts] Dibuje el modelo para la lista circular L=(8,9,6,7,2,4).

2.b) [33 pts] Implemente el método clist::Orden_896724() 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 (2,4,6,7,8,9). 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.

2.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_896724()?

3.a) [8 pts] Especifique en formato "Doxygen" la función Splice() para la lista, que sirve para trasladar valores de una lista a otra usando cirugía de punteros.

3.b) [3 pts] Especifique en formato "Doxygen" la función Reverse() que vuelve al revés los valores de una lista.

3.c) [22 pts] Implemente Reverse(). Utilice su Splice() para evitar accesar el Rep de la lista. Puede usar los métodos de la lista pero evite copiar cualquiera de los valores que la lista contiene.

3.d) [0 pts] Especifique el método list::size() que retorna la cantidad de valores almacenados en la lista.

4.a) [6 pts] Especifique en formato "Doxygen" la función Splice() para la lista, que sirve para trasladar valores de una lista a otra usando cirugía de punteros.

4.b) [5 pts] Especifique en formato "Doxygen" la operación L.Merge(LL) que funciona intercalando en orden los valores de "L" y "LL" cuando ambas listas están ordenadas.

4.c) [22 pts] Implemente L.Merge(LL). Utilice su Splice() para evitar accesar el Rep de la lista. Puede usar los métodos de la lista pero evite copiar cualquiera de los valores que la lista contiene. Debe implementar el algoritmo de intercalación.

4.d) [0 pts] Especifique el método list::size() que retorna la cantidad de valores almacenados en la lista.

Soluciones

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