Estructuras de datos y algoritmos: pack de repaso

Hojas de fórmulas, los pasos clave de los métodos de cada tema y 6 problemas de práctica, con las soluciones completas al final.

Problemas nuevosVolver a la asignatura

En la ventana de impresión, elige «Guardar como PDF» para conservar una copia en tu dispositivo.

1Fórmulas y métodos

Teoría de grafos

Lema del apretón de manos
Σ deg(v) = 2|E|
Grafos completos
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Grafo regular
|E| = n·k/2
Árbol y bosque
|E| = n − 1, |E| = n − c
Hojas de un árbol
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
circuito: todos los grados pares; camino: exactamente 2 grados impares
Circuitos de Hamilton en Kn
(n − 1)!/2
Actualización de Dijkstra
d(v) = min(d(v), d(u) + w(u, v))
Recorridos de longitud L
(Mᴸ)ij

Método

  1. Anota el grado de cada vértice; los grados suman el doble del número de aristas.
  2. En las preguntas de Euler, comprueba que el grafo sea conexo y cuenta los vértices de grado impar.
  3. En los árboles, usa n − 1 aristas y el lema del apretón de manos.
  4. En Dijkstra, lleva una tabla de distancias provisionales y fija en cada ronda el vértice no fijado de menor distancia.
  5. Para un árbol generador mínimo, ordena las aristas por peso y descarta toda arista que cierre un ciclo (Kruskal), o haz crecer un único árbol desde un vértice inicial (Prim).

2Problemas de práctica

1.Algoritmos y complejidadMedia

¿Cuál es la solución de la recurrencia T(n) = 2T(n/2) + O(1)?

  1. AO(log n)
  2. BO(n)
  3. CO(n log n)
  4. DO(n²)
2.Algoritmos y complejidadDifícil

¿Cuál es la solución de la recurrencia T(n) = 2T(n/2) + n log n?

  1. AΘ(n²)
  2. BΘ(n log² n)
  3. CΘ(n log n)
  4. DΘ(n)
3.Estructuras de datosMedia

¿Cuánta memoria usa una lista de adyacencia para un grafo con V vértices y E aristas?

  1. AO(V²)
  2. BO(E²)
  3. CO(V × E)
  4. DO(V + E)
4.Estructuras de datosDifícil

Debes conservar los k valores más pequeños de un flujo de n números usando O(k) de memoria. ¿Qué enfoque funciona en un tiempo O(n log k)?

  1. AUn arreglo ordenado con los n valores
  2. BUna cola FIFO con los últimos k valores
  3. CUn max-heap de tamaño k, sustituyendo su raíz cuando llega un valor menor
  4. DUn min-heap que contiene los n valores, del que se extraen al final los k menores
5.Teoría de grafosMedia
ABCDEFCircuito eulerianoCamino euleriano, sin circuitoninguna de las dos

¿Tiene el grafo conexo un circuito euleriano, un camino euleriano que no es un circuito, o ninguno de los dos? Haz clic en tu respuesta.

|V| = 6|E| = 7
  1. 1Circuito euleriano
  2. 2Camino euleriano, sin circuito
  3. 3ninguna de las dos
6.Teoría de grafosDifícil
6174121014205ABCDEF

Halla el peso total W de un árbol generador mínimo del grafo ponderado.

|V| = 6|E| = 8
W =

3Disoluciones

1.Algoritmos y complejidad

Respuesta: B · O(n)

Por qué esta es la respuesta

Por el teorema maestro, nlog₂ 2 = n domina al trabajo constante, así que T(n) = Θ(n), como al hallar un máximo dividiendo en mitades.

Respuesta

B · O(n)
2.Algoritmos y complejidad

Respuesta: B · Θ(n log² n)

Por qué esta es la respuesta

El nivel k hace un trabajo de unos n log(n / 2ᵏ), y sumar sobre los log n niveles da Θ(n log² n), el segundo caso ampliado del teorema maestro.

Respuesta

B · Θ(n log² n)
3.Estructuras de datos

Respuesta: D · O(V + E)

Por qué esta es la respuesta

Cada vértice tiene una lista y cada arista aparece una vez (dirigido) o dos veces (no dirigido), lo que da O(V + E).

Respuesta

D · O(V + E)
4.Estructuras de datos

Respuesta: C · Un max-heap de tamaño k, sustituyendo su raíz cuando llega un valor menor

Por qué esta es la respuesta

La raíz del max-heap es el mayor valor conservado; cualquier valor nuevo menor la sustituye en O(log k), así que el montículo siempre contiene los k menores vistos hasta el momento.

Respuesta

C · Un max-heap de tamaño k, sustituyendo su raíz cuando llega un valor menor
5.Teoría de grafos

Respuesta: ninguna de las dos

Euler, Hamilton y árboles: un grafo conexo tiene un circuito euleriano (cada arista una vez, volviendo al inicio) cuando todos los vértices tienen grado par, y un camino euleriano que no es un circuito cuando exactamente dos vértices tienen grado impar; entonces el camino va de un vértice impar al otro. Un circuito hamiltoniano visita cada vértice una vez; Kn tiene (n − 1)!/2 de ellos. Un árbol de n vértices tiene n − 1 aristas, y un grafo conexo con m aristas conserva un árbol generador tras quitarle m − n + 1 aristas.

Grados

deg(A) = 2, deg(B) = 3, deg(C) = 3, deg(D) = 2, deg(E) = 3, deg(F) = 1

Vértices impares

B, C, E, F → 4
ninguna de las dos

Respuesta

ninguna de las dos
6.Teoría de grafos

Respuesta: W = 39

Caminos mínimos y árboles generadores: el algoritmo de Dijkstra fija un vértice por ronda: el vértice no fijado con la menor distancia provisional. Su distancia es entonces definitiva, y cada vecino v recibe d(v) = min(d(v), d(u) + w(u, v)). El algoritmo de Kruskal construye un árbol generador mínimo tomando las aristas de la más ligera a la más pesada y descartando toda arista que cierre un ciclo; el algoritmo de Prim hace crecer un único árbol desde un vértice inicial añadiendo siempre la arista más ligera que sale de él. Un árbol generador de n vértices tiene n − 1 aristas.

Algoritmo de Kruskal

BC (4): tomar
BE (5): tomar
AB (6): tomar
DE (10): tomar
CE (12): descartar, cierra un ciclo
DF (14): tomar

Peso total

W = 4 + 5 + 6 + 10 + 14 = 39

Respuesta

W = 39

ExamProblems · examproblems.com/courses/data-structures-and-algorithms