Algoritmos, grafos, programación dinámica y bases de datos relacionales
32 tarjetas de repaso universitario sobre ordenación, algoritmos de grafos, programación dinámica, SQL, índices y transacciones. Requiere programación básica, estructuras de datos y SQL.
- Category
- Computer Science
- Level
- basic
- Languages
- es → es
- Cards
- 32
- Markdown
- Algoritmos, grafos, programación dinámica y bases de datos relacionales (.md)
Flashcards (32)
| # | Front (Term / Question) | Back (Definition / Answer) | Example | Multiple-Choice Options |
|---|---|---|---|---|
| 1 | ¿Cómo trata Bellman–Ford las aristas negativas y detecta un ciclo negativo alcanzable? | Relaja todas las aristas hasta V−1 veces. Una mejora adicional desde un vértice alcanzable revela un ciclo negativo alcanzable desde el origen. El peor caso cuesta O(VE); los vértices alcanzables desde ese ciclo no tienen un coste mínimo finito. | ||
| 2 | ¿Qué exige la búsqueda binaria y cuándo tarda O(log n)? | Reduce a la mitad el intervalo de búsqueda en datos ordenados según el criterio de comparación. En un array con acceso por índice O(1) y comparaciones de tiempo constante, buscar entre n elementos cuesta O(log n). | ||
| 3 | ¿Qué exigen la primera, segunda y tercera formas normales? | 1FN: valores atómicos. 2FN: 1FN y ningún atributo no primo depende de una parte propia de ninguna clave candidata. 3FN: 1FN y, en toda dependencia no trivial X→A, X es superclave o A es primo. Un atributo primo pertenece a alguna clave candidata. | ||
| 4 | ¿Cuáles son los costes de tiempo en el peor caso y de espacio adicional de heapsort in situ? | Construir el montículo cuesta O(n) y las extracciones suman O(n log n). Con descenso iterativo dentro del array de entrada, heapsort tarda O(n log n) en el peor caso y usa O(1) de espacio adicional. | ||
| 5 | ¿Cuál es la recurrencia habitual de la mochila 0/1 con capacidad entera W? | Sea D[i,w] el mejor valor usando los primeros i objetos con capacidad w y pesos enteros positivos wᵢ. D[0,w]=0. Si wᵢ>w, se copia D[i−1,w]; en otro caso, max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). El tiempo O(NW) es seudopolinómico. | ||
| 6 | ¿Por qué quicksort puede tardar Θ(n²) y cómo ayuda la aleatorización? | Las particiones repetidamente desequilibradas, como elegir siempre la menor clave entre claves distintas, causan trabajo cuadrático. Con claves distintas o un tratamiento adecuado de los duplicados, los pivotes aleatorios dan tiempo esperado O(n log n). La mediana de tres es una heurística útil, no una garantía para el peor caso. | ||
| 7 | ¿Cuándo pueden la ordenación por conteo y por radix tardar tiempo lineal? | El conteo cuesta O(n+k) para n claves en un rango de k valores. Radix con d pasadas estables por dígitos y base b cuesta O(d(n+b)). Solo son lineales cuando esos parámetros lo permiten; aprovechan la estructura de las claves además de compararlas. | ||
| 8 | ¿Cuáles son las dos fases del bloqueo en dos fases (2PL)? | Crecimiento: adquirir bloqueos sin liberarlos. Decrecimiento: liberarlos sin adquirir otros nuevos. Con bloqueos adecuados para lecturas y escrituras en conflicto, 2PL garantiza planes serializables por conflictos, pero puede haber interbloqueos. | ||
| 9 | ¿Qué es una lectura no repetible y qué nivel estándar la impide? | Al releer una fila, sus datos han cambiado o la fila ha desaparecido después de que otra transacción confirme una actualización o eliminación. REPEATABLE READ y SERIALIZABLE impiden esta anomalía. | ||
| 10 | ¿Cuándo es válido Dijkstra y cuál es un coste habitual con montículo? | Con pesos no negativos, fija repetidamente el vértice de menor distancia provisional. Una implementación con listas de adyacencia y montículo binario mínimo tarda O((V+E) log V). Las aristas negativas pueden invalidar el argumento de distancia definitiva. | ||
| 11 | ¿Por qué son útiles los árboles B+ para índices y consultas por rango? | Su elevado factor de ramificación mantiene poca altura y reduce accesos a páginas. Las claves ordenadas y las hojas enlazadas permiten recorrer rangos. Los índices hash se orientan a la igualdad y no ofrecen intrínsecamente el mismo acceso ordenado por rangos. | ||
| 12 | ¿En qué difiere un algoritmo voraz de la programación dinámica? | El voraz adopta una decisión local y necesita demostrar que esas decisiones conservan un óptimo. La programación dinámica compara alternativas mediante una recurrencia y reutiliza resultados. Lograr el óptimo global requiere un modelo y una recurrencia correctos, no solo la etiqueta «programación dinámica». | ||
| 13 | ¿En qué se diferencian las claves primarias y foráneas en PostgreSQL? | La primaria identifica filas mediante valores únicos y no NULL. La foránea exige coincidencia con valores de una clave referenciada, según sus reglas para NULL. Puede referenciar una clave UNIQUE apta o una primaria de la misma tabla o de otra. | ||
| 14 | ¿Qué es un orden topológico y cómo lo obtiene el algoritmo de Kahn? | En un DAG, cada arista u→v sitúa u antes que v. Se extrae repetidamente un vértice de grado de entrada cero y se eliminan sus aristas salientes, encolando los nuevos vértices de grado cero. Si salen menos de V vértices, existe un ciclo dirigido. | ||
| 15 | ¿En qué se diferencian INNER JOIN y LEFT JOIN? | INNER JOIN devuelve las combinaciones de filas que cumplen la condición de unión. LEFT JOIN conserva además cada fila izquierda sin coincidencia, con NULL en las columnas derechas. Varias coincidencias derechas pueden producir varias filas por una fila izquierda. | ||
| 16 | ¿En qué se diferencian WHERE y HAVING en una consulta agrupada? | WHERE filtra las filas de entrada antes de agrupar. HAVING filtra los grupos resultantes y admite condiciones con agregados, como COUNT(*)>1. | ||
| 17 | ¿Cómo funciona la ordenación por inserción y de qué depende su coste con datos casi ordenados? | Inserta cada elemento en un prefijo ordenado. La versión habitual con desplazamientos o intercambios adyacentes tarda Θ(n+I), donde I es el número de inversiones. Es lineal si I=O(n); un tamaño pequeño no cambia el peor caso Θ(n²). | ||
| 18 | ¿En qué se diferencian los índices agrupados y no agrupados de almacenamiento por filas en SQL Server? | El agrupado almacena las filas en orden de clave, por lo que solo puede haber uno por tabla. El no agrupado tiene sus propias claves y localizadores de filas, y puede incluir otras columnas. La terminología y los detalles varían entre sistemas. | ||
| 19 | ¿Qué es una lectura sucia y cuál es el primer nivel estándar que la impide? | Leer datos no confirmados de otra transacción, tanto si luego se revierte como si no. READ COMMITTED y los niveles estándar superiores prohíben las lecturas sucias. | ||
| 20 | ¿Qué significa que un algoritmo de ordenación sea estable? | Los elementos con claves iguales conservan su orden relativo original. La mezcla puede ser estable si se toma primero el elemento izquierdo en los empates; el quicksort habitual in situ suele ser inestable. Depende de la implementación. | ||
| 21 | ¿Cómo se comparan una matriz de adyacencia y unas listas de adyacencia ordinarias? | Con V vértices y E aristas, la matriz ocupa O(V²) y comprueba una arista en O(1). Las listas ocupan O(V+E); buscar (u,v) en una lista no ordenada cuesta O(deg(u)), donde deg(u) es la longitud de esa lista. | ||
| 22 | ¿Cuál es un orden lógico simplificado para procesar una consulta SQL SELECT? | Sin CTE, funciones de ventana ni operaciones entre conjuntos: FROM/JOIN → WHERE → GROUP BY y agregados → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. Es un modelo lógico, no necesariamente el orden físico elegido por el optimizador. | ||
| 23 | ¿Cómo detecta DFS un ciclo en un grafo dirigido? | DFS profundiza mediante recursión o una pila explícita. Una arista hacia un vértice todavía activo en el camino actual es una arista de retroceso y demuestra un ciclo dirigido; no basta con que el vértice se haya visitado antes. | ||
| 24 | ¿En qué se diferencian la memoización y la programación dinámica ascendente? | La memoización evalúa subproblemas según se necesitan, normalmente de forma recursiva, y guarda los resultados. La programación dinámica ascendente evalúa estados cuando sus dependencias ya están disponibles, normalmente llenando una tabla. | ||
| 25 | ¿Cómo mantiene WAL la durabilidad en PostgreSQL con confirmación síncrona normal? | Los registros pertinentes llegan al almacenamiento duradero antes de reconocer la confirmación y antes de escribir las páginas modificadas. Tras un fallo, WAL puede reproducir los cambios que faltan en las páginas. La confirmación asíncrona puede perder transacciones recientes ya reconocidas. | ||
| 26 | ¿Cómo encuentra BFS los caminos más cortos en un grafo no ponderado? | BFS utiliza una cola FIFO y explora por distancia en número de aristas. Marcar un vértice al encolarlo evita visitas repetidas. El primer camino descubierto hasta un vértice alcanzable tiene el mínimo número de aristas. | ||
| 27 | ¿Por qué resulta útil la programación dinámica en muchos problemas de optimización? | La subestructura óptima permite expresar un óptimo mediante óptimos de subproblemas. Si estos se solapan, almacenar sus respuestas evita trabajo repetido. La definición de estados y la recurrencia deben representar correctamente el problema original. | ||
| 28 | ¿Cómo funciona la ordenación por mezcla estándar para arrays y cuáles son sus costes? | Ordena recursivamente dos mitades y las mezcla en tiempo lineal. La versión estándar tarda Θ(n log n) y usa O(n) de espacio auxiliar, suponiendo comparaciones de tiempo constante. | ||
| 29 | ¿Cuál es la recurrencia dinámica para la longitud de la subsecuencia común más larga (LCS)? | L[i,j] es la longitud de la LCS de prefijos de longitudes i,j. L[0,j]=L[i,0]=0. Si coinciden los últimos caracteres, L[i,j]=1+L[i−1,j−1]; si no, L[i,j]=max(L[i−1,j],L[i,j−1]). La tabla completa requiere tiempo y espacio O(mn). | ||
| 30 | ¿Qué es una lectura fantasma y cómo se evita? | Repetir una consulta por predicado encuentra otro conjunto de filas coincidentes tras cambios confirmados por otra transacción. SERIALIZABLE la impide en el modelo estándar; algunas implementaciones, como REPEATABLE READ de PostgreSQL, también la impiden en un nivel inferior. | ||
| 31 | ¿Cómo construyen Kruskal y Prim un árbol de expansión mínimo? | En un grafo conexo, no dirigido y ponderado, Kruskal considera las aristas por peso creciente y usa Union–Find para rechazar ciclos. Prim amplía un solo árbol eligiendo una arista de peso mínimo que conecte el árbol con un vértice exterior. | ||
| 32 | ¿Qué significan las propiedades ACID de una transacción? | Atomicidad: efectos completos o ninguno. Consistencia: las transacciones correctas preservan restricciones e invariantes de la aplicación. Aislamiento: la concurrencia respeta el nivel elegido. Durabilidad: los efectos confirmados sobreviven a los fallos cubiertos por las garantías configuradas. |