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 complejidad temporal de: para i = 1 hasta n: (j = 1; mientras j < n: j = j × 2)?

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

¿Qué cota es correcta para log(n!)?

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

¿Cómo funciona extract-min en un min-heap binario?

  1. ASe mueve el último elemento a la raíz y se hace bajar (sift-down)
  2. BSe elimina el último elemento del arreglo
  3. CSe buscan en todas las hojas el nuevo mínimo
  4. DSe elimina la raíz y se desplazan todos los elementos una posición a la izquierda
4.Estructuras de datosDifícil

¿Qué hace un splay tree después de cada acceso?

  1. ASube mediante rotaciones el nodo accedido hasta la raíz
  2. BMueve el nodo accedido a una hoja
  3. CReconstruye todo el árbol en forma balanceada
  4. DRecolorea los nodos del camino de búsqueda
5.Teoría de grafosMedia

Un árbol tiene 2 vértices de grado 3, 2 vértices de grado 5, y todos sus demás vértices son hojas (grado 1). ¿Cuántas hojas, L, tiene?

2 × deg 32 × deg 5
L =
6.Teoría de grafosDifícil
1410931432129ABCDEFG

Usa el algoritmo de Dijkstra para hallar la longitud d(F) del camino más corto de A a F en el grafo ponderado.

inicio: Afin: F
d(F) =

3Disoluciones

1.Algoritmos y complejidad

Respuesta: C · O(n log n)

Por qué esta es la respuesta

El bucle interior se ejecuta unas log₂ n veces por cada una de las n iteraciones exteriores, lo que da O(n log n).

Respuesta

C · O(n log n)
2.Algoritmos y complejidad

Respuesta: D · Θ(n log n)

Por qué esta es la respuesta

log(n!) ≤ n log n, y los n / 2 factores mayores dan log(n!) ≥ (n / 2) log(n / 2); por eso la ordenación por comparaciones necesita Ω(n log n).

Respuesta

D · Θ(n log n)
3.Estructuras de datos

Respuesta: A · Se mueve el último elemento a la raíz y se hace bajar (sift-down)

Por qué esta es la respuesta

El último elemento ocupa el hueco de la raíz y se intercambia con su hijo menor hasta que se cumple la propiedad de montículo, lo que cuesta O(log n).

Respuesta

A · Se mueve el último elemento a la raíz y se hace bajar (sift-down)
4.Estructuras de datos

Respuesta: A · Sube mediante rotaciones el nodo accedido hasta la raíz

Por qué esta es la respuesta

El splaying lleva el nodo accedido a la raíz mediante rotaciones; una sola operación puede costar O(n), pero el coste amortizado es O(log n).

Respuesta

A · Sube mediante rotaciones el nodo accedido hasta la raíz
5.Teoría de grafos

Respuesta: L = 10

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.

Lema del apretón de manos para un árbol

L + 16 = 2(L + 4) − 2
L = 10

Respuesta

L = 10

Atajo: L = 2 + Σ (d − 2) sobre los vértices de grado d ≥ 3.

6.Teoría de grafos

Respuesta: d(F) = 26

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.

Dijkstra ronda a ronda

Cada línea: el vértice fijado, su distancia definitiva y los vecinos cuya distancia mejora.

A (0): B: 14
B (14): C: 24, D: 23, G: 26
D (23): E: 37, F: 26
C (24): E: 27
F (26)
G (26)
E (27)

Camino más corto

A → B → D → F
d(F) = 26

Respuesta

d(F) = 26

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