Resuelve empleando Linux, cualquier editor y un terminal los siguientes ejercicios. Posteriormente, piensa qué solución te parece mejor, la tuya o alguna de las que se proporcionan a continuación.

1. Escribe en lenguaje Java un programa que pida al usuario y lea de la entrada estándar un valor entero. Mientras el entero leído sea negativo se lo debe volver a pedir, tantas veces como sea necesario. Una vez leído un entero no negativo, el programa debe calcular y mostrar en la salida estándar cuánto vale el factorial de dicho número.

   • Solución 1
   • Solución 2
   • Solución 3
   • Solución 4

2. Escribe en lenguaje Java un programa que pida al usuario y lea de la entrada estándar un valor entero positivo, suponiendo que será así. El programa debe mostrar en la salida estándar un mensaje indicando si el número es primo o no. Observa que, por convenio, el número 1 no se considera primo.

   • Solución 1
   • Solución 2
   • Solución 3
   • Solución 4

Completa las actividades no presenciales de esta semana resolviendo los siguientes ejercicios, o resuélvelos también si puedes en el laboratorio:

3. Escribe en lenguaje Java un programa que pida al usuario y lea de la entrada estándar un valor entero no negativo. El programa debe mostrar en la salida estándar cuánto vale el doble factorial de dicho número.

4. Escribe en lenguaje Java un programa que pida al usuario y lea de la entrada estándar un valor entero positivo. El programa debe mostrar en la salida estándar cuánto vale el primorial de dicho número.

Resuelve empleando Linux, cualquier editor y un terminal los siguientes ejercicios. Si no te da tiempo de resolver ambos en el laboratorio, complétalos como parte de las actividades no presenciales de esta semana.

5. [!] Escribe en lenguaje Java un programa que pida al usuario y lea de la entrada estándar un valor entero no negativo n. El programa debe mostrar en la salida estándar el resultado de calcular el siguiente sumatorio:

   $$\sum _{i=0}^{n}i!=0!+1!+2!+\dots +n!$$

   En una primera versión, puedes utilizar el método factorial(n) de la solución 4 del ejercicio 1.

   Después piensa si puedes aumentar la velocidad con la que se ejecuta tu solución reduciendo la cantidad de multiplicaciones que se realizan para calcular el resultado.

   Para comprobar que tus implementaciones son correctas, puedes consultar WolframAlpha.com y comprobar que obtienes el mismo resultado en las pruebas que hagas. Por ejemplo:

   • 4!
   • sum i!, i=0 to 4

   Posteriormente, piensa qué solución te parece mejor, la tuya o alguna de las que se proporcionan a continuación.

   • Solución 1
   • Solución 2
   • Solución 3
   • Solución 4
   • Solución 5

6. [!] Escribe en lenguaje Java un programa que pida al usuario y lea de la entrada estándar un valor real x seguido de un entero positivo n, y escriba en la salida estándar el valor aproximado de e^x dado por el siguiente desarrollo en serie:

   $$e^x\simeq 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots +\frac{x^n}{n!}$$

   En una primera versión, implementa y utiliza un método factorial(n) y un método potencia(x,n).

   En una segunda versión, intenta aumentar la velocidad con la que se ejecuta el programa calculando cada sumando a partir del anterior. ¿Es conveniente utilizar en este caso factorial (n) y potencia(x, n)?

   Para probar tus soluciones, introduce los decimales separados por una coma, no por un punto. Por ejemplo, "0,2" en vez de "0.2".

   Para comprobar que tus implementaciones son correctas, puedes consultar WolframAlpha.com y comprobar que obtienes el mismo resultado en las pruebas que hagas. Por ejemplo:

   • e^0.2

Resuelve los siguientes ejercicios distribuyendo como prefieras las horas de clase de prácticas del 13/02/2013 y las horas de trabajo no presencial. Hazlo trabajando en pareja o individualmente.

7. Escribe en lenguaje Java un método que reciba dos vectores de enteros y devuelva un nuevo vector que contenga los elementos del primero seguidos de los elementos del segundo.

