✅ Examen Maestro EDA — SOLUCIONES (código compilado y ejecutado)

class CuentaBancaria {
    // 1. ATRIBUTOS PRIVADOS: nadie puede tocarlos directamente desde fuera
    private String titular;
    private double saldo;

    // 2. CONSTRUCTOR con validación: es imposible crear una cuenta inválida
    public CuentaBancaria(String titular, double saldoInicial) {
        if (titular == null || titular.isEmpty()) {
            throw new IllegalArgumentException("El titular es obligatorio");
        }
        if (saldoInicial < 0) {
            throw new IllegalArgumentException("El saldo inicial no puede ser negativo");
        }
        this.titular = titular;        // this.titular = atributo; titular = parámetro
        this.saldo = saldoInicial;
    }

    // 3. GETTERS: lectura controlada. OJO: no hay setSaldo() a propósito,
    //    el saldo SOLO cambia a través de depositar() y retirar().
    public String getTitular() { return titular; }
    public double getSaldo()   { return saldo; }

    // 4. OPERACIONES con validación (aquí vive la lógica de la clase)
    public void depositar(double cantidad) {
        if (cantidad <= 0) {
            System.out.println("Depósito rechazado: la cantidad debe ser positiva");
            return;                     // la operación inválida se ignora
        }
        saldo += cantidad;
    }

    public boolean retirar(double cantidad) {
        if (cantidad <= 0 || cantidad > saldo) {
            return false;               // nunca se permite dejar el saldo negativo
        }
        saldo -= cantidad;
        return true;
    }

    @Override
    public String toString() {
        return "Cuenta de " + titular + " | saldo: " + saldo + " EUR";
    }
}

public static void main(String[] args) {
    CuentaBancaria c = new CuentaBancaria("Ana Pérez", 100.0);
    System.out.println(c);

    c.depositar(50);
    System.out.println("Tras depositar 50 -> saldo = " + c.getSaldo());

    System.out.println("¿Puedo retirar 500? " + c.retirar(500)
            + " (saldo sigue en " + c.getSaldo() + ")");
    System.out.println("¿Puedo retirar 80?  " + c.retirar(80)
            + " -> saldo = " + c.getSaldo());

    c.depositar(-10);
    System.out.println("Saldo final: " + c.getSaldo());
}

Cuenta de Ana Pérez | saldo: 100.0 EUR
Tras depositar 50 -> saldo = 150.0
¿Puedo retirar 500? false (saldo sigue en 150.0)
¿Puedo retirar 80?  true -> saldo = 70.0
Depósito rechazado: la cantidad debe ser positiva
Saldo final: 70.0

Explicación. Los atributos son private: la única forma de tocar el saldo es a través de depositar/retirar, que validan. El constructor impide nacer en estado inválido (lanza IllegalArgumentException). ¿Por qué no hay setSaldo? Porque permitiría saltarse todas las reglas (p. ej. c.setSaldo(-5000)); el saldo solo debe cambiar mediante operaciones con significado de negocio. Fíjate en la salida: el retiro de 500 devuelve false sin tocar el saldo, y el depósito de -10 se rechaza con aviso.

abstract class Figura {
    private String nombre;                 // atributo común, encapsulado

    public Figura(String nombre) { this.nombre = nombre; }

    public String getNombre() { return nombre; }

    // Métodos ABSTRACTOS: se declaran pero NO se implementan aquí,
    // porque cada figura calcula su área y su perímetro de forma distinta.
    public abstract double area();
    public abstract double perimetro();

    // Método CONCRETO heredado por todas las hijas (usa los abstractos):
    public void describir() {
        System.out.println(nombre + " -> área = " + redondear(area())
                + ", perímetro = " + redondear(perimetro()));
    }

    private static double redondear(double v) {   // 2 decimales
        return Math.round(v * 100) / 100.0;
    }
}

class Circulo extends Figura {
    private double radio;

    public Circulo(double radio) {
        super("Círculo de radio " + radio);   // llama al constructor del padre
        this.radio = radio;
    }
    @Override public double area()      { return Math.PI * radio * radio; }
    @Override public double perimetro() { return 2 * Math.PI * radio; }
}

class Rectangulo extends Figura {
    private double base, altura;

    public Rectangulo(double base, double altura) {
        super("Rectángulo " + base + "x" + altura);
        this.base = base;
        this.altura = altura;
    }
    @Override public double area()      { return base * altura; }
    @Override public double perimetro() { return 2 * (base + altura); }
}

public static void main(String[] args) {
    // POLIMORFISMO: un array del tipo PADRE guarda objetos de las HIJAS
    Figura[] figuras = {
        new Circulo(3),
        new Rectangulo(4, 5),
        new Circulo(1)
    };
    double total = 0;
    for (Figura f : figuras) {   // la MISMA llamada...
        f.describir();           // ...ejecuta un código distinto según el objeto
        total += f.area();
    }
    System.out.println("Suma de todas las áreas: " + Math.round(total * 100) / 100.0);
    // Figura f = new Figura("x");  // NO COMPILA: una clase abstracta no se instancia
}

Círculo de radio 3.0 -> área = 28.27, perímetro = 18.85
Rectángulo 4.0x5.0 -> área = 20.0, perímetro = 18.0
Círculo de radio 1.0 -> área = 3.14, perímetro = 6.28
Suma de todas las áreas: 51.42

Polimorfismo: la variable f es de tipo Figura (el padre), pero en cada vuelta apunta a un objeto real distinto (Circulo o Rectangulo); la llamada f.describir() → area() ejecuta LA VERSIÓN DE LA CLASE REAL del objeto. Aparece exactamente en el bucle for (Figura f : figuras).

¿Por qué new Figura("x") no compila? Porque Figura es abstracta: tiene métodos sin cuerpo (area, perimetro), así que un objeto Figura "a secas" estaría incompleto; solo se instancian sus hijas, que completan esos métodos.

interface Bonificable {
    double bonus();               // CONTRATO: quien lo implemente DEBE tener bonus()
}

abstract class Empleado {
    private String nombre;
    private double salarioBase;

    public Empleado(String nombre, double salarioBase) {
        this.nombre = nombre;
        this.salarioBase = salarioBase;
    }
    public String getNombre()      { return nombre; }
    public double getSalarioBase() { return salarioBase; }

    // SOBRECARGA (overloading): mismo nombre, PARÁMETROS distintos, misma clase
    public void subirSalario(double cantidad)     { salarioBase += cantidad; }
    public void subirSalario(double c, int veces) { salarioBase += c * veces; }

    // Cada tipo de empleado calcula su salario a su manera:
    public abstract double salarioMensual();

    @Override
    public String toString() {
        return nombre + " cobra " + salarioMensual() + " EUR";
    }
}

class EmpleadoFijo extends Empleado implements Bonificable {
    private int trienios;

    public EmpleadoFijo(String nombre, double salarioBase, int trienios) {
        super(nombre, salarioBase);
        this.trienios = trienios;
    }
    // SOBRESCRITURA (overriding): MISMA firma que el padre, redefinida en la hija
    @Override public double salarioMensual() {
        return getSalarioBase() + 50 * trienios + bonus();
    }
    @Override public double bonus() { return 100; }
}

class EmpleadoTemporal extends Empleado {
    private int horasExtra;

