REPASO EXPRÉS — ESTRUCTURA DE DATOS (Java) LECTURA: 30 MIN

1 · PLANTILLA DE CLASE ENCAPSULADA (la que siempre cae)

public class Alumno {                              // 1. clase publica
    private String nombre;                         // 2. atributos SIEMPRE private
    private double nota;                           //    (nadie los toca desde fuera)

    public Alumno(String nombre, double nota) {    // 3. constructor = nombre de la clase, sin tipo de retorno
        this.nombre = nombre;                      //    this.atributo = parametro (mismo nombre)
        setNota(nota);                             //    reuso el setter: tambien valida al construir
    }

    public String getNombre() { return nombre; }   // 4. getters: lectura controlada
    public double getNota()   { return nota;   }

    public void setNota(double nota) {             // 5. setter CON validacion (esto da puntos)
        if (nota >= 0 && nota <= 10) {             //    solo acepta valores legales
            this.nota = nota;                      //    si no, se ignora (o lanzar excepcion)
        }
    }

    @Override                                      // 6. redefine el toString de Object
    public String toString() {
        return nombre + " (" + nota + ")";         //    lo que imprime System.out.println(alumno)
    }
}

2 · PLANTILLA DE JERARQUÍA: abstracta + hijas + polimorfismo

public abstract class Figura {                     // abstract: NO se puede hacer new Figura()
    protected String nombre;                       // protected: las hijas SI lo ven

    public Figura(String nombre) {                 // las hijas lo llaman con super(...)
        this.nombre = nombre;
    }

    public abstract double area();                 // SIN cuerpo: cada hija DEBE implementarlo

    public String describir() {                    // metodo normal: se hereda tal cual
        return nombre + ": area = " + area();      // llama al area() de la hija real
    }
}

class Circulo extends Figura {
    private double radio;
    public Circulo(double radio) {
        super("Circulo");                          // PRIMERA linea: constructor del padre
        this.radio = radio;
    }
    @Override public double area() { return Math.PI * radio * radio; }
}

class Rectangulo extends Figura {
    private double base, altura;
    public Rectangulo(double base, double altura) {
        super("Rectangulo");
        this.base = base; this.altura = altura;
    }
    @Override public double area() { return base * altura; }
}

Uso polimórfico (esto es lo que demuestra que entiendes el tema):

Figura[] figuras = { new Circulo(2), new Rectangulo(3, 4) };  // array del tipo PADRE
for (Figura f : figuras) {
    System.out.println(f.describir());   // ejecuta el area() de CADA hija (enlace dinamico)
}

3 · COMPLEJIDAD EN 4 PASOS (receta)

1. Un bucle que recorre n elementos → O(n).
2. Bucles anidados independientes → se multiplican: n·n = O(n²). Bucles seguidos (no anidados) → se suman: n+n → sigue siendo O(n).
3. Índice que se duplica o divide (i*=2, i/=2, mitades) → O(log n). Bucle de n con interno logarítmico → O(n log n).
4. Quédate con el término dominante y tira las constantes: 3n² + 5n + 7 → O(n²).

4 · ORDENACIÓN — los 6 códigos que hay que saber picar

static void burbujaMejorada(int[] a) {
    boolean cambio = true;                         // bandera: optimizacion 1
    for (int i = 0; i < a.length - 1 && cambio; i++) {
        cambio = false;                            // supongo que ya esta ordenado
        for (int j = 0; j < a.length - 1 - i; j++) {   // -i: el final ya esta ordenado (opt. 2)
            if (a[j] > a[j + 1]) {                 // vecinos desordenados...
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;   // ...se intercambian
                cambio = true;
            }
        }
    }
}

static void seleccion(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int min = i;                               // posicion del minimo de lo no ordenado
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[min]) min = j;            // solo APUNTO donde esta (no intercambio aun)
        }
        int t = a[i]; a[i] = a[min]; a[min] = t;   // UN solo intercambio por pasada
    }
}

static void insercion(int[] a) {
    for (int i = 1; i < a.length; i++) {           // a[0] ya es una "mano" ordenada
        int v = a[i];                              // carta que voy a colocar
        int j = i - 1;
        while (j >= 0 && a[j] > v) {               // mientras haya mayores a la izquierda...
            a[j + 1] = a[j];                       // ...los desplazo un hueco a la derecha
            j--;
        }
        a[j + 1] = v;                              // inserto la carta en su hueco
    }
}

static void mergeSort(int[] a, int ini, int fin) {
    if (ini >= fin) return;                        // CASO BASE: 0 o 1 elementos
    int mid = (ini + fin) / 2;
    mergeSort(a, ini, mid);                        // 1) ordeno mitad izquierda
    mergeSort(a, mid + 1, fin);                    // 2) ordeno mitad derecha
    merge(a, ini, mid, fin);                       // 3) mezclo las dos mitades ordenadas
}