8. Escribe en lenguaje Java un método que reciba una matriz de enteros de tamaño m×n, sume los elementos de cada columna, y devuelva el índice de la columna cuya suma sea máxima. En caso de empate, debe devolver el menor de los índices con los que se obtiene la suma máxima.

   Hazlo completando el siguiente programa: EjercicioM0_08.java.

   Después compara tu solución con esta: EjercicioM0_08_resuelto.java.

9. Escribe en lenguaje Java un método que reciba un vector de reales cuyas componentes son las temperaturas diarias máximas registradas en una determinada localidad a lo largo de cada uno de los días de un año. El método debe devolver la duración de la ola de frío más larga, o cero si no ha habido ninguna ola de frío. Considera que una ola de frío en esa localidad se produce cuando la temperatura máxima es negativa durante más de 5 días consecutivos.

   Hazlo completando el siguiente programa: EjercicioM0_09.java.

   Después compara tu solución con esta: EjercicioM0_09_resuelto.java.

10. Escribe en lenguaje Java un método que sirva para eliminar elementos duplicados en un vector de enteros. Decide qué perfil puede tener ese método.

    Hazlo escribiendo primero un programa de prueba.

    Después compara tu solución con esta: EjercicioM0_10_resuelto.java.

11. Escribe en lenguaje Java un método compararVectoresOrdenados que reciba dos vectores de enteros que están ordenados de menor a mayor en cada uno de ellos. El método debe devolver un valor booleano indicando si ambos vectores contienen los mismos valores (y en las mismas cantidades, en caso de haber valores repetidos).

    Hazlo escribiendo primero un programa de prueba.

Mira estos enlaces sobre Extreme Programming:

• Pair Programming.

• Code the Unit Test First.

Resuelve los siguientes ejercicios distribuyendo como prefieras las horas de clase de prácticas del 20/02/2013 y las horas de trabajo no presencial. Hazlo trabajando en pareja o individualmente. Compara tus soluciones con las de tus compañeros de clase.

1. Lee esta página: algoritmo de ordenación por selección (selection sort).

   Escribe en lenguaje Java un método para ordenar un vector de enteros de mayor a menor empleando ese algoritmo.

2. Escribe en lenguaje Java un método mezclarVectoresOrdenados que reciba dos vectores de enteros ordenados de mayor a menor y devuelva como resultado un nuevo vector que contenga todos los elementos de ambos, incluyendo duplicados, ordenados también de mayor a menor. El tiempo de ejecución de tu algoritmo debe ser lineal (es decir, debe crecer de forma lineal cuando crece la talla de los vectores).

   Después consulta estas soluciones de otros estudiantes:

   • Solución 1
   • Solución 2
   • Solución 3
   • Solución 4

3. Escribe en lenguaje Java un método conjuntosDisjuntos que reciba dos vectores de enteros ordenados de mayor a menor y devuelva como resultado true si no hay ningún elemento que esté en ambos vectores y false en caso contrario. El tiempo de ejecución de tu algoritmo debe ser lineal.

   Después consulta esta solución de otro estudiante:

   • Una solución

4. Escribe en lenguaje Java un método interseccionDeVectoresOrdenados que reciba dos vectores de enteros ordenados de mayor a menor y devuelva como resultado un nuevo vector que contenga, ordenados también de mayor a menor, solamente los elementos que están tanto en un vector como en el otro (es decir, en la intersección de los dos conjuntos de valores dados). Supón que ninguno de los dos vectores contiene elementos repetidos. El tiempo de ejecución de tu algoritmo debe ser lineal.

   Después consulta esta solución de otro estudiante:

   • Una solución

Resuelve los siguientes ejercicios.

5. Escribe en lenguaje Java un método para averiguar si un vector de cadenas que están ordenadas lexicográficamente contiene una determinada cadena, empleando el algoritmo de búsqueda binaria.

   Considera que el vector puede estar vacío.

6. Este programa EjemploPotenciaRecursiva.java le pide al usuario dos datos x y n y calcula de forma recursiva xⁿ en tiempo O(n).

   Utiliza el depurador de Eclipse para ejecutar el programa paso a paso prestando atención a lo que sucede en las llamadas recursivas y a los cambios en los valores de las variables.

   Piensa y prueba qué pasa si el usuario introduce un valor n negativo. Modifica el programa para que funcione bien en ese caso, teniendo en cuenta el significado matemático cuando n es negativo.

   Finalmente, diseña e implementa un algoritmo recursivo que haga ese mismo cálculo en tiempo O(log |n|), siendo |n| el valor absoluto de n. Tu solución debe funcionar tanto si n es positivo como si es negativo.