    public EmpleadoTemporal(String nombre, double salarioBase, int horasExtra) {
        super(nombre, salarioBase);
        this.horasExtra = horasExtra;
    }
    @Override public double salarioMensual() {
        return getSalarioBase() + 15 * horasExtra;
    }
}

public static void main(String[] args) {
    List<Empleado> plantilla = new ArrayList<>();
    plantilla.add(new EmpleadoFijo("Lucía", 1500, 2));
    plantilla.add(new EmpleadoTemporal("Marcos", 1100, 10));

    for (Empleado e : plantilla) {
        System.out.println(e);              // polimorfismo: cada uno usa SU salarioMensual()
        if (e instanceof Bonificable) {     // ¿cumple este objeto el contrato Bonificable?
            System.out.println("   (incluye bonus de " + ((Bonificable) e).bonus() + ")");
        }
    }
    plantilla.get(1).subirSalario(50);      // usa la sobrecarga de 1 parámetro
    plantilla.get(1).subirSalario(10, 3);   // usa la sobrecarga de 2 parámetros
    System.out.println("Marcos tras las subidas: " + plantilla.get(1).salarioMensual());
}

Lucía cobra 1700.0 EUR
   (incluye bonus de 100.0)
Marcos cobra 1250.0 EUR
Marcos tras las subidas: 1330.0

Comprobación de la salida: Lucía (fija) = 1500 + 50·2 + 100 de bonus = 1700. Marcos (temporal) = 1100 + 15·10 = 1250. Tras subirSalario(50) y subirSalario(10,3) su base pasa a 1100+50+30 = 1180 → salario 1180+150 = 1330. ✓

Sobrescritura (override): salarioMensual() se declara abstracto en el padre y cada hija lo redefine con LA MISMA firma; se decide en ejecución según el objeto. Sobrecarga (overload): subirSalario(double) y subirSalario(double,int) conviven en la misma clase con parámetros distintos; el compilador elige por los argumentos de la llamada.

a) Problemas de ProductoMal: con atributos public, cualquier código externo puede hacer m.precio = -999; o m.stock = -3; y el objeto queda en un estado absurdo sin que nadie lo detecte. Además, si mañana cambias cómo se guarda el precio, TODO el código externo que lo tocaba se rompe: no hay ningún punto único de control.

class Producto {
    private String nombre;    // privados: solo la propia clase los toca
    private double precio;
    private int stock;

    public Producto(String nombre, double precio, int stock) {
        this.nombre = nombre;
        setPrecio(precio);    // reutilizo la validación de los setters
        setStock(stock);
    }

    public String getNombre() { return nombre; }
    public double getPrecio() { return precio; }
    public int    getStock()  { return stock; }

    // SETTERS con validación: el objeto nunca queda en un estado absurdo
    public void setPrecio(double precio) {
        if (precio < 0) throw new IllegalArgumentException("Precio negativo: " + precio);
        this.precio = precio;
    }
    public void setStock(int stock) {
        if (stock < 0) throw new IllegalArgumentException("Stock negativo: " + stock);
        this.stock = stock;
    }

    public void vender(int unidades) {
        if (unidades <= 0 || unidades > stock) {
            System.out.println("Venta imposible de " + unidades + " uds de " + nombre);
            return;
        }
        stock -= unidades;
    }
}

public static void main(String[] args) {
    ProductoMal m = new ProductoMal();
    m.precio = -999;                 // ¡nadie lo impide! Estado absurdo permitido
    System.out.println("ProductoMal admite precio " + m.precio);

    Producto p = new Producto("Teclado", 25.5, 10);
    p.vender(3);
    System.out.println(p.getNombre() + ": quedan " + p.getStock() + " uds");
    p.vender(20);                    // venta imposible: se rechaza con un aviso
    try {
        p.setPrecio(-5);             // la validación lanza una excepción
    } catch (IllegalArgumentException e) {
        System.out.println("Rechazado: " + e.getMessage());
    }
    System.out.println("Precio final: " + p.getPrecio());
}

ProductoMal admite precio -999.0
Teclado: quedan 7 uds
Venta imposible de 20 uds de Teclado
Rechazado: Precio negativo: -5.0
Precio final: 25.5

c) Definiciones. Abstracción: quedarse con lo esencial de una entidad (qué operaciones ofrece) ocultando los detalles internos de cómo lo hace; en Java se plasma en clases, clases abstractas e interfaces (el "contrato" público). Encapsulación: proteger el estado interno declarando los atributos private y obligando a pasar por métodos públicos (getters/setters/operaciones) que validan; en Java se plasma con los modificadores de visibilidad. La abstracción decide QUÉ se ve; la encapsulación IMPIDE ver/tocar el resto.

(a)

public static int c1(int[] a) {
    int suma = 0;
    for (int i = 0; i < a.length; i++) {
        suma += a[i];
    }
    return suma;
}

n = a.length. Un solo bucle: i = 0,1,...,n-1 → n vueltas, con trabajo O(1) por vuelta (una suma y un acceso). Total n·O(1) → O(n).

(b)

public static int c2(int[] a, int x) {
    int veces = 0;
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < a.length && a[j] != x; j++) {
            veces++;
        }
    }
    return veces;
}

n = a.length. El externo da n vueltas SIEMPRE. El interno tiene la condición compuesta j < a.length && a[j] != x: peor caso (x no está en el array): el corte nunca actúa → n vueltas internas por cada externa → n·n = O(n²). Mejor caso (x está en a[0]): el interno corta a la primera comprobación → solo quedan las n vueltas del externo → O(n). Verificado en la ejecución: con n=6, peor caso 36 = 6² iteraciones internas; mejor caso 0.

(c)

public static long c3(int n) {
    long c = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                c++;
            }
        }
    }
    return c;
}

n = parámetro. Tres bucles anidados INDEPENDIENTES (cada uno da n vueltas, sin depender de los otros) → se multiplican: n·n·n = O(n³). Verificado: c3(10) = 1000.

(d)

public static int c4(int n) {
    int c = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            c++;
        }
    }
    return c;
}

n = parámetro. El interno DEPENDE del externo (j llega hasta i), así que no se multiplica: se SUMA el trabajo real: cuando i=1 → 1 vuelta; i=2 → 2; ...; i=n → n. Total = 1+2+...+n = n(n+1)/2 = n²/2 + n/2 → domina n² → O(n²). Verificado: c4(8) = 36 = 8·9/2.

(e)

public static int c5(int n) {
    int c = 0;
    for (int j = 1; j <= n; j *= 2) {
        c++;
    }
    return c;
}

n = parámetro. j no suma: SE MULTIPLICA por 2 (j = 1, 2, 4, ..., n) → da ⌊log₂ n⌋+1 vueltas → O(log n). Verificado: c5(1000) = 10 vueltas (2¹⁰=1024>1000).

(f)

public static int c6(int n) {
    int c = 0;
    for (int i = 1; i <= n; i *= 2) {
        for (int k = 0; k < n; k++) {
            c++;
        }
    }
    return c;
}

n = parámetro. Externo logarítmico (i se multiplica por 2 → log₂ n vueltas); interno SIEMPRE n vueltas (va hasta n, no depende de i) → anidados independientes → se multiplican: O(n log n). Verificado: c6(1000) = 10·1000 = 10 000.

(g)

public static int c7(int n) {
    int c = 0;
    for (int i = 1; i <= n; i *= 2) {
        for (int k = 0; k < i; k++) {
            c++;
        }
    }
    return c;
}

