Estructuras de datos: preguntas de práctica con explicaciones

1Qué es una estructura de datos

Una estructura de datos es una forma de organizar los datos en memoria para que ciertas operaciones sean rápidas: buscar un elemento, añadir uno, eliminar uno.

Ninguna estructura es rápida en todo. Elegir una significa elegir qué operaciones deben ser baratas. Sus costes se escriben en notación O grande, con n el número de elementos.

Los dos bloques básicos son el array y la lista enlazada.

Un array guarda sus elementos en un único bloque de memoria, uno tras otro. El ordenador puede calcular dónde está el elemento i, así que leer a[i] cuesta O(1). Insertar al principio obliga a desplazar todos los elementos: O(n).

Una lista enlazada guarda cada elemento en un nodo con un puntero al nodo siguiente. El último puntero es nulo. Insertar en la cabeza (h) solo cambia un puntero: O(1). Pero para llegar al elemento i hay que seguir i punteros: O(n).

Una lista doblemente enlazada tiene además un puntero al nodo anterior, así que se puede recorrer en ambos sentidos.

2Pilas y colas

Una pila es como un montón de platos: solo se añade y se quita por arriba. El último elemento en entrar es el primero en salir: LIFO.

• push pone un elemento arriba, pop quita el elemento de arriba, peek lee el de arriba sin quitarlo. Todas son O(1).
• Usos: la función deshacer de un editor, la pila de llamadas de un programa, comprobar que los paréntesis están balanceados, la búsqueda en profundidad.

Una cola es como la fila de una caja: te unes por detrás y sales por delante. El primer elemento en entrar es el primero en salir: FIFO.

• enqueue añade por detrás, dequeue quita por delante. Ambas son O(1).
• Usos: trabajos de impresión, mensajes a la espera de ser procesados, la búsqueda en anchura.

Una deque (cola de doble extremo) permite añadir y quitar por ambos extremos. Una cola de prioridad siempre quita primero el elemento de mayor prioridad; normalmente se construye como un montículo.

3Árboles, montículos, tablas hash y grafos

Un árbol tiene un nodo superior, la raíz. Todos los demás nodos tienen exactamente un padre. Los nodos sin hijos son hojas. Un árbol con n nodos tiene n − 1 aristas.

En un árbol binario cada nodo tiene como máximo dos hijos. Un árbol binario de búsqueda (BST) añade una regla: las claves del subárbol izquierdo son menores que el nodo, las del subárbol derecho son mayores.

Buscar en un BST sigue un solo camino hacia abajo, así que cuesta O(altura). Un árbol equilibrado (AVL, rojinegro) mantiene la altura cerca de log₂ n. Las claves insertadas en orden crean una cadena de altura n.

Un montículo (heap) es un árbol binario en el que cada padre es menor que sus hijos (min-heap) o mayor (max-heap). El mínimo o el máximo está en la raíz, e insertar y extraer cuestan O(log n).

Una tabla hash guarda pares clave–valor. Una función hash convierte la clave en un índice, así que insertar y buscar cuestan O(1) en promedio. Dos claves con el mismo índice son una colisión, que se resuelve con encadenamiento (una lista por casilla) o con direccionamiento abierto (probar otra casilla).

Un grafo tiene vértices unidos por aristas, que pueden tener dirección o peso. Se guarda como matriz de adyacencia, con memoria O(V²), o como listas de adyacencia, O(V + E).

4El método paso a paso

Las preguntas suelen describir una tarea y preguntar qué estructura encaja, o preguntar cómo queda una estructura tras algunas operaciones.

1. Encuentra la operación que debe ser rápida: acceso por posición, por clave, el elemento más nuevo, el más antiguo, el más pequeño o un rango.
2. Asóciala a una estructura: índice → array, clave → tabla hash, el más nuevo → pila, el más antiguo → cola, el menor o el mayor → montículo, orden o rangos → árbol de búsqueda equilibrado.
3. Comprueba el coste, en notación O grande, de las demás operaciones que necesita la tarea.
4. En una pregunta de traza, realiza las operaciones una a una y anota el estado tras cada una.
5. Comprueba el estado final con la regla de la estructura: LIFO, FIFO, el orden del BST o el orden del montículo.

5Un ejemplo resuelto

Sigue cada paso. Intenta adivinar el siguiente antes de abrirlo.

6Errores frecuentes

• Confundir LIFO y FIFO. Una pila devuelve el elemento más nuevo, una cola el más antiguo.
• Creer que una lista enlazada da acceso rápido por índice. Tiene que recorrerse desde la cabeza.
• Suponer que un BST siempre es O(log n). Solo lo es un árbol equilibrado; las inserciones en orden dan O(n).
• Olvidar las colisiones en una tabla hash. O(1) es el caso promedio, no el peor caso.
• Confundir los recorridos. Preorden: primero el nodo. En orden: el nodo en medio. Postorden: el nodo al final.
• Usar una matriz de adyacencia para un grafo grande y disperso. Desperdicia memoria O(V²).

7Cómo son las preguntas de examen

• Fácil: términos y datos clave. LIFO y FIFO, qué es un nodo, una raíz o una hoja, la regla del BST, qué hace una función hash.
• Medio: aplicar los conceptos. Qué estructura encaja con una tarea, el resultado de push y pop o de inserciones en un BST, recorridos de árboles, una tabla hash con sondeo lineal, costes en notación O grande.
• Difícil: casos y análisis. Árboles equilibrados, montículos en arrays, árboles B, tries, union-find, filtros de Bloom y diseños como una caché LRU.

En un montículo guardado en un array desde el índice 0, los hijos del índice i están en 2i + 1 y 2i + 2, y su padre está en ⌊(i − 1) / 2⌋.