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

¿Qué mide el análisis amortizado?

  1. AEl coste esperado con entradas aleatorias
  2. BEl coste medio por operación a lo largo de una secuencia de operaciones del peor caso
  3. CEl coste de un algoritmo con la mejor entrada
  4. DEl coste de la única operación más cara de toda la secuencia
2.Algoritmos y complejidadDifícil

¿Cuál de estos problemas de satisfacibilidad se sabe que es resoluble en tiempo polinómico?

  1. ALa satisfacibilidad de circuitos
  2. B3-SAT, donde cada cláusula tiene exactamente tres literales
  3. CSAT general sobre fórmulas en forma normal conjuntiva
  4. D2-SAT, donde cada cláusula tiene como mucho dos literales
3.Estructuras de datosMedia

Los árboles AVL y los árboles rojo-negro garantizan:

  1. AUna altura O(log n) mediante el rebalanceo
  2. BBúsqueda en tiempo constante en todos los casos
  3. CQue ningún nodo tenga dos hijos
  4. DQue las claves se almacenen en orden de inserción
4.Estructuras de datosDifícil

Un filtro de Bloom puede responder a «¿está este elemento en el conjunto?» con:

  1. ARespuestas siempre exactas
  2. BPosibles falsos positivos, pero sin falsos negativos
  3. CRespuestas solo para números
  4. DPosibles falsos negativos, pero sin falsos positivos
5.Teoría de grafosMedia

¿Cuántos circuitos de Hamilton distintos, H, tiene el grafo completo K8? Los circuitos que solo difieren en el vértice inicial o en el sentido cuentan como el mismo.

K8
H =
6.Teoría de grafosDifícil
151781195169210ABCDEFG

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: B · El coste medio por operación a lo largo de una secuencia de operaciones del peor caso

Por qué esta es la respuesta

El análisis amortizado reparte el coste de las operaciones caras y poco frecuentes entre muchas baratas, lo que da una media garantizada para cualquier secuencia.

Respuesta

B · El coste medio por operación a lo largo de una secuencia de operaciones del peor caso
2.Algoritmos y complejidad

Respuesta: D · 2-SAT, donde cada cláusula tiene como mucho dos literales

Por qué esta es la respuesta

2-SAT está en P (tiempo lineal mediante componentes fuertemente conexas), mientras que 3-SAT es NP-completo.

Respuesta

D · 2-SAT, donde cada cláusula tiene como mucho dos literales
3.Estructuras de datos

Respuesta: A · Una altura O(log n) mediante el rebalanceo

Por qué esta es la respuesta

Los árboles autobalanceados mantienen una altura logarítmica, así que la búsqueda, la inserción y la eliminación son O(log n) en el peor caso.

Respuesta

A · Una altura O(log n) mediante el rebalanceo
4.Estructuras de datos

Respuesta: B · Posibles falsos positivos, pero sin falsos negativos

Por qué esta es la respuesta

Si algún bit de un elemento es 0, seguro que no está; si todos son 1, probablemente está. Los filtros de Bloom sacrifican precisión a cambio de usar muy poca memoria.

Respuesta

B · Posibles falsos positivos, pero sin falsos negativos
5.Teoría de grafos

Respuesta: H = 2520

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.

Contar

H = (8 − 1)!/2 = 5040/2 = 2520

Respuesta

H = 2520
6.Teoría de grafos

Respuesta: W = 40

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 (2): tomar
DF (5): tomar
BC (8): tomar
GB (9): tomar
GE (10): descartar, cierra un ciclo
AB (15): tomar

Peso total

W = 1 + 2 + 5 + 8 + 9 + 15 = 40

Respuesta

W = 40

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