La trampa. Se parece a (f), pero el interno va hasta i, que vale 1, 2, 4, ..., n → DEPENDE del externo → hay que SUMAR: 1+2+4+...+n (suma geométrica) ≈ 2n → O(n), ¡no O(n log n)! Verificado: c7(1024) = 2047 ≈ 2·1024.

(h)

public static int c8(int n) {
    if (n <= 1) return 0;
    return 1 + c8(n / 2);
}

n = parámetro. Cada llamada hace trabajo O(1) y UNA llamada recursiva con n/2: n → n/2 → n/4 → ... → 1. Número de llamadas = cuántas veces se puede dividir n entre 2 = log₂ n → O(log n). Verificado: c8(1024) = 10.

(i)

public static long c9(int n) {
    if (n <= 1) return n;
    return c9(n - 1) + c9(n - 2);
}

n = parámetro. Cada llamada genera DOS llamadas (n-1 y n-2): el árbol de llamadas casi se duplica en cada nivel y tiene profundidad ≈n → del orden de 2ⁿ llamadas, cada una O(1) → O(2ⁿ) (exponencial). Es el Fibonacci ingenuo: c9(10)=55 es instantáneo, pero c9(60) sería inviable.

c1(a) = 32  (recorre las 6 posiciones una vez)
c2 PEOR caso, x=100 no está:  36 iteraciones (6x6 = n^2)
c2 MEJOR caso, x=3 el primero: 0 iteraciones (el bucle interno corta siempre)
c3(10)   = 1000  (10^3 = n^3)
c4(8)    = 36  (1+2+...+8 = 8*9/2 = 36 ~ n^2/2)
c5(1000) = 10  (1,2,4,...,512 -> ~log2 de n vueltas)
c6(1000) = 10000  (~log2(n) * n = 10 * 1000)
c7(1024) = 2047  (1+2+4+...+1024 = 2047 ~ 2n, ¡O(n), no n log n!)
c8(1024) = 10  (1024->512->...->1: log2(1024) = 10 llamadas)
c9(10)   = 55  (Fibonacci: el ARBOL de llamadas crece ~2^n)

a) Funcionamiento: en cada pasada se recorren los pares de VECINOS (a[j], a[j+1]) y se intercambian si están desordenados; así el mayor de la zona no ordenada "burbujea" hasta el final. Tras la pasada k, los k últimos elementos están en su posición definitiva; con n elementos bastan n-1 pasadas.

/** BURBUJA CLÁSICA: en cada pasada compara VECINOS y los intercambia si
 *  están desordenados; el mayor "burbujea" hasta el final del array. */
public static void burbuja(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {           // n-1 pasadas como máximo
        for (int j = 0; j < n - 1 - i; j++) {   // los i últimos YA están colocados
            if (a[j] > a[j + 1]) {              // vecinos desordenados...
                int tmp = a[j];                 // ...intercambio clásico con
                a[j] = a[j + 1];                //    variable temporal
                a[j + 1] = tmp;
            }
        }
        System.out.println("Tras la pasada " + (i + 1) + ": " + Arrays.toString(a));
    }
}

c) Traza sobre [1, 4, 8, 10, 2] (salida real): pasada 1: solo el par (10,2) se intercambia y el 10 llega al final; pasada 2: (8,2) se intercambian; pasada 3: (4,2) se intercambian y ya está ordenado; pasada 4: sin cambios.

BURBUJA CLÁSICA sobre [1, 4, 8, 10, 2]
Tras la pasada 1: [1, 4, 8, 2, 10]
Tras la pasada 2: [1, 4, 2, 8, 10]
Tras la pasada 3: [1, 2, 4, 8, 10]
Tras la pasada 4: [1, 2, 4, 8, 10]

BURBUJA MEJORADA sobre [1, 4, 8, 10, 2]
Tras la pasada 1: [1, 4, 8, 2, 10]
Tras la pasada 2: [1, 4, 2, 8, 10]
Tras la pasada 3: [1, 2, 4, 8, 10]
Tras la pasada 4: [1, 2, 4, 8, 10]   <- pasada sin cambios: ya ordenado, ¡PARO!

d) Las dos optimizaciones: (1) bandera de cambios (huboCambios): si una pasada completa no intercambia nada, el array ya está ordenado y se corta el bucle externo — en la traza real se ve cómo la mejorada anuncia "¡PARO!" en la pasada 4; (2) límite decreciente (j < n-1-i): los i últimos ya colocados no se recomparan. Con la bandera, el mejor caso pasa a ser O(n) (una sola pasada) y se da con el array YA ordenado. Peor y medio siguen siendo O(n²). Es estable (solo intercambia vecinos estrictamente desordenados).

/** BURBUJA MEJORADA. Dos optimizaciones:
 *  1) bandera huboCambios: si una pasada no intercambia nada, el array ya
 *     está ordenado y se PARA (mejor caso O(n));
 *  2) límite decreciente (n-1-i): la zona final ya ordenada no se revisita. */
public static void burbujaMejorada(int[] a) {
    int n = a.length;
    boolean huboCambios = true;
    for (int i = 0; i < n - 1 && huboCambios; i++) {
        huboCambios = false;                    // supongo que ya está ordenado
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                huboCambios = true;             // esta pasada SÍ tocó algo
            }
        }
        System.out.println("Tras la pasada " + (i + 1) + ": " + Arrays.toString(a)
                + (huboCambios ? "" : "   <- pasada sin cambios: ya ordenado, ¡PARO!"));
    }
}

a) En cada paso i, busca el MÍNIMO de la zona no ordenada (de i al final) y lo intercambia con la posición i: una colocación definitiva por pasada.

/** SELECCIÓN: busca el MÍNIMO de la zona sin ordenar y lo intercambia con
 *  la primera posición libre. Una colocación definitiva por pasada. */
public static void seleccion(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {       // posición que voy a rellenar
        int posMin = i;                     // candidato a mínimo
        for (int j = i + 1; j < n; j++) {   // busco el mínimo real del resto
            if (a[j] < a[posMin]) {
                posMin = j;
            }
        }
        int tmp = a[i];                     // intercambio el mínimo con a[i]
        a[i] = a[posMin];
        a[posMin] = tmp;
        System.out.println("Paso " + (i + 1) + ": coloco el mínimo " + a[i]
                + " en la posición " + i + " -> " + Arrays.toString(a));
    }
}

SELECCIÓN sobre [29, 10, 14, 37, 13]
Paso 1: coloco el mínimo 10 en la posición 0 -> [10, 29, 14, 37, 13]
Paso 2: coloco el mínimo 13 en la posición 1 -> [10, 13, 14, 37, 29]
Paso 3: coloco el mínimo 14 en la posición 2 -> [10, 13, 14, 37, 29]
Paso 4: coloco el mínimo 29 en la posición 3 -> [10, 13, 14, 29, 37]

c) Es O(n²) incluso con el array ordenado porque para saber cuál es el mínimo siempre tiene que mirar toda la zona restante: (n-1)+(n-2)+...+1 = n(n-1)/2 comparaciones pase lo que pase (no hay "atajo" tipo bandera). Su ventaja: hace como mucho n-1 intercambios, el mínimo posible — interesa cuando MOVER un elemento es muy caro. No es estable (el intercambio a distancia puede saltar por encima de un elemento igual).

