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(log n)
  4. DO(n log n)
2.Algoritmos y complejidadDifícil

El algoritmo de programación dinámica de Held-Karp resuelve exactamente el problema del viajante. ¿Cuál es su tiempo de ejecución para n ciudades?

  1. AO(n!)
  2. BO(n² 2ⁿ)
  3. CO(2n²)
  4. DO(n³)
3.Estructuras de datosMedia

Un árbol binario tiene la raíz 1 con hijo izquierdo 2 e hijo derecho 3; el nodo 2 tiene los hijos 4 (izquierdo) y 5 (derecho). ¿Cuál es el recorrido en postorden?

  1. A1 2 4 5 3
  2. B5 4 3 2 1
  3. C4 5 2 3 1
  4. D4 2 5 1 3
4.Estructuras de datosDifícil

Las claves 5, 3, 8, 1 se insertan en este orden en un min-heap binario vacío basado en un arreglo. ¿Cuál es el arreglo final?

  1. A[3, 1, 8, 5]
  2. B[1, 5, 8, 3]
  3. C[1, 3, 8, 5]
  4. D[1, 3, 5, 8]
5.Teoría de grafosMedia
ABCDECircuito 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| = 5|E| = 6
  1. 1Circuito euleriano
  2. 2Camino euleriano, sin circuito
  3. 3ninguna de las dos
6.Teoría de grafosDifícil
ABCDE

¿Cuántos recorridos de longitud 3 van de E a B? Un recorrido puede repetir vértices y aristas. Llama al número N.

M = matriz de adyacenciaL = 3
N =

3Disoluciones

1.Algoritmos y complejidad

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

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

Respuesta: B · O(n² 2ⁿ)

Por qué esta es la respuesta

Hay unos n 2ⁿ estados, y cada uno se calcula en O(n); es exponencial, pero mucho más rápido que probar los (n − 1)! recorridos.

Respuesta

B · O(n² 2ⁿ)
3.Estructuras de datos

Respuesta: C · 4 5 2 3 1

Por qué esta es la respuesta

El postorden procesa 4 y 5 antes que 2, luego 3 y, por último, la raíz 1.

Respuesta

C · 4 5 2 3 1
4.Estructuras de datos

Respuesta: C · [1, 3, 8, 5]

Por qué esta es la respuesta

Tras 5, 3, 8 el arreglo es [3, 5, 8]; 1 va al índice 3, se intercambia con su padre 5 y luego con 3, lo que da [1, 3, 8, 5].

Respuesta

C · [1, 3, 8, 5]
5.Teoría de grafos

Respuesta: Circuito euleriano

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) = 4, deg(C) = 2, deg(D) = 2, deg(E) = 2

Vértices impares

0
Circuito euleriano

Respuesta

Circuito euleriano
6.Teoría de grafos

Respuesta: N = 1

Grados: el grado de un vértice es el número de aristas que inciden en él. Cada arista tiene dos extremos, así que los grados suman el doble del número de aristas: Σ gr(v) = 2|E| (el lema del apretón de manos). Por tanto, el número de vértices de grado impar es par. Kn tiene n(n − 1)/2 aristas, un grafo k-regular de n vértices tiene nk/2, y un árbol de n vértices tiene n − 1 aristas.

Matriz de adyacencia

A: 0 1 1 0 0
B: 1 0 1 1 0
C: 1 1 0 0 1
D: 0 1 0 0 1
E: 0 0 1 1 0

Un paso más

(M³)EB = 1·1 + 2·0 + 0·1 + 0·1 + 2·0 = 1

Respuesta

N = 1

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