Recordatorio: La semana 7 (Magdalena) no es lectiva, la próxima sesión de prácticas se realizará dentro de dos semanas. Sería bueno que leas documentación sobre los ejercicios propuestos para esa sesión antes de acudir al laboratorio, tanto en los enlaces y bibliografía recomendados como buscando en Internet.

Resuelve los siguientes ejercicios.

7. Este programa BusquedaBinariaRecursivaIncorrecta.java contiene una implementación recursiva incorrecta del algoritmo de búsqueda binaria recursiva. Piensa por qué es incorrecta, y corrígela para que funcione bien.

8. Mira esta página sobre las torres de Hanoi de Rodolfo Valeiras, hasta entender el algoritmo recursivo (el resto no es necesario ahora, míralo opcionalmente en otro momento si te interesa).

   Sin buscar ninguna página donde te lo den hecho, implementa un programa que pida al usuario un entero positivo n y, empleando ese algoritmo recursivo, escriba en la salida estándar la secuencia de movimientos a realizar para resolver el problema de las torres de Hanoi de n discos.

El siguiente ejercicio es opcional:

9. Escribe en lenguaje Java un método recursivo que permita ordenar un vector empleando el algoritmo de ordenación por mezcla (merge sort). Aunque la dificultad de este ejercicio es elevada, sería bueno que lo intentes resolver sin consultar la implementación de otros autores, y que discutas tu solución con el profesor en clase de prácticas o en tutorías.

Resuelve los siguientes ejercicios, intentando completar de forma no presencial lo que no te de tiempo de completar en el laboratorio y planteando tus dudas en tutorías o en la siguiente sesión de prácticas.

En el primer ejercicio se te pide implementar una primera versión de una clase Fecha. Imagínate que, una vez completada, la hicieses pública y otros usuarios empezasen a usarla en sus programas. En el segundo ejercicio se te pide hacer un tipo de actualización que no debería afectar a ninguno de los programas que ya estuviesen usando la clase: añadir un nuevo método. En el tercer ejercicio se te pide hacer otro tipo de actualización que tampoco debe requerir cambiar nada en ninguno de dichos programas: cambiar la representación interna de los datos y realizar más eficientemente algunas de las operaciones. Ello ilustra la importancia del principio de ocultación de información en la programación orientada a objetos.

1. Implementa en lenguaje Java una clase Fecha que permita representar fechas formadas por día, mes y año. Esos tres datos se deben guardar en atributos privados. La especificación de la clase requiere que tenga los siguientes métodos públicos. Ten en cuenta que el orden en que aparecen los métodos a continuación no es necesariamente el orden en que debes implementarlos. Piensa por dónde te interesa empezar para poder ir probando tu implementación gradualmente, y prueba cada método tras implementarlo, no esperes a tener todos para probar todo. Guarda tus programas de prueba para utilizarlos tras las modificaciones que se te pedirán más adelante.

   Además de utilizar tus propias pruebas, cuando finalices puedes utilizar las siguientes: PruebaFecha01.java y PruebaFecha02.java.

   1. Un constructor Fecha(int día, int mes, int año) que permita crear una nueva fecha. En este ejercicio puedes suponer que es responsabilidad del usuario de la clase proporcionar los datos de una fecha válida.

   2. Un constructor Fecha(Fecha otraFecha) que permita crear una nueva fecha que sea una copia de la que se le pasa.

   3. Un método de acceso int getDía() que devuelva el día.

   4. Un método de acceso int getMes() que devuelva el mes.

   5. Un método de acceso int getAño() que devuelva el año.

   6. Un método Fecha díaSiguiente() que cree y devuelva una nueva fecha correspondiente al día siguiente, sin modificar la fecha que se tiene.

   7. Un método Fecha sumarDías(int días) que cree y devuelva una nueva fecha con el resultado de sumar el número de días que se le pase, sin modificar la fecha que se tiene. Puedes hacerlo utilizando el método díaSiguiente, ya que no se requiere que la solución sea eficiente.

   8. Un método String toString() que permita obtener una cadena que representa la fecha en formato día/mes/año.

   9. Un método boolean equals(Object otroObjeto) que devuelva true si la fecha es igual a la que se le pase y false en caso contrario.

   10. Un método int compareTo(Fecha otraFecha) que devuelva un valor negativo, cero o positivo indicando si la fecha es anterior, igual o posterior, respectivamente, a la que se le pase como argumento.

   11. Un método estático int díasMes(int mes, int año) que devuelva la cantidad de días de un determinado mes, teniendo en cuenta si es febrero y pertenece a un año bisiesto.

   12. Un método estático boolean añoBisiesto(int año) para comprobar si un año es bisiesto. Recuerda que un año es bisiesto si es divisible por 4 y no es divisible por 100, o si es divisible por 400.

   Después compara esta solución con la tuya.