a) Como ordenar cartas: la zona izquierda se mantiene siempre ordenada; se toma el siguiente elemento (valor) y se desplazan una posición a la derecha todos los mayores que él, hasta encontrar su hueco.

/** INSERCIÓN: mantiene ordenada la zona izquierda; toma el siguiente
 *  elemento y lo desplaza hacia atrás hasta su sitio (como ordenar cartas). */
public static void insercion(int[] a) {
    for (int i = 1; i < a.length; i++) {    // a[0] ya es una "zona ordenada" de 1
        int valor = a[i];                   // elemento a colocar
        int j = i - 1;
        while (j >= 0 && a[j] > valor) {    // mientras el de la izquierda sea mayor...
            a[j + 1] = a[j];                // ...lo desplazo un hueco a la derecha
            j--;
        }
        a[j + 1] = valor;                   // hueco encontrado: inserto el valor
        System.out.println("Inserto " + valor + " -> " + Arrays.toString(a));
    }
}

INSERCIÓN sobre [25, 9, 14, 3, 20]
Inserto 9 -> [9, 25, 14, 3, 20]
Inserto 14 -> [9, 14, 25, 3, 20]
Inserto 3 -> [3, 9, 14, 25, 20]
Inserto 20 -> [3, 9, 14, 20, 25]

c) Mejor caso O(n): con el array YA ordenado (o casi), el while no desplaza nada y cada elemento cuesta O(1); por eso inserción es ideal para arrays casi ordenados o pequeños. Peor caso O(n²): array en orden inverso (cada elemento recorre toda la zona ordenada). Es estable: la condición a[j] > valor (estricta) nunca cruza dos iguales.

a) Divide y vencerás: (1) DIVIDE el array por la mitad recursivamente hasta trozos de 1 elemento (que ya están ordenados por definición); (2) MEZCLA los trozos de dos en dos comparando sus cabezas y copiando siempre la menor.

/** MERGESORT (divide y vencerás):
 *  1) DIVIDE el trozo por la mitad hasta llegar a trozos de 1 elemento;
 *  2) MEZCLA (merge) los trozos de dos en dos, que ya vienen ordenados. */
public static void mergeSort(int[] a, int ini, int fin) {
    if (ini >= fin) return;             // CASO BASE: 0 o 1 elementos -> ya ordenado
    int mid = (ini + fin) / 2;          // punto de corte
    mergeSort(a, ini, mid);             // 1) ordeno la mitad izquierda
    mergeSort(a, mid + 1, fin);         // 2) ordeno la mitad derecha
    merge(a, ini, mid, fin);            // 3) mezclo ambas mitades ya ordenadas
    System.out.println("MEZCLO a[" + ini + ".." + fin + "] -> " + trozo(a, ini, fin));
}

/** Mezcla dos zonas YA ordenadas: a[ini..mid] y a[mid+1..fin]. */
public static void merge(int[] a, int ini, int mid, int fin) {
    int[] aux = new int[fin - ini + 1];     // array auxiliar: la memoria O(n) extra
    int i = ini, j = mid + 1, k = 0;

    while (i <= mid && j <= fin) {          // comparo las CABEZAS, copio la menor
        if (a[i] <= a[j]) {                 // el <= hace a Mergesort ESTABLE
            aux[k++] = a[i++];
        } else {
            aux[k++] = a[j++];
        }
    }
    while (i <= mid) aux[k++] = a[i++];     // restos de la izquierda (si quedan)
    while (j <= fin) aux[k++] = a[j++];     // restos de la derecha (si quedan)

    for (k = 0; k < aux.length; k++) {      // vuelco el auxiliar al array original
        a[ini + k] = aux[k];
    }
}

c) Traza sobre [31, 7, 24, 9, 15, 2]. Divisiones: [31 7 24 | 9 15 2]; [31 7 | 24]; [31 | 7]; [9 15 | 2]; [9 | 15]. Mezclas (salida real, de abajo arriba):

MERGESORT sobre [31, 7, 24, 9, 15, 2]
MEZCLO a[0..1] -> [7 31]
MEZCLO a[0..2] -> [7 24 31]
MEZCLO a[3..4] -> [9 15]
MEZCLO a[3..5] -> [2 9 15]
MEZCLO a[0..5] -> [2 7 9 15 24 31]
Resultado final: [2, 7, 9, 15, 24, 31]

d) ¿Por qué O(n log n) SIEMPRE? El array se divide por la mitad hasta profundidad log₂ n (niveles), y en cada nivel el conjunto de mezclas toca cada posición una vez → O(n) por nivel × log₂ n niveles = O(n log n), sin depender de cómo vengan los datos (divide SIEMPRE por la mitad). Gasta O(n) de memoria extra (el array aux). Estable: cuando las cabezas empatan, el if (a[i] <= a[j]) copia primero la de la IZQUIERDA, conservando el orden relativo original de los iguales — esa línea del merge es la que garantiza la estabilidad.

a) Se elige un PIVOTE y se PARTICIONA el trozo: menores a la izquierda, mayores a la derecha; el pivote queda COLOCADO en su posición definitiva y se repite en cada lado. Diferencia con Mergesort: Quicksort hace el trabajo ANTES de las llamadas recursivas (particionar) y no necesita fase de combinación; Mergesort trabaja DESPUÉS (mezclar).

/** QUICKSORT (divide y vencerás, al revés que Mergesort: el trabajo se hace
 *  ANTES de las llamadas recursivas, en la partición):
 *  1) elige un PIVOTE (aquí, el primer elemento del trozo);
 *  2) PARTICIONA: menores a su izquierda, mayores a su derecha
 *     -> el pivote queda COLOCADO en su posición definitiva;
 *  3) repite recursivamente en el trozo izquierdo y en el derecho. */
public static void quickSort(int[] a, int ini, int fin) {
    if (ini >= fin) return;                 // CASO BASE: 0 o 1 elementos
    int p = particionar(a, ini, fin);       // coloca el pivote y devuelve su posición
    quickSort(a, ini, p - 1);               // ordeno los menores
    quickSort(a, p + 1, fin);               // ordeno los mayores
}

/** Partición con pivote = a[ini]. 'i' marca la frontera de los menores:
 *  tras el bucle, todo lo de ini+1..i es menor que el pivote. */
public static int particionar(int[] a, int ini, int fin) {
    int pivote = a[ini];
    int i = ini;                            // frontera de la zona de menores
    for (int j = ini + 1; j <= fin; j++) {
        if (a[j] < pivote) {                // a[j] es menor -> lo paso a la
            i++;                            //    zona de menores
            intercambiar(a, i, j);
        }
    }
    intercambiar(a, ini, i);                // el pivote, a su sitio definitivo
    System.out.println("Partición de a[" + ini + ".." + fin + "], pivote " + pivote
            + " queda en la posición " + i + " -> " + Arrays.toString(a));
    return i;
}

static void intercambiar(int[] a, int x, int y) {
    int t = a[x]; a[x] = a[y]; a[y] = t;
}

c) Traza sobre [35, 12, 48, 7, 29, 50, 18] (salida real): pivote 35 → menores {18,12,7,29} | 35 | mayores {50,48}; en el trozo izquierdo pivote 18 → {7,12} | 18 | {29}; pivote 7 → {} | 7 | {12}; en el derecho pivote 50 → {48} | 50 | {}.

