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 − 1) + O(1)?

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

Para demostrar que un problema nuevo X es NP-difícil, ¿qué hay que hacer?

  1. ADemostrar que X no tiene algoritmo polinómico para entradas pequeñas
  2. BDemostrar que X puede verificarse en tiempo polinómico
  3. CReducir en tiempo polinómico X a un problema NP-difícil conocido
  4. DReducir en tiempo polinómico un problema NP-difícil conocido a X
3.Estructuras de datosMedia

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

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

Un nodo AVL está desequilibrado porque el subárbol derecho de su hijo izquierdo ha quedado demasiado alto (caso izquierda-derecha). ¿Qué corrección se aplica?

  1. AUna rotación a la izquierda en el hijo izquierdo y luego una rotación a la derecha en el nodo
  2. BUna rotación simple a la derecha en el nodo
  3. CUna rotación a la derecha en el hijo izquierdo y luego una rotación a la izquierda en el nodo
  4. DUna rotación simple a la izquierda en el nodo
5.Teoría de grafosMedia

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

3 × deg 34 × deg 42 × deg 5
L =
6.Teoría de grafosDifícil
191718148315620ABCDEFG

El algoritmo de Kruskal construye un árbol generador mínimo. Haz clic en la arista que añade como arista número 4; las aristas descartadas no cuentan.

k = 4
  1. 1arista AB
  2. 2arista BC
  3. 3arista BD
  4. 4arista DE
  5. 5arista DF
  6. 6arista EF
  7. 7arista GB
  8. 8arista GC
  9. 9arista GD

3Disoluciones

1.Algoritmos y complejidad

Respuesta: C · O(2ⁿ)

Por qué esta es la respuesta

El número de llamadas se duplica en cada nivel y hay n niveles, así que el total es de unos 2ⁿ, como en las torres de Hanói.

Respuesta

C · O(2ⁿ)
2.Algoritmos y complejidad

Respuesta: D · Reducir en tiempo polinómico un problema NP-difícil conocido a X

Por qué esta es la respuesta

Si un problema difícil conocido puede transformarse eficientemente en X, un algoritmo rápido para X resolvería también el problema conocido.

Respuesta

D · Reducir en tiempo polinómico un problema NP-difícil conocido a X
3.Estructuras de datos

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

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

Respuesta: A · Una rotación a la izquierda en el hijo izquierdo y luego una rotación a la derecha en el nodo

Por qué esta es la respuesta

La primera rotación convierte el caso izquierda-derecha en un caso izquierda-izquierda, que luego corrige una rotación a la derecha en el nodo desequilibrado.

Respuesta

A · Una rotación a la izquierda en el hijo izquierdo y luego una rotación a la derecha en el nodo
5.Teoría de grafos

Respuesta: L = 19

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 + 35 = 2(L + 9) − 2
L = 19

Respuesta

L = 19

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

6.Teoría de grafos

Respuesta: arista GB

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

1. EF (3)
2. GC (6)
3. DF (8)
4. GB (15)
5. BD (18)
6. AB (19)

arista número 4

GB

Respuesta

arista GB

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