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

Una función ejecuta un bucle de n iteraciones y después, por separado, otro bucle de n iteraciones. ¿Cuál es su complejidad temporal?

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

¿Cómo se clasifica el problema del viajante?

  1. ALa versión de decisión está en P, pero la de optimización es NP-completa
  2. BEs indecidible
  3. CEstá en P porque el algoritmo de Dijkstra lo resuelve visitando cada ciudad una vez
  4. DLa versión de decisión es NP-completa y la de optimización es NP-difícil
3.Estructuras de datosMedia

Un recorrido en orden (in-order) de un árbol binario de búsqueda visita las claves en:

  1. AOrden de inserción
  2. BOrden por niveles
  3. COrden ascendente
  4. DSiempre orden descendente
4.Estructuras de datosDifícil

¿Qué garantía dan las reglas del árbol rojo-negro sobre la altura de un árbol con n claves?

  1. ALa altura es como máximo log2 n + 1
  2. BLa altura es exactamente log2 n
  3. CLa altura es como máximo n / 2
  4. DLa altura es como máximo 2 log2(n + 1)
5.Teoría de grafosMedia

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

3 × deg 34 × deg 43 × deg 53 × deg 2
L =
6.Teoría de grafosDifícil
10171616984193ABCDEFG

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

|V| = 7|E| = 10
W =

3Disoluciones

1.Algoritmos y complejidad

Respuesta: D · O(n)

Por qué esta es la respuesta

n + n = 2n, y los factores constantes se eliminan, así que la función es O(n).

Respuesta

D · O(n)
2.Algoritmos y complejidad

Respuesta: D · La versión de decisión es NP-completa y la de optimización es NP-difícil

Por qué esta es la respuesta

«¿Hay un recorrido de longitud como mucho k?» es NP-completo; hallar el recorrido más corto es NP-difícil, porque es al menos igual de difícil.

Respuesta

D · La versión de decisión es NP-completa y la de optimización es NP-difícil
3.Estructuras de datos

Respuesta: C · Orden ascendente

Por qué esta es la respuesta

Visitar el subárbol izquierdo, luego el nodo y luego el subárbol derecho produce las claves del BST ordenadas.

Respuesta

C · Orden ascendente
4.Estructuras de datos

Respuesta: D · La altura es como máximo 2 log2(n + 1)

Por qué esta es la respuesta

Todos los caminos tienen el mismo número de nodos negros y los nodos rojos no pueden ser adyacentes, así que el camino más largo es como mucho el doble del más corto, lo que da una altura O(log n).

Respuesta

D · La altura es como máximo 2 log2(n + 1)
5.Teoría de grafos

Respuesta: L = 22

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 + 46 = 2(L + 13) − 2
L = 22

Respuesta

L = 22

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

6.Teoría de grafos

Respuesta: W = 32

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

CE (1): tomar
GD (3): tomar
GB (4): tomar
DE (6): tomar
EF (8): tomar
DF (9): descartar, cierra un ciclo
AC (10): tomar

Peso total

W = 1 + 3 + 4 + 6 + 8 + 10 = 32

Respuesta

W = 32

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