QUICKSORT sobre [35, 12, 48, 7, 29, 50, 18]
Partición de a[0..6], pivote 35 queda en la posición 4 -> [18, 12, 7, 29, 35, 50, 48]
Partición de a[0..3], pivote 18 queda en la posición 2 -> [7, 12, 18, 29, 35, 50, 48]
Partición de a[0..1], pivote 7 queda en la posición 0 -> [7, 12, 18, 29, 35, 50, 48]
Partición de a[5..6], pivote 50 queda en la posición 6 -> [7, 12, 18, 29, 35, 48, 50]
Resultado final: [7, 12, 18, 29, 35, 48, 50]

d) Peor caso O(n²): cuando el pivote cae siempre en un extremo de su trozo, las particiones quedan de tamaños 0 y n-1 y hay n niveles de O(n) → n². Con pivote = primer elemento lo provoca un array ya ordenado (o inverso). Se evita eligiendo pivote aleatorio o la "mediana de tres" (primero, central, último). Caso medio y mejor: O(n log n); no es estable; memoria O(log n) por la pila de recursión.

a) Un max-heap es un árbol binario casi completo donde CADA padre ≥ sus hijos; guardado en el propio array: los hijos de la posición i están en 2i+1 y 2i+2 (y el padre de j en (j-1)/2). El máximo queda siempre en la raíz a[0].

/** HEAPSORT: usa un MAX-HEAP (montículo binario donde cada padre es MAYOR
 *  o igual que sus hijos, guardado en el propio array: hijos de i en 2i+1 y 2i+2).
 *  FASE 1: construir el montículo -> el máximo queda en a[0].
 *  FASE 2: intercambiar a[0] con el último, encoger el montículo y reparar. */
public static void heapSort(int[] a) {
    int n = a.length;
    // FASE 1: construir el max-heap hundiendo desde el último padre hacia la raíz
    for (int i = n / 2 - 1; i >= 0; i--) {
        hundir(a, n, i);
    }
    System.out.println("Montículo construido: " + Arrays.toString(a));

    // FASE 2: extraer el máximo n-1 veces
    for (int fin = n - 1; fin > 0; fin--) {
        int tmp = a[0]; a[0] = a[fin]; a[fin] = tmp;  // máximo -> al final
        hundir(a, fin, 0);                            // reparo el montículo restante
        System.out.println("Extraigo " + a[fin] + " -> " + Arrays.toString(a)
                + "  (ordenado desde la posición " + fin + ")");
    }
}

/** "Hunde" el nodo i: mientras algún hijo sea mayor que él, se intercambia
 *  con el mayor de sus hijos (n = tamaño actual del montículo). */
private static void hundir(int[] a, int n, int i) {
    int mayor = i;
    int izq = 2 * i + 1;                    // hijo izquierdo
    int der = 2 * i + 2;                    // hijo derecho
    if (izq < n && a[izq] > a[mayor]) mayor = izq;
    if (der < n && a[der] > a[mayor]) mayor = der;
    if (mayor != i) {                       // algún hijo le gana ->
        int tmp = a[i]; a[i] = a[mayor]; a[mayor] = tmp;
        hundir(a, n, mayor);                // sigo hundiendo más abajo
    }
}

c) Traza sobre [19, 4, 27, 11, 8] (salida real). Construcción: se hunde desde el último padre (posición 1) hacia la raíz → queda [27, 11, 19, 4, 8]. Después, 4 extracciones: el máximo se intercambia con la última posición del montículo y se repara con hundir:

HEAPSORT sobre [19, 4, 27, 11, 8]
Montículo construido: [27, 11, 19, 4, 8]
Extraigo 27 -> [19, 11, 8, 4, 27]  (ordenado desde la posición 4)
Extraigo 19 -> [11, 4, 8, 19, 27]  (ordenado desde la posición 3)
Extraigo 11 -> [8, 4, 11, 19, 27]  (ordenado desde la posición 2)
Extraigo 8 -> [4, 8, 11, 19, 27]  (ordenado desde la posición 1)
Resultado final: [4, 8, 11, 19, 27]

d) Complejidad: construir el montículo es O(n) (hundir desde n/2 posiciones, la mayoría cerca de las hojas); la fase de extracción son n-1 intercambios con reparación O(log n) cada uno → total O(n log n) en TODOS los casos. Ventaja sobre Mergesort: no gasta memoria extra (ordena dentro del propio array, O(1) adicional). No es estable.

a) Mejora la inserción atacando su punto débil: mover elementos de 1 en 1. Los gaps son las distancias de comparación: se hacen pasadas de inserción comparando elementos a distancia gap (n/2, luego n/4, ..., hasta 1); con gaps grandes los elementos lejanos viajan rápido hacia su zona, y el pase final con gap = 1 es una inserción normal sobre un array ya casi ordenado (su mejor escenario, cercano a O(n)).

/** SHELLSORT: es una INSERCIÓN mejorada. Compara elementos separados por un
 *  SALTO (gap) que empieza grande (n/2) y se va reduciendo a la mitad hasta 1.
 *  Con gap grande, los elementos lejanos de su sitio viajan rápido; el último
 *  pase (gap=1) es una inserción normal sobre una lista ya casi ordenada. */
public static void shellSort(int[] a) {
    int n = a.length;
    for (int gap = n / 2; gap >= 1; gap /= 2) {   // gaps: n/2, n/4, ..., 1
        for (int i = gap; i < n; i++) {           // inserción "a saltos de gap"
            int valor = a[i];
            int j = i;
            while (j >= gap && a[j - gap] > valor) {
                a[j] = a[j - gap];                // desplazo gap posiciones
                j -= gap;
            }
            a[j] = valor;
        }
        System.out.println("Tras el pase con gap " + gap + ": " + Arrays.toString(a));
    }
}

SHELLSORT sobre [45, 23, 67, 12, 38, 7]
Tras el pase con gap 3: [12, 23, 7, 45, 38, 67]
Tras el pase con gap 1: [7, 12, 23, 38, 45, 67]

Lectura: con n = 6 los gaps son 3 y 1. El pase de gap 3 compara las parejas (45,12), (23,38), (67,7) y deja [12, 23, 7, 45, 38, 67]; el pase final de gap 1 remata como inserción normal.

a) Respuesta: d) TreeSet. Cumple los TRES requisitos: es un Set (rechaza duplicados por definición), mantiene los elementos siempre ordenados automáticamente tras cada inserción (internamente es un árbol rojo-negro: un ABB equilibrado), y sus operaciones add/contains/ remove son O(log n) garantizado.

Por qué las otras NO valen (obligatorio para la máxima puntuación):

b) Demostración en código (ejecutada):

public static void demoTreeSet() {
    TreeSet<Integer> ids = new TreeSet<>();     // sin duplicados + SIEMPRE ordenado
    ids.add(50);
    ids.add(20);
    ids.add(70);
    System.out.println("¿Se añade 20 otra vez? " + ids.add(20));  // false: duplicado
    System.out.println("Contenido (orden automático): " + ids);
    System.out.println("¿Contiene 70? " + ids.contains(70) + "  (búsqueda O(log n))");
    System.out.println("Menor: " + ids.first() + " | Mayor: " + ids.last());
}

