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 multiplicar dos matrices n × n con el triple bucle estándar?

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

¿Qué afirmación sobre la notación o pequeña es correcta?

  1. An = o(n²), pero n no es o(n)
  2. Bn = o(n), porque toda función es o pequeña de sí misma
  3. Cn² = o(n)
  4. D2n = o(n), porque 2n crece despacio
3.Estructuras de datosMedia

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

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

¿Cuáles son los costes en tiempo y en espacio adicional de invertir en el sitio una lista simplemente enlazada?

  1. ATiempo O(n) y espacio adicional O(1)
  2. BTiempo O(n log n) y espacio adicional O(1)
  3. CTiempo O(1) y espacio adicional O(1)
  4. DTiempo O(n) y espacio adicional O(n)
5.Teoría de grafosMedia

Un grafo conexo tiene 20 vértices y 25 aristas. ¿Cuántas aristas, k, hay que quitar para obtener un árbol generador?

|V| = 20|E| = 25
k =
6.Teoría de grafosDifícil
1219927153ABCDE

El algoritmo de Prim construye un árbol generador mínimo a partir del vértice E. Haz clic en la arista que añade como arista número 4.

inicio: Ek = 4
  1. 1arista AB
  2. 2arista AC
  3. 3arista BC
  4. 4arista BD
  5. 5arista CE
  6. 6arista DE
  7. 7arista BE

3Disoluciones

1.Algoritmos y complejidad

Respuesta: C · O(n³)

Por qué esta es la respuesta

Hay n² entradas y cada una necesita n multiplicaciones, lo que da n³ operaciones.

Respuesta

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

Respuesta: A · n = o(n²), pero n no es o(n)

Por qué esta es la respuesta

f = o(g) significa que f(n) / g(n) tiende a 0; n / n² tiende a 0, pero n / n = 1 no.

Respuesta

A · n = o(n²), pero n no es o(n)
3.Estructuras de datos

Respuesta: B · 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

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

Respuesta: A · Tiempo O(n) y espacio adicional O(1)

Por qué esta es la respuesta

Con tres punteros (anterior, actual, siguiente) se puede invertir cada enlace en una sola pasada sin reservar nodos nuevos.

Respuesta

A · Tiempo O(n) y espacio adicional O(1)
5.Teoría de grafos

Respuesta: k = 6

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.

Aristas de un árbol generador

20 − 1 = 19

Aristas que quitar

k = 25 − 19 = 6

Respuesta

k = 6
6.Teoría de grafos

Respuesta: arista AB

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 Prim

1. BE (3)
2. BD (2)
3. CE (7)
4. AB (12)

arista número 4

AB

Respuesta

arista AB

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