Examen de Programació II UDL 2021 · Primer Parcial (Noviembre 2021)

Contexto: Métodos de utilidad de la API disponibles durante la prueba

List<E>: void add(int index, E element), boolean add(E e), boolean addAll(int index, Collection<? extends E> c), boolean addAll(Collection<? extends E> c), boolean isEmpty(), E remove(int index), boolean remove(Object o), Iterator<E> iterator(), ListIterator<E> listIterator(), ListIterator<E> listIterator(int index).

Iterator<E>: boolean hasNext(), E next(), void remove().

ListIterator<E>: boolean hasNext(), E next(), void remove(), boolean hasPrevious(), E previous(), void add(E e).

Object: Class<?> getClass(), boolean equals(Object obj).

Pregunta 1 (1,5 puntos). Cuestiones teóricas sobre iteradores y costes computacionales

Responde de forma concisa y razonada a cada uno de los siguientes apartados:

a.

Disponemos de un objeto listIt de tipo ListIterator<E> posicionado en una posición intermedia (ni al comienzo ni al final) sobre una lista doblemente enlazada LinkedList<E> no vacía. Si se ejecuta de forma consecutiva la secuencia de sentencias:

1º listIt.previous() -> 2º listIt.remove() -> 3º listIt.remove()

¿qué sucederá y por qué?

b.

Al realizar una operación de desencolado o eliminación de un elemento en una cola, ¿existe diferencia en el coste temporal asintótico si se emplea una cola circular sobre un array frente a una implementación basada en LinkedList<E> ? Razona la respuesta.

c.

¿Qué diferencia existe, en términos de orden de complejidad computacional, al realizar continuas inserciones al final de la estructura si se utiliza un ArrayList<E> frente a un LinkedList<E> ?

Pregunta 2 (3 puntos). Implementación de getMultiples con iteradores

Escribe el código en Java del método getMultiples que, dadas dos listas de números enteros denominadas source y multiples, retorne una nueva lista con todos aquellos valores de source que resulten ser múltiplos de al menos uno de los valores contenidos en multiples.

Se deben satisfacer las siguientes condiciones:

El método no debe alterar el contenido ni la estructura de source ni de multiples.

Si cualquiera de las dos listas (o ambas) es vacía, el resultado devuelto debe ser una lista vacía.

Es obligatorio utilizar iteradores para recorrer los elementos tanto de source como de multiples.

public static List<Integer> getMultiples(List<Integer> source, List<Integer> multiples)

Pregunta 3 (3 puntos). Operaciones de inserción y eliminación en LinkedList

A partir de la estructura interna y la representación de LinkedList<E> estudiada (véase la imagen adjunta), implementa los siguientes métodos de la clase:

void linkLast(E e): inserta el elemento recibido como el nuevo último nodo de la lista enlazada.

E unlinkFirst(): suprime y retorna el elemento alojado en la primera posición de la lista. En caso de que la lista se halle vacía, debe lanzar la excepción NoSuchElementException.

Nota: Si necesitas algún método auxiliar, inclúyelo en la solución. Recuerda gestionar adecuadamente el contador de modificaciones modCount, al igual que los atributos size, first y last.

Estructura de la clase y del nodo proporcionada:

public class LinkedList<E> {

private Node<E> first = null;

private Node<E> last = null;

private int size = 0;

private int modCount = 0;

//...

private static class Node<E> {

E item;

Node<E> next;

Node<E> prev;

Node(Node<E> prev, E element, Node<E> next) {

this.item = element;

this.next = next;

this.prev = prev;

}

}

//...

}

public void linkLast(E e) {

}

public E unlinkFirst() {

}

Pregunta 4 (2,5 puntos). Implementación del método equals en Rectangle con y sin interoperabilidad

Dadas las siguientes clases Java:

public class Rectangle {

final int width;

final int height;

public Rectangle(int width, int height) {

this.width = width;

this.height = height;

}

public int getWidth() { return width; }

public int getHeight() { return height; }

}

public class ColoredRectangle extends Rectangle {

private Color color;

public ColoredRectangle(int width, int height, Color color) {

super(width, height);

this.color = color;

}

public Color getColor() { return color; }

}

Implementa el método equals(Object obj) dentro de Rectangle de dos formas distintas:

a.

De modo que no sea interoperable con ColoredRectangle (una instancia de ColoredRectangle nunca se considerará igual a una de Rectangle).

b.

De modo que sea interoperable con subclases como ColoredRectangle (se puedan comparar atendiendo a las dimensiones de Rectangle sin violar simetría).

Explica y justifica razonadamente las diferencias técnicas entre ambas implementaciones.