2. Supongamos que la especificación de la clase Fecha que has implementado en el ejercicio anterior sufre una modificación, consistente en añadir lo siguiente:

   13. Un método int restarFechas(Fecha otraFecha) que calcule y devuelva la cantidad de días entre las dos fechas. El resultado será positivo, cero o negativo dependiendo de que la fecha sea posterior, igual o anterior a otraFecha, respectivamente.

   Haz una primera implementación sin preocuparte de la eficiencia de la solución. Para ello, puedes contar cuántas veces hace falta usar el método díaSiguiente partiendo de la fecha menor hasta llegar a la fecha mayor.

   Verifica que los programas de prueba del ejercicio anterior siguen funcionando tras la actualización sin cambiar nada en ellos y haz también pruebas del nuevo método.

   Después compara esta solución con la tuya.

3. Supongamos ahora que necesitamos una nueva actualización de la clase Fecha. La interfaz de la clase no cambia respecto de la que ha quedado al completar el ejercicio anterior, es decir, las cabeceras de los métodos públicos deben seguir siendo las mismas, pero necesitamos la clase Fecha en un contexto en el que se va a hacer un uso intensivo de los métodos sumarDías y restarFechas y la eficiencia de ambos pasa a ser importante, necesitamos que ambos se ejecuten en tiempo O(1).

   Trata de entender la propuesta que se hace en el ejercicio 3.12, página 71, del libro "Estructuras de datos en Java" de M. A. Weiss, e intenta aplicarla en tu implementación. Si necesitas ayuda pídesela al profesor. En clase de prácticas se explicará a quien asista y lo solicite.

   En esta versión no es necesario que te preocupes por comprobar la validez de la fecha, te encargarás de eso en una versión posterior. Puedes suponer que solamente necesitamos poder trabajar con fechas comprendidas entre el 1 de enero de 1800 y el 31 de diciembre de 2500, y que es responsabilidad del usuario de la clase no salirse de dichos límites.

   Si quieres, puedes resolver el ejercicio completando lo que falta en la siguiente implementación incompleta, en la que puedes ver cómo utilizar atributos e inicializadores estáticos: Fecha.java. También puedes modificarla como creas conveniente.

   Después compara esta solución con la tuya.

   Al finalizar compara el tiempo que cuesta ejecutar PruebaFecha02.java con la versión del ejercicio 1 y con la nueva. Haz una comparación similar incluyendo el método restarFechas.

   Guarda las implementaciones realizadas para poder utilizarlas en sesiones posteriores.

Resuelve los siguientes ejercicios, intentando completar de forma no presencial lo que no te de tiempo de completar en el laboratorio y planteando tus dudas en tutorías o en la siguiente sesión de prácticas o teoría.

En el primer ejercicio se te pide implementar una primera versión de una clase LineaPoligonal como ampliación del paquete FigurasGeometricas presentado en clase de teoría (puedes encontrar aquí los ejemplos vistos). En el segundo ejercicio se te pide cambiar la representación interna de los datos sin alterar la interfaz pública de la clase, aplicando de nuevo el principio de ocultación de información.

