# Estructuras de Datos, Análisis de Complejidad (Big-O) y Algoritmos Clave > Repaso universitario que requiere programación básica: 32 tarjetas sobre arrays, listas, hashing, árboles, montículos, tries, Union–Find, filtros de Bloom y complejidad. - **Canonical URL:** https://flashcards.world/flashcards/sets/e3e86ce5-ab66-4e1e-a345-60fff63d5e5a/ - **Markdown URL:** https://flashcards.world/flashcards/sets/e3e86ce5-ab66-4e1e-a345-60fff63d5e5a.md - **Level:** basic - **Languages:** es → es - **Total Cards:** 32 ## Flashcards (32 Cards) | # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options | | :--- | :--- | :--- | :--- | :--- | | 1 | ¿Cómo dependen de la altura h la búsqueda, inserción y eliminación en un BST? | Cuestan O(h). Un árbol equilibrado tiene h = O(log n); una cadena, h = O(n). El coste esperado O(log n) exige hipótesis como un orden de inserción aleatorio. | | | | 2 | ¿Qué reglas de color mantienen equilibrado un BST rojinegro? | Los nodos son rojos o negros; la raíz y las hojas NIL son negras. Ningún nodo rojo tiene hijos rojos. Todos los caminos de un nodo a una hoja NIL descendiente contienen igual número de nodos negros. Estas reglas acotan la altura a O(log n). | | | | 3 | ¿Qué hacen find y union en una estructura de conjuntos disjuntos? | find(x) devuelve el representante del conjunto de x. union(x,y) fusiona sus conjuntos si son distintos; si ya pertenecen al mismo, la partición no cambia. | | | | 4 | ¿Qué es un trie y cuándo cuesta O(L) buscar una clave de L caracteres? | Es un árbol de prefijos que guarda las claves en caminos de caracteres, con marcas de clave completa. La búsqueda cuesta O(L) si cada transición al carácter siguiente cuesta O(1). | | | | 5 | ¿Por qué el acceso por índice en un array de tamaño fijo cuesta O(1)? | Sus posiciones, de igual tamaño, son contiguas: dirección(i) = base + i·tamaño_posición. Se supone que calcular direcciones cuesta tiempo constante. | | | | 6 | Para funciones no negativas f y g, ¿qué significa f(n) ∈ O(g(n))? | Existen constantes c > 0 y n₀ ≥ 0 tales que f(n) ≤ c·g(n) para todo n ≥ n₀. | | | | 7 | ¿Cómo recorre un árbol binario el recorrido por niveles? | Usa una cola FIFO para visitar un nivel de profundidad cada vez. Encola el hijo izquierdo antes que el derecho para obtener el orden de izquierda a derecha. | | | | 8 | ¿Cómo funciona una pila y cuándo cuestan O(1) sus operaciones? | LIFO: el último elemento insertado sale primero. En la cabeza de una lista enlazada, insertar, extraer y consultar cuestan O(1); redimensionar un array puede hacer que una inserción cueste O(n). | | | | 9 | ¿Por qué una lista doblemente enlazada puede eliminar un nodo dado en O(1)? | Sus enlaces anterior y siguiente permiten reconectar directamente los vecinos. Se actualizan cabeza y cola si hace falta; no hay que buscar el predecesor. | | | | 10 | ¿Cuánto cuesta construir un montículo de abajo arriba con n elementos? | O(n). La mayoría de los nodos están cerca de las hojas y requieren pocos descensos; sumar el trabajo por altura de nodo da un total lineal. | | | | 11 | Si la capacidad se duplica, ¿cuánto cuesta amortizadamente añadir al final de un array dinámico? | O(1) por inserción. Redimensionar puede costar O(n), pero n inserciones al final desde un array vacío cuestan O(n) en total. | | | | 12 | ¿Cuáles son los costes esperados y de peor caso en una tabla hash con encadenamiento separado? | Con carga acotada, hashes bien distribuidos y operaciones sobre claves de coste constante, buscar y borrar cuestan O(1) esperado. Con crecimiento geométrico, insertar cuesta O(1) amortizado esperado. Una cadena de n claves en colisión puede causar O(n). | | | | 13 | Compara la inserción al principio y el acceso por índice en una lista simplemente enlazada y un array dinámico. | Lista: inserción inicial O(1), acceso por índice O(n). Array: inserción inicial O(n), acceso por índice O(1); insertar al principio desplaza elementos. | | | | 14 | ¿Cómo resuelve las colisiones hash el encadenamiento separado? | Cada cubeta contiene una colección de entradas con ese índice, a menudo una lista enlazada. Las claves distintas que comparten cubeta siguen siendo entradas separadas. | | | | 15 | ¿En qué se diferencian la compresión de caminos, la unión por rango y la unión por tamaño? | La compresión redirige los nodos visitados a la raíz. Por rango, la raíz de menor rango queda bajo la de mayor rango; por tamaño, el conjunto menor queda bajo el mayor. El rango no tiene por qué ser la altura actual. | | | | 16 | ¿Qué produce el recorrido inorden de un BST con claves distintas? | Todas las claves en orden estrictamente creciente, visitando n nodos en O(n). | | | | 17 | ¿Qué propiedades debe tener una función hash para buscar en una tabla? | Debe ser determinista y distribuir bien las claves esperadas. Calcular el hash de claves de tamaño fijo puede costar O(1); el de una cadena nueva de L caracteres suele costar O(L). | | | | 18 | ¿Qué invariante de orden define un árbol binario de búsqueda (BST) con claves distintas? | En cada nodo, todas las claves del subárbol izquierdo son menores y todas las del derecho son mayores. La regla se aplica recursivamente. | | | | 19 | ¿Qué respuestas puede dar un filtro de Bloom que solo permite inserciones? | Un resultado negativo indica que el elemento no se insertó; uno positivo, que puede haberse insertado. Los hashes activan bits en un array: puede haber falsos positivos, pero no falsos negativos si el estado está intacto. | | | | 20 | ¿Cómo evita una cola circular en un array desplazar elementos al extraer? | Los índices inicial y final avanzan módulo la capacidad. Extraer adelanta el índice inicial, permitiendo reutilizar posiciones libres sin mover los demás elementos. | | | | 21 | ¿Cuál es la condición de equilibrio AVL? | En cada nodo, altura(izquierda) − altura(derecha) ∈ {−1, 0, 1}. El árbol también cumple el invariante de orden de un BST. | | | | 22 | ¿Cuáles son los órdenes de recorrido preorden, inorden y postorden de un árbol binario? | Preorden: nodo → izquierda → derecha. Inorden: izquierda → nodo → derecha. Postorden: izquierda → derecha → nodo. | | | | 23 | ¿Dónde están el padre y los hijos del nodo i en un array de montículo de longitud n e índices desde cero? | Padre: ⌊(i−1)/2⌋ si i>0. Hijos: 2i+1 y 2i+2, solo si esos índices son menores que n. El índice 0 no tiene padre. | | | | 24 | ¿Qué dos propiedades definen un montículo binario mínimo? | Es un árbol binario completo y la clave de cada padre no supera las de sus hijos. Por tanto, la raíz contiene un mínimo. | | | | 25 | ¿Qué es el factor de carga de una tabla hash y por qué puede redimensionarse? | α = n/m: n entradas almacenadas y m cubetas o posiciones. Superar el umbral de la implementación puede provocar una ampliación y redistribución mediante hash; 0,75 no es universal. | | | | 26 | ¿Cómo se corrige un desequilibrio izquierda-derecha causado por una inserción AVL? | Primero se rota el hijo izquierdo hacia la izquierda; después, el nodo desequilibrado hacia la derecha. | | | | 27 | ¿En qué se diferencian O, Ω y Θ? | Expresan cotas asintóticas superior, inferior y ajustada, respectivamente. Describen una función de coste especificada; O no significa por sí misma «peor caso». | | | | 28 | ¿Cuál es el coste amortizado de union/find con compresión de caminos y unión por rango? | O(α(n)) por operación, donde α es la inversa de Ackermann y n el número de elementos. Inicializar cuesta O(n); la cota describe una secuencia, no un coste constante de peor caso para cada llamada. | | | | 29 | ¿Cuánto cuestan insertar, eliminar la raíz y consultar la raíz en un montículo binario? | O(log n), O(log n) y O(1), respectivamente, si no hace falta redimensionar el array. Redimensionarlo puede costar O(n). | | | | 30 | Ordena de menor a mayor crecimiento cuando n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n. | Asintóticamente: 1 < log n < n < n log n < n² < 2ⁿ < n!. | | | | 31 | ¿Qué orden de acceso usa una cola y cuánto suelen costar sus operaciones? | FIFO: se añade por detrás y se extrae por delante. Ambas operaciones cuestan O(1) con enlaces a cabeza y cola o un búfer circular de capacidad fija; desplazar un array hace que extraer cueste O(n). | | | | 32 | ¿En qué se diferencian el sondeo lineal y el cuadrático en direccionamiento abierto? | Las entradas permanecen en el array. Con tamaño m e índice inicial h, se prueban (h+i) mod m y (h+c₁i+c₂i²) mod m, respectivamente. El sondeo cuadrático requiere parámetros adecuados. | | | --- Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/e3e86ce5-ab66-4e1e-a345-60fff63d5e5a/).