static void merge(int[] a, int ini, int mid, int fin) {
    int[] aux = new int[fin - ini + 1];            // array auxiliar (memoria extra O(n))
    int i = ini, j = mid + 1, k = 0;
    while (i <= mid && j <= fin) {                 // comparo cabezas y copio la menor
        aux[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];   // <= mantiene la estabilidad
    }
    while (i <= mid) aux[k++] = a[i++];            // restos de la izquierda
    while (j <= fin) aux[k++] = a[j++];            // restos de la derecha
    for (k = 0; k < aux.length; k++) a[ini + k] = aux[k];  // vuelco aux al original
}

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 en su sitio definitivo
    quickSort(a, ini, p - 1);                      // ordeno los menores
    quickSort(a, p + 1, fin);                      // ordeno los mayores
}

static int particionar(int[] a, int ini, int fin) {
    int pivote = a[ini];                           // pivote = primer elemento
    int i = ini;                                   // frontera de los menores
    for (int j = ini + 1; j <= fin; j++) {
        if (a[j] < pivote) {                       // menor que el pivote:
            i++;                                   // amplio la zona de menores...
            int t = a[i]; a[i] = a[j]; a[j] = t;   // ...y lo meto en ella
        }
    }
    int t = a[ini]; a[ini] = a[i]; a[i] = t;       // pivote a la frontera (su sitio final)
    return i;                                      // posicion definitiva del pivote
}

static void heapSort(int[] a) {
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) {         // FASE 1: construir MAX-HEAP
        hundir(a, n, i);                           //   desde el ultimo padre hacia la raiz
    }
    for (int fin = n - 1; fin > 0; fin--) {        // FASE 2: extraer el maximo n-1 veces
        int t = a[0]; a[0] = a[fin]; a[fin] = t;   //   raiz (maximo) ↔ ultimo del heap
        hundir(a, fin, 0);                         //   re-hundir la nueva raiz (heap mas corto)
    }
}

static void hundir(int[] a, int n, int i) {        // baja a[i] hasta cumplir padre >= hijos
    int mayor = i, izq = 2 * i + 1, der = 2 * i + 2;   // hijos de i en el array
    if (izq < n && a[izq] > a[mayor]) mayor = izq;
    if (der < n && a[der] > a[mayor]) mayor = der;
    if (mayor != i) {                              // algun hijo es mayor que el padre:
        int t = a[i]; a[i] = a[mayor]; a[mayor] = t;
        hundir(a, n, mayor);                       // sigo hundiendo por esa rama
    }
}

TABLA RESUMEN — vuélcala tal cual en el examen

5 · BÚSQUEDA BINARIA (solo sobre array ORDENADO)

static int busquedaBinaria(int[] a, int x) {
    int low = 0, high = a.length - 1;
    while (low <= high) {                          // OJO: <=  (con < falla, ver abajo)
        int mid = (low + high) / 2;                // miro el centro
        if (a[mid] == x) return mid;               // encontrado
        if (a[mid] < x) low  = mid + 1;            // esta a la derecha: descarto mitad izq.
        else            high = mid - 1;            // esta a la izquierda: descarto mitad der.
    }
    return -1;                                     // no esta
}

Cada vuelta descarta la mitad → O(log n) (peor caso). Mejor caso O(1): acierta al centro a la primera.

6 · ESTRUCTURAS DE DATOS EXPRÉS

Deque<Integer> pila = new ArrayDeque<>();   // pila LIFO
pila.push(1); pila.push(2); pila.push(3);   // apilar: la cima es 3
System.out.println(pila.pop());             // 3 (sale el ULTIMO que entro)
System.out.println(pila.peek());            // 2 (mira la cima SIN sacarla)
System.out.println(pila.isEmpty());         // false

Map<String, Integer> notas = new HashMap<>();  // clave -> valor
notas.put("Ana", 7);  notas.put("Luis", 5);    // insertar O(1)
notas.put("Ana", 9);                           // clave repetida: SOBRESCRIBE
System.out.println(notas.get("Ana"));          // 9 (acceso O(1) por clave)
System.out.println(notas.containsKey("Eva"));  // false

Imports: import java.util.*; cubre Deque, ArrayDeque, Map, HashMap, List, ArrayList…

7 · RECURSIÓN EXPRÉS

static long factorial(int n) {
    if (n <= 1) return 1;              // CASO BASE: 0! = 1! = 1
    return n * factorial(n - 1);       // CASO RECURSIVO: n! = n * (n-1)!
}

Traza: factorial(4) = 4·factorial(3) = 4·3·factorial(2) = 4·3·2·factorial(1) = 4·3·2·1 = 24. Sin caso base → StackOverflowError.

8 · ERRORES QUE TE QUITAN PUNTOS

Repaso Exprés EDA · UAX 1º Ing. Informática · Si sabes reproducir a mano las plantillas 1, 2 y los 6 códigos del punto 4, el examen está hecho.