4. Implementa en lenguaje Java una clase LíneaPoligonal que permita representar líneas poligonales. Una línea poligonal está formada por un conjunto de cero o más segmentos de modo que el extremo final de cada segmento coincide con el extremo inicial del siguiente.

   Para representar internamente una línea poligonal, en este ejercicio debes utilizar un vector de puntos. Si el vector es de talla n > 1, representará una línea poligonal formada por n - 1 segmentos cuyos extremos son los puntos almacenados en el vector, en el mismo orden en que aparecen. Por ejemplo, un vector de puntos de talla 4 que contiene los puntos (2,3), (4,5), (6,7) y (8,9), en ese orden, representa una línea poligonal formada por tres segmentos en la que el primer segmento va del punto (2,3) al punto (4,5), el segundo segmento va del (4,5) al (6,7), y el tercer segmento va del (6,7) al (8,9). Si el vector es de talla cero o uno, no tendremos ningún segmento pero consideraremos que se trata de una línea poligonal válida de longitud cero.

   La especificación de la clase requiere que tenga los siguientes métodos públicos. Antes de implementar cada método, piensa y escribe lo necesario para comprobar que funciona correctamente, y verifica que es así antes de pasar a otro. Para ello, puedes empezar implementando el método toString() y utilizarlo para probar los demás. Conserva tus programas de prueba para el ejercicio siguiente.

   1. Un constructor sin parámetros LíneaPoligonal() para crear una nueva línea poligonal que inicialmente estará vacía.

   2. Un método void añadir(Punto punto) para extender la línea poligonal añadiendo ese punto al final.

   3. Un método void quitar(int posición) para reducir la línea poligonal quitando el punto que ocupa esa posición, contando desde cero inclusive. La línea no debe cambiar si la posición es menor que cero o mayor o igual que la cantidad de puntos.

   4. Un método void quitar(Punto punto) para reducir la línea poligonal quitando ese punto. La línea no debe cambiar si no contiene ese punto. Si el punto aparece varias veces en la línea, sólo se debe quitar su primera aparición. Aunque hay otras alternativas, en este ejercicio debes implementar este método llamando al anterior.

   5. Un método void mover(double desplazamientoX, double desplazamientoY) para mover la línea poligonal moviendo cada uno de sus puntos (sin crear para ello puntos nuevos).

   6. Un método double longitud() para obtener la longitud de la línea poligonal. Si la línea tiene cero o un puntos, su longitud es cero. Si tiene dos o más puntos, su longitud es la suma de las longitudes de los segmentos que la forman. La longitud de cada segmento es la distancia entre sus dos puntos extremos.

   7. Un método String toString() para obtener una representación de la línea poligonal en forma de cadena. En dicha representación aparecen representados todos los puntos separados por --. La representación de cada punto es la propia de la clase Punto. Por ejemplo, la cadena (2.00,3.00)--(4.00,5.00)--(6.00,7.00)--(8.00,9.00) representa la línea poligonal definida por esos cuatro puntos como extremos de sus tres segmentos. Los casos especiales en que tenemos cero o un puntos se representan mediante la cadena vacía o mediante la cadena que representa un punto, respectivamente.

   8. Un método boolean equals(Object otroObjeto) para comprobar si la línea es igual que otra, es decir, tiene los mismos puntos y en el mismo orden que otra. Las líneas que contienen los mismos puntos en orden inverso consideraremos que son diferentes.

   9. Un método LíneaPoligonal crearCopiaEnProfundidad() para obtener una copia de la línea poligonal a la que luego podamos aplicar cualquier método público sin que eso cambie la línea original (por ejemplo, el método que mueve cada uno de los puntos).

   Este LineaPoligonalEjemplosErroresCopiaEnProfundidad.java contiene implementaciones incorrectas del método crearCopiaEnProfundidad(), con ejemplos de errores cometidos por estudiantes. Solamente una de esas implementaciones es correcta. Piensa cuál es la buena y por qué son incorrectas las demás, y no cometas los mismos errores

   Después compara esta solución con la tuya. Verifica que entiendes lo que sucede con el programa de prueba que se proporciona ahí y que tu implementación produce la misma salida.

   Ejercicio extra (opcional): Piensa cómo modificar el método void quitar(Punto punto) para que, si el punto aparece varias veces, se quiten todas sus apariciones en tiempo O(n) en el peor de los casos. Observa que no se consigue ese tiempo de ejecución llamando al método void quitar(int posición) para cada posición en la que se encuentra.