¿Se añade 20 otra vez? false
Contenido (orden automático): [20, 50, 70]
¿Contiene 70? true  (búsqueda O(log n))
Menor: 20 | Mayor: 70

Marta aparece 1 veces
Ana aparece 3 veces
Luis aparece 2 veces

class PilaArray {
    private int[] datos;      // almacén de los elementos
    private int tope;         // índice de la CIMA (-1 = pila vacía)

    public PilaArray(int capacidad) {
        datos = new int[capacidad];
        tope = -1;
    }
    public boolean estaVacia() { return tope == -1; }
    public boolean estaLlena() { return tope == datos.length - 1; }

    public void push(int e) {                    // apilar: O(1)
        if (estaLlena()) throw new RuntimeException("Pila llena");
        datos[++tope] = e;                       // avanzo el tope y guardo encima
    }
    public int pop() {                           // desapilar: O(1)
        if (estaVacia()) throw new RuntimeException("Pila vacía");
        return datos[tope--];                    // devuelvo la cima y retrocedo
    }
    public int peek() {                          // consultar la cima sin sacarla: O(1)
        if (estaVacia()) throw new RuntimeException("Pila vacía");
        return datos[tope];
    }
}

Complejidades: push, pop, peek, estaVacia y estaLlena son todas O(1): solo tocan la casilla del tope, sin recorrer nada. datos[++tope] = e primero avanza el tope y luego guarda; datos[tope--] devuelve la cima y luego retrocede.

/** Comprueba con una PILA si (), [] y {} están correctamente equilibrados. */
public static boolean equilibrada(String expr) {
    Deque<Character> pila = new ArrayDeque<>();
    for (int i = 0; i < expr.length(); i++) {
        char c = expr.charAt(i);
        if (c == '(' || c == '[' || c == '{') {
            pila.push(c);                       // apertura: la apilo
        } else if (c == ')' || c == ']' || c == '}') {
            if (pila.isEmpty()) return false;   // cierre sin pareja pendiente
            char abre = pila.pop();             // debe casar con la ÚLTIMA apertura
            if ((c == ')' && abre != '(') ||
                (c == ']' && abre != '[') ||
                (c == '}' && abre != '{')) {
                return false;                   // cierra un símbolo que no toca
            }
        }
    }
    return pila.isEmpty();      // si sobra alguna apertura, NO está equilibrada
}

peek: 8
pop:  8
pop:  3
pop:  5
¿vacía? true

{[()]}  -> true
([)]    -> false
(((     -> false

c) ¿Por qué una pila? Porque el ÚLTIMO símbolo abierto es el PRIMERO que debe cerrarse (anidamiento = LIFO puro). La pila recuerda las aperturas pendientes en el orden exacto en que deben resolverse: cada cierre debe casar con la cima. Los tres fallos posibles: cerrar sin nada pendiente (pop sobre vacía), cerrar con un símbolo que no casa, o terminar con aperturas sin cerrar (pila no vacía al final).

class ColaEnlazada {
    private static class Nodo {
        String dato;
        Nodo siguiente;
        Nodo(String dato) { this.dato = dato; }
    }

    private Nodo primero;   // FRENTE: por aquí se SACA
    private Nodo ultimo;    // FINAL:  por aquí se METE
    private int n;          // contador de elementos

    public boolean estaVacia() { return primero == null; }
    public int tamano()        { return n; }

    public void encolar(String e) {              // O(1) gracias a 'ultimo'
        Nodo nuevo = new Nodo(e);
        if (estaVacia()) {
            primero = nuevo;                     // cola vacía: el nuevo es a la vez
        } else {                                 //   el primero...
            ultimo.siguiente = nuevo;            // si no, el antiguo último lo engancha
        }
        ultimo = nuevo;                          // ...y el último
        n++;
    }

    public String desencolar() {                 // O(1)
        if (estaVacia()) throw new RuntimeException("Cola vacía");
        String dato = primero.dato;
        primero = primero.siguiente;             // el segundo pasa a ser el frente
        if (primero == null) ultimo = null;      // quedó vacía: cuidar también 'ultimo'
        n--;
        return dato;
    }

    public String frente() {                     // consultar sin sacar: O(1)
        if (estaVacia()) throw new RuntimeException("Cola vacía");
        return primero.dato;
    }
}

El papel de ultimo: sin esa referencia, encolar exigiría recorrer toda la lista hasta el final (O(n)); con ella se engancha directamente el nuevo nodo → O(1). Casos especiales: al encolar en vacía, el nuevo nodo es a la vez primero y último; al desencolar el último elemento hay que poner ultimo = null también (si no, quedaría apuntando a un nodo "fantasma").

public static void main(String[] args) {
    ColaEnlazada c = new ColaEnlazada();
    c.encolar("Ana");
    c.encolar("Luis");
    System.out.println("desencolar: " + c.desencolar());   // sale Ana (la primera)
    c.encolar("Marta");
    c.encolar("Pedro");
    System.out.println("frente:     " + c.frente());       // Luis, sin sacarlo
    System.out.println("desencolar: " + c.desencolar());
    System.out.println("desencolar: " + c.desencolar());
    System.out.println("quedan " + c.tamano() + " -> frente: " + c.frente());
}

desencolar: Ana
frente:     Luis
desencolar: Luis
desencolar: Marta
quedan 1 -> frente: Pedro

b) Traza razonada: entra Ana, entra Luis → desencolar saca a Ana (la primera en llegar); entran Marta y Pedro; frente() mira a Luis sin sacarlo; los dos desencolar siguientes sacan Luis y Marta; queda [Pedro]. c) LIFO (Last In First Out) = pila: el último en entrar sale primero. FIFO (First In First Out) = cola: el primero en entrar sale primero.

a) Gestión de referencias al insertar entre dos nodos A y B: cada nodo tiene DOS flechas (anterior y siguiente), así que insertar exige dejar coherentes 4 referencias: (1) nuevo.anterior = A; (2) nuevo.siguiente = B; (3) B.anterior = nuevo; (4) A.siguiente = nuevo. El orden importa: primero se conectan las flechas del NUEVO (mientras A y B todavía se apuntan entre sí) y después se redirigen las de los vecinos; si haces (4) antes de leer A.siguiente, pierdes el acceso a B. Casos especiales: lista vacía (el nuevo es primero y último), insertar al principio (no hay A: se actualiza primero) e insertar al final (no hay B: se actualiza ultimo).

class ListaDoble {
    static class Nodo {
        int dato;
        Nodo anterior;    // flecha hacia atrás
        Nodo siguiente;   // flecha hacia delante
        Nodo(int dato) { this.dato = dato; }
    }

    private Nodo primero, ultimo;

    /** Inserta al principio: O(1). */
    public void insertarPrincipio(int valor) {
        Nodo nuevo = new Nodo(valor);
        if (primero == null) {            // CASO ESPECIAL: lista vacía
            primero = ultimo = nuevo;
            return;
        }
        nuevo.siguiente = primero;        // 1) el nuevo mira adelante al antiguo primero
        primero.anterior = nuevo;         // 2) el antiguo primero mira atrás al nuevo
        primero = nuevo;                  // 3) actualizo la cabeza
    }

