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

La ordenación topológica solo es posible en:

  1. AGrafos con pesos negativos
  2. BGrafos no dirigidos
  3. CGrafos completos
  4. DGrafos dirigidos acíclicos (DAG)
3.Estructuras de datosMedia

¿Cuál es el valor de la expresión en notación postfija 3 4 + 2 * ?

  1. A10
  2. B11
  3. C14
  4. D24
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[1, 5, 8, 3]
  2. B[1, 3, 5, 8]
  3. C[3, 1, 8, 5]
  4. D[1, 3, 8, 5]
5.Teoría de grafosMedia

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

2 × deg 32 × deg 44 × deg 52 × deg 2
L =
6.Teoría de grafosDifícil
1314151117191618ABCDEFG

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 6.

inicio: Ek = 6
  1. 1arista AB
  2. 2arista AC
  3. 3arista BC
  4. 4arista CE
  5. 5arista DE
  6. 6arista DF
  7. 7arista EF
  8. 8arista GB
  9. 9arista GE

3Disoluciones

1.Algoritmos y complejidad

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

A · O(n)
2.Algoritmos y complejidad

Respuesta: D · Grafos dirigidos acíclicos (DAG)

Por qué esta es la respuesta

Existe un orden topológico si y solo si el grafo dirigido no tiene ciclos; se puede encontrar en O(V + E) con DFS o con el algoritmo de Kahn.

Respuesta

D · Grafos dirigidos acíclicos (DAG)
3.Estructuras de datos

Respuesta: C · 14

Por qué esta es la respuesta

Se apilan 3 y 4, + da 7; se apila 2, * da 7 × 2 = 14.

Respuesta

C · 14
4.Estructuras de datos

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

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

Respuesta: L = 20

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 + 38 = 2(L + 10) − 2
L = 20

Respuesta

L = 20

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

6.Teoría de grafos

Respuesta: arista DE

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. EF (1)
2. CE (11)
3. AC (14)
4. AB (13)
5. GB (6)
6. DE (17)

arista número 6

DE

Respuesta

arista DE

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