5. Lee el apartado 2.4.2 "Expansión dinámica de vectores" del libro "Estructuras de datos en Java" de M. A. Weiss.

   Haz una nueva implementación de la clase LíneaPoligonal en la que se utilice esa estrategia. Como talla inicial del vector puedes utilizar un valor pequeño, por ejemplo 8 o 10 son valores recomendables. Utiliza un nuevo atributo de tipo entero para saber cuántos puntos contiene la línea poligonal en cada momento (puesto que ese dato ya no coincidirá siempre con la talla del vector) y piensa en qué métodos y cómo debe actualizarse. La interfaz pública de la clase no debe cambiar.

   Conserva la versión anterior, copia su contenido y después modifica todo lo que haga falta.

   Verifica que la nueva versión funciona correctamente utilizando tus programas de prueba del ejercicio anterior.

   Después compara esta solución con la tuya.

6. Resuelve el ejercicio 3 de este examen de mayo 2012, utilizando este fichero Estudiante.java. Escribe tú las clases necesarias para representar las excepciones que se piden (aunque el enunciado diga que puedes considerar que ya están definidas). Escribe también pruebas de todo lo que se pide.

7. Completa el trabajo de prácticas del módulo 2 eligiendo el ejercicio de programación que prefieras entre los propuestos en la parte de teoría.

Resuelve los siguientes ejercicios, intentando completar de forma no presencial lo que no te de tiempo de completar en el laboratorio y planteando tus dudas en tutorías o en la siguiente sesión de teoría o prácticas. Hazlo consultando los ejemplos y la bibliografía recomendados en la parte de teoría.

En esta primera sesión del módulo 3 vamos a empezar utilizando algunas de las clases disponibles en las bibliotecas del lenguaje Java para almacenar colecciones de objetos. Dichas clases nos permiten trabajar sin tener que preocuparnos nosotros de reservar la memoria necesaria para representar la colección. A la hora de elegir cuál utilizar y cómo, hemos de tener en cuenta el coste computacional de las operaciones que necesitemos.

1. Reescribe tu implementación de la clase LíneaPoligonal de la semana 10, reemplazando el vector de puntos por un objeto de la clase ArrayList y haciendo todos los cambios necesarios en cada uno de los métodos.

   Comprueba que sigue funcionando correctamente, utilizando tus programas de prueba y cualquier prueba adicional que consideres oportuna.

   Piensa cuál es el coste computacional de cada uno de los métodos de la clase LíneaPoligonal con tu implementación, teniendo en cuenta cuál es el coste computacional de los métodos de la clase ArrayList que has utilizado.

2. Sustituye el objeto de la clase ArrayList por un objeto de la clase LinkedList.

   Comprueba que todo sigue funcionando correctamente.

   Piensa ahora cuál es el coste de cada método de la clase LíneaPoligonal con la nueva implementación. Piensa también si se puede mejorar alguna de tus implementaciones para que sea más eficiente (por ejemplo, utilizando iteradores para recorrer la lista de puntos). Si es así, hazlo.

3. Imagina que necesitásemos un método para extender la línea poligonal añadiendo un nuevo punto delante del primero. ¿Qué representación interna elegirías para que la implementación de ese método fuese lo más eficiente posible?

4. Imagina que necesitásemos un método para unir dos líneas poligonales poniendo los puntos de la segunda tras los de la primera. ¿Qué coste tendría ese método utilizando la clase LinkedList? ¿Sabrías hacer eso en tiempo O(1), con esa representación interna o con alguna representación alternativa? Si no es así, piénsalo de nuevo tras completar las clase de teoría del módulo 3.

Resuelve los siguientes ejercicios, intentando completar de forma no presencial lo que no te de tiempo de completar en el laboratorio y planteando tus dudas en tutorías o en la siguiente sesión de prácticas. Hazlo consultando los ejemplos y la bibliografía recomendados en la parte de teoría.

Ten en cuenta que el miércoles 01/05/2013 no es lectivo, y que el miércoles 08/05/2013 será la última sesión de laboratorio del curso.

En estas sesiones te proponemos ejercicios consistentes en implementar varios Tipos Abstractos de Datos cumpliendo ciertas especificaciones, utilizando internamente diferentes listas de nodos enlazados implementadas por ti. Queremos que aprendas a hacer implementaciones así, y para ello no debes resolver el problema empleando otra representación interna ni empleando las implementaciones estándar de estructuras de datos disponibles en las bibliotecas de Java. No debes deducir que la representación interna que se pide aquí es la más adecuada para implementar ese Tipo Abstracto de Datos.

5. Ficheros necesarios.

   Realiza una implementación del Tipo Abstracto de Datos Cola introducido en clase que permita almacenar datos de tipo entero, empleando ahora una lista de nodos simplemente enlazada para representar internamente la cola. Cada nodo tendrá una referencia al siguiente nodo, manteniendo en la cola una referencia al primer nodo y una referencia al último nodo.

   Puedes completar la implementación de esta clase ColaEnlazada. Observa que esa clase implementa esta interfaz Cola. Por tanto, para que tu implementación esté completa debe incluir al menos todos los métodos declarados en esa interfaz, y hasta que sea así tendrás errores de compilación. Debes tener en cuenta, además, los siguientes requisitos. Observa que para conseguir la eficiencia que se pide es importante elegir bien en qué extremo de la cola se realizan las inserciones y en qué extremo se realizan las extracciones.

   1. El constructor sin argumentos ColaEnlazada() debe crear una nueva cola que inicialmente estará vacía.

   2. El método void insertar(int dato) debe insertar el dato en la cola. El tiempo de ejecución de este método debe ser O(1).

   3. El método int extraerPrimero() debe devolver y eliminar el dato que lleva más tiempo en la cola, siguiendo una estrategia FIFO. Si la cola está vacía, no debe cambiar y debes lanzar una excepción ExcepcionColaVacia. El tiempo de ejecución de este método debe ser O(1).

      Puedes utilizar esta clase ExcepcionColaVacia. Observa que la clase ExcepcionColaVacia extiende la clase RuntimeException en vez de la clase Exception. De ese modo el usuario de la clase no estará obligado a capturarla o relanzarla si sabe que no va a suceder. Comprueba que es así.

   4. El método int consultarPrimero() debe devolver el dato que lleva más tiempo en la cola, sin eliminarlo de la cola. Si la cola está vacía, no debe cambiar y debes lanzar una excepción ExcepcionColaVacia. El tiempo de ejecución de este método debe ser O(1).

   5. El método int talla() debe devolver la cantidad de elementos que contiene la cola. El tiempo de ejecución de este método debe ser O(1).

   6. El método boolean esVacía() debe devolver true si la cola está vacía y false si no es así. El tiempo de ejecución de este método debe ser O(1).

   7. El método void vaciar() debe volver a dejar una cola vacía. El tiempo de ejecución de este método debe ser O(1), sin tener en cuenta el tiempo asociado al recolector de basura.

   8. El método String toString() debe devolver una cadena que empiece con el carácter <, termine con el carácter >, y contenga entre ambos los números que están almacenados en la cola (en el orden en que podrían ser extraídos). Utiliza un espacio en blanco para separar los números entre si y para separarlos de los delimitadores < y >. La cadena que representa la cola vacía es <>. El tiempo de ejecución de este método debe ser O(n), siendo n la talla de la cola.

      Si, por ejemplo, en una cola inicialmente vacía insertamos los datos 5, 7 y 3, en este orden, obtendremos la cadena < 5 7 3 >.

   Debes hacer también tus propias pruebas para verificar que cada uno de los métodos funciona correctamente en todos los casos.

6. Realiza una implementación del Tipo Abstracto de Datos Diccionario, suponiendo que tanto los datos a guardar como las claves asociadas a los mismos son de tipo entero, que tenga al menos las siguientes operaciones básicas explicadas en clase:

   1. void insertar(int dato, int clave)
   2. int buscar(int clave)
   3. void eliminar(int clave)

   En el libro "Estructuras de datos en Java" de M. A. Weiss los diccionarios se definen brevemente en el segundo párrafo de la página 155. También puedes buscar en Internet TAD diccionario.

   Lanza excepciones que indiquen que el dato a buscar o a eliminar no se ha encontrado.

   Como representación interna utiliza una lista de nodos doblemente enlazada para guardar los datos y las claves, para hacer un ejercicio con ese tipo de representación interna. Cada nodo tendrá cuatro atributos: un dato, su clave, la referencia del nodo siguiente (o null si es el último) y la referencia del nodo anterior (o null si es el primero).

   Puedes consultar el apartado 16.3 "Listas doblemente enlazadas y listas enlazadas circulares" del libro de M. A. Weiss para ello (aunque tu implementación no es necesario que sea circular). En ese apartado Weiss utiliza la idea que explica en el 16.1.1 "Nodos cabecera"; en tu implementación puedes optar por utilizar nodos cabecera y final o no, lo que prefieras.

   Analiza el tiempo de ejecución de cada operación con la representación anterior. Compáralo con el que se obtendría con otras representaciones internas: una lista simplemente enlazada, una lista simplemente enlazada y ordenada, un vector, o un vector ordenado. Después compara esta solución con la tuya.

7. El Tipo Abstracto de Datos Multiconjunto permite representar lo que en matemáticas se denomina multiconjunto, que es es un conjunto que puede contener elementos repetidos.

   Supongamos que estamos desarrollando una aplicación en la que necesitamos trabajar con multiconjuntos que contengan elementos de tipo entero, como por ejemplo {12, 35, 7, 23, 12, 12, 35, 7, 9}. Supongamos también, como ejercicio, que las operaciones que necesitamos realizar con dichos multiconjuntos son las que se enumeran a continuación (no pretendemos que sea un comportamiento estándar).

   Implementa en Java la clase Multiconjunto con dichas operaciones, teniendo en cuenta que no se conoce a priori el tamaño del multiconjunto y la memoria necesaria para guardar los elementos se debe gestionar dinámicamente, reservándola en tiempo de ejecución cuando corresponda. Las operaciones se deben poder utilizar como ilustran los ejemplos.

   Como representación interna utiliza una lista de nodos simplemente enlazada y ordenada, en la que cada nodo contenga un elemento, un contador de ocurrencias de ese elemento y la referencia del nodo siguiente (o null si es el último). El orden de los nodos en la lista debe venir dado por el orden entre los valores que contienen, no por el orden de inserción. De ese modo, la comparación entre dos multiconjuntos que necesitamos se puede (y se debe) realizar en tiempo O(n) siendo n la talla de las listas. Al eliminar un elemento, quita el nodo de la lista.

   1. Crear un nuevo multiconjunto vacío. Ejemplo:

      Multiconjunto mc = new Multiconjunto();

   2. Insertar elementos en el multiconjunto. Ejemplo:

      mc.insertar(7);

      El orden en que se insertan los elementos no es necesario conservarlo para ninguna operación.

   3. Averiguar cuántas veces aparece un elemento en el multiconjunto. Ejemplo:

      if (mc.contar(7) > 5) ...

      Si el elemento elem no está en el multiconjunto mc, mc.contar(elem) debe devolver 0.

   4. Eliminar todas las ocurrencias de un elemento del multiconjunto. Ejemplo:

      mc.eliminar(7);

      Si el elemento elem no está en el multiconjunto mc, mc.eliminar(elem) debe lanzar una excepción de tipo ElementoNoEncontrado y el multiconjunto mc no debe modificarse.

   5. Dados dos multiconjuntos, eliminar del primero todas las ocurrencias de los elementos que contiene el segundo. Ejemplo:

      mc1.eliminar(mc2);

      Si no hay ningún elemento de mc2 en mc1, no se debe modificar mc1 ni se debe lanzar ninguna excepción.

   6. Comparar dos multiconjuntos para averiguar si son iguales. Ejemplo:

      if (mc1.equals(mc2)) ...

      Dos multiconjuntos se consideran iguales si, y sólo si, contienen los mismos elementos y en la misma cantidad. Por ejemplo, los multiconjuntos {7, 9, 5, 7, 7, 5} y {9, 5, 7, 7, 7, 5} se consideran iguales.