    /** Inserta al final: O(1) gracias a la referencia 'ultimo'. */
    public void insertarFinal(int valor) {
        Nodo nuevo = new Nodo(valor);
        if (ultimo == null) {
            primero = ultimo = nuevo;
            return;
        }
        nuevo.anterior = ultimo;          // 1) el nuevo mira atrás al antiguo último
        ultimo.siguiente = nuevo;         // 2) el antiguo último mira adelante al nuevo
        ultimo = nuevo;                   // 3) actualizo la cola
    }

    /** Inserta 'valor' justo DESPUÉS del primer nodo que contenga 'ref'.
     *  Hay que reajustar 4 referencias: las 2 del nuevo y una de cada vecino. */
    public boolean insertarDespuesDe(int ref, int valor) {
        Nodo actual = primero;
        while (actual != null && actual.dato != ref) {
            actual = actual.siguiente;    // busco el nodo de referencia: O(n)
        }
        if (actual == null) return false; // 'ref' no está en la lista

        Nodo nuevo = new Nodo(valor);
        nuevo.anterior = actual;               // 1) nuevo mira atrás a 'actual'
        nuevo.siguiente = actual.siguiente;    // 2) nuevo mira adelante al que seguía
        if (actual.siguiente != null) {
            actual.siguiente.anterior = nuevo; // 3) el vecino derecho mira atrás al nuevo
        } else {
            ultimo = nuevo;                    //    (no había vecino: nuevo es el último)
        }
        actual.siguiente = nuevo;              // 4) 'actual' mira adelante al nuevo
        return true;
    }

    /** Elimina el primer nodo con ese valor "puenteándolo" entre sus vecinos. */
    public boolean eliminar(int valor) {
        Nodo actual = primero;
        while (actual != null && actual.dato != valor) {
            actual = actual.siguiente;
        }
        if (actual == null) return false;      // no estaba

        if (actual.anterior != null) {
            actual.anterior.siguiente = actual.siguiente;
        } else {
            primero = actual.siguiente;        // era el primero
        }
        if (actual.siguiente != null) {
            actual.siguiente.anterior = actual.anterior;
        } else {
            ultimo = actual.anterior;          // era el último
        }
        return true;
    }

    public void imprimirAdelante() {
        StringBuilder sb = new StringBuilder("primero -> ");
        for (Nodo a = primero; a != null; a = a.siguiente) {
            sb.append(a.dato).append(" <-> ");
        }
        System.out.println(sb.append("null"));
    }

    public void imprimirAtras() {
        StringBuilder sb = new StringBuilder("ultimo  -> ");
        for (Nodo a = ultimo; a != null; a = a.anterior) {
            sb.append(a.dato).append(" <-> ");
        }
        System.out.println(sb.append("null"));
    }
}

public static void main(String[] args) {
    ListaDoble lista = new ListaDoble();
    lista.insertarFinal(10);
    lista.insertarFinal(20);
    lista.insertarFinal(40);
    lista.insertarDespuesDe(20, 30);       // inserta 30 entre 20 y 40
    lista.insertarPrincipio(5);
    lista.imprimirAdelante();
    lista.imprimirAtras();                 // comprobar las flechas 'anterior'
    System.out.println("eliminar(40): " + lista.eliminar(40));
    System.out.println("eliminar(99): " + lista.eliminar(99));
    lista.imprimirAdelante();
    lista.imprimirAtras();
}

primero -> 5 <-> 10 <-> 20 <-> 30 <-> 40 <-> null
ultimo  -> 40 <-> 30 <-> 20 <-> 10 <-> 5 <-> null
eliminar(40): true
eliminar(99): false
primero -> 5 <-> 10 <-> 20 <-> 30 <-> null
ultimo  -> 30 <-> 20 <-> 10 <-> 5 <-> null

Comprobación: imprimirAtras() muestra 40, 30, 20, 10, 5: las flechas anterior están perfectas (es el espejo exacto del recorrido hacia delante). Al eliminar, el nodo se "puentea": su anterior pasa a apuntar a su siguiente y viceversa, con los casos especiales de ser el primero o el último.

class ABB {
    private static class Nodo {
        int dato;
        Nodo izquierdo, derecho;
        Nodo(int dato) { this.dato = dato; }
    }

    private Nodo raiz;

    /** Método público "lanzadera" + método privado recursivo (patrón habitual). */
    public void insertar(int valor) {
        raiz = insertar(raiz, valor);
    }
    private Nodo insertar(Nodo actual, int valor) {
        if (actual == null) {                   // CASO BASE: hueco encontrado
            return new Nodo(valor);
        }
        if (valor < actual.dato) {              // menores -> subárbol izquierdo
            actual.izquierdo = insertar(actual.izquierdo, valor);
        } else if (valor > actual.dato) {       // mayores -> subárbol derecho
            actual.derecho = insertar(actual.derecho, valor);
        }                                       // iguales: no se insertan (sin duplicados)
        return actual;
    }

    /** Búsqueda: aprovecha el orden del ABB, NO recorre todo el árbol. */
    public boolean buscar(int valor) {
        Nodo actual = raiz;
        while (actual != null) {
            System.out.print("visito " + actual.dato + "  ");
            if (valor == actual.dato) {
                System.out.println("-> ¡encontrado!");
                return true;
            }
            actual = (valor < actual.dato) ? actual.izquierdo : actual.derecho;
        }
        System.out.println("-> no está");
        return false;
    }

    // Los TRES recorridos: solo cambia DÓNDE se procesa la raíz
    public void preorden()  { preorden(raiz);  System.out.println(); }
    private void preorden(Nodo n) {
        if (n == null) return;                  // caso base ¡SIEMPRE!
        System.out.print(n.dato + " ");         // Raíz, Izquierda, Derecha
        preorden(n.izquierdo);
        preorden(n.derecho);
    }

    public void inorden()   { inorden(raiz);   System.out.println(); }
    private void inorden(Nodo n) {
        if (n == null) return;
        inorden(n.izquierdo);                   // Izquierda, Raíz, Derecha
        System.out.print(n.dato + " ");
        inorden(n.derecho);
    }

    public void postorden() { postorden(raiz); System.out.println(); }
    private void postorden(Nodo n) {
        if (n == null) return;
        postorden(n.izquierdo);                 // Izquierda, Derecha, Raíz
        postorden(n.derecho);
        System.out.print(n.dato + " ");
    }
}

c) El árbol que resulta de insertar 45, 23, 67, 12, 38, 51, 89, 30:

            45
          /    \
       23        67
      /  \      /  \
    12    38  51    89
         /
       30

public static void main(String[] args) {
    ABB arbol = new ABB();
    int[] valores = {45, 23, 67, 12, 38, 51, 89, 30};
    for (int v : valores) {
        arbol.insertar(v);
    }
    System.out.print("Preorden:  "); arbol.preorden();
    System.out.print("Inorden:   "); arbol.inorden();     // ¡sale ORDENADO!
    System.out.print("Postorden: "); arbol.postorden();
    System.out.println();
    System.out.println("Buscar 30:");
    arbol.buscar(30);
    System.out.println("Buscar 99:");
    arbol.buscar(99);
}

Preorden:  45 23 12 38 30 67 51 89 
Inorden:   12 23 30 38 45 51 67 89 
Postorden: 12 30 38 23 51 89 67 45 

Buscar 30:
visito 45  visito 23  visito 38  visito 30  -> ¡encontrado!
Buscar 99:
visito 45  visito 67  visito 89  -> no está

d) El inorden de un ABB sale ordenado de menor a mayor (12 23 30 38 45 51 67 89 ✓): el recorrido procesa primero todo lo menor (subárbol izquierdo), luego el nodo, luego lo mayor — exactamente la regla del ABB aplicada recursivamente. Sirve para comprobar tu árbol. Búsqueda de 30: 45 (30<45, izquierda) → 23 (30>23, derecha) → 38 (30<38, izquierda) → 30 ✓ — 4 comparaciones, coincide con la salida. Complejidad: O(altura); este árbol está razonablemente equilibrado (altura 4 con 8 nodos → ≈O(log n)). Si los 8 valores se insertaran en orden creciente (12, 23, 30, ...), cada uno caería siempre a la DERECHA del anterior: árbol degenerado en lista diagonal de altura 8 → buscar sería O(n).

/** Cuenta cuántas veces aparece cada nombre usando un Map. */
public static Map<String, Integer> frecuencias(String[] nombres) {
    Map<String, Integer> frec = new HashMap<>();
    for (String s : nombres) {
        // si no estaba, parte de 0; si estaba, coge su valor actual y suma 1
        frec.put(s, frec.getOrDefault(s, 0) + 1);
    }
    return frec;
}

¿Se añade 20 otra vez? false
Contenido (orden automático): [20, 50, 70]
¿Contiene 70? true  (búsqueda O(log n))
Menor: 20 | Mayor: 70

Marta aparece 1 veces
Ana aparece 3 veces
Luis aparece 2 veces

b) Con dos ArrayList paralelos, para cada nombre habría que BUSCARLO primero en la lista (O(n)) y mantener los índices sincronizados a mano (frágil). El Map asocia directamente clave→valor: put y get son O(1) de media gracias a la tabla hash: hashCode() de la clave se convierte en el índice de una casilla del array interno, y se va directo a ella sin buscar. Colisión: dos claves distintas caen en la misma casilla; se resuelve encadenando en esa casilla una pequeña lista de nodos (encadenamiento separado). Nota: un HashMap no garantiza ningún orden de recorrido, como se ve en la salida.

/** BÚSQUEDA LINEAL: mira las casillas una a una. Vale para arrays SIN ordenar. */
public static int busquedaLineal(int[] a, int x) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == x) return i;    // encontrado: devuelvo su posición
    }
    return -1;                      // recorrido entero sin éxito
}

/** BÚSQUEDA BINARIA (exige array ORDENADO): mira el centro y descarta
 *  media tabla en cada paso -> O(log n). */
public static int busquedaBinaria(int[] a, int x) {
    int ini = 0, fin = a.length - 1;
    while (ini <= fin) {                    // mientras quede zona por mirar
        int mid = (ini + fin) / 2;          // posición central
        System.out.println("  miro a[" + mid + "] = " + a[mid]);
        if (a[mid] == x) return mid;        // ¡es él!
        if (a[mid] < x) ini = mid + 1;      // x está a la DERECHA: descarto mitad izq.
        else            fin = mid - 1;      // x está a la IZQUIERDA: descarto mitad der.
    }
    return -1;                              // la zona se agotó: no está
}

Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Lineal, buscar 23  -> posición 5
Binaria, buscar 23:
  miro a[4] = 16
  miro a[7] = 56
  miro a[5] = 23
  -> posición 5
Binaria, buscar 7:
  miro a[4] = 16
  miro a[1] = 5
  miro a[2] = 8
  -> posición -1
Binaria recursiva, buscar 91 -> posición 9

b) Trazas (coinciden con la salida): buscar 23: mid=4 (a[4]=16 < 23, voy a la derecha) → mid=7 (a[7]=56 > 23, izquierda) → mid=5 (a[5]=23 ✓) — 3 comparaciones. Buscar 7: mid=4 (16>7, izquierda) → mid=1 (5<7, derecha) → mid=2 (8>7, izquierda) → ini>fin → devuelve -1.

c) La binaria descarta media zona en cada paso ASUMIENDO que todo lo anterior al centro es menor y todo lo posterior es mayor: eso solo es verdad si el array está ordenado; si no, podría descartar la mitad donde está x. Cada comparación divide la zona por 2: de n a 1 hay log₂ n pasos → O(log n). Con n = 1000: ⌈log₂ 1000⌉ = 10 comparaciones como máximo (2¹⁰ = 1024).

/** La misma idea, en versión RECURSIVA. */
public static int busquedaBinariaRec(int[] a, int x, int ini, int fin) {
    if (ini > fin) return -1;               // CASO BASE 1: zona vacía -> no está
    int mid = (ini + fin) / 2;
    if (a[mid] == x) return mid;            // CASO BASE 2: encontrado
    if (a[mid] < x) {
        return busquedaBinariaRec(a, x, mid + 1, fin);   // mitad derecha
    }
    return busquedaBinariaRec(a, x, ini, mid - 1);       // mitad izquierda
}

Los dos casos base: (1) ini > fin: la zona de búsqueda se quedó vacía → x no está, devuelve -1; (2) a[mid] == x: encontrado, devuelve mid. b) Si el array no está ordenado, el método NO lo detecta: sigue descartando mitades según sus comparaciones y puede devolver -1 aunque x esté en el array (o encontrarlo "de suerte"). La precondición de orden es responsabilidad de quien llama.

/** n! = n * (n-1) * ... * 2 * 1. Versión recursiva. */
public static long factorial(int n) {
    if (n <= 1) return 1;             // CASO BASE: detiene la recursión
    return n * factorial(n - 1);      // CASO RECURSIVO: problema más pequeño
}

b) Traza de factorial(4): se apilan factorial(4) → factorial(3) → factorial(2) → factorial(1); factorial(1) toca el caso base y devuelve 1; al deshacerse la pila: factorial(2) = 2·1 = 2; factorial(3) = 3·2 = 6; factorial(4) = 4·6 = 24. Verificado con la versión que imprime su propia pila:

/** Igual que factorial, pero imprimiendo la pila de llamadas. */
public static long factorialTraza(int n, String sangria) {
    System.out.println(sangria + "entra factorial(" + n + ")");
    if (n <= 1) {
        System.out.println(sangria + "caso base -> devuelve 1");
        return 1;
    }
    long resultado = n * factorialTraza(n - 1, sangria + "   ");
    System.out.println(sangria + "devuelve " + n + " * factorial(" + (n - 1)
            + ") = " + resultado);
    return resultado;
}

/** Suma recursiva: el elemento i + la suma del resto del array. */
public static int sumaArray(int[] a, int i) {
    if (i == a.length) return 0;          // CASO BASE: no quedan elementos
    return a[i] + sumaArray(a, i + 1);    // primero + suma del resto
}

Traza de factorial(4):
entra factorial(4)
   entra factorial(3)
      entra factorial(2)
         entra factorial(1)
         caso base -> devuelve 1
      devuelve 2 * factorial(1) = 2
   devuelve 3 * factorial(2) = 6
devuelve 4 * factorial(3) = 24
factorial(4) = 24

sumaArray({3,1,4,1,5}) = 14

d) Sin caso base, las llamadas no paran nunca: cada una apila un marco nuevo hasta agotar la pila de llamadas → StackOverflowError. Java gestiona las llamadas pendientes con una PILA (la pila de llamadas o call stack): cada llamada apila sus variables locales y su punto de retorno, y al terminar se desapila — LIFO puro, por eso la traza se "deshace" en orden inverso.