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

¿Qué estableció el teorema de Cook-Levin?

  1. AEl problema de satisfacibilidad booleana (SAT) es NP-completo
  2. BEl problema de la parada es indecidible
  3. CTodo problema NP puede resolverse en tiempo exponencial
  4. DP no es igual a NP
3.Estructuras de datosMedia

¿Qué ocurre cuando una tabla hash hace un rehash porque su factor de carga supera un umbral?

  1. ASe reserva una tabla mayor y se vuelve a insertar cada clave
  2. BSe eliminan las claves más antiguas para hacer sitio
  3. CLas claves existentes se ordenan en su sitio
  4. DSolo las claves que colisionan se mueven a una lista de desbordamiento nueva al final de la tabla
4.Estructuras de datosDifícil

Un árbol de segmentos (segment tree) se usa normalmente para:

  1. AOrdenar cadenas alfabéticamente almacenando cada prefijo en un nodo distinto del árbol
  2. BImplementar una pila
  3. CAlmacenar las aristas de un grafo
  4. DResponder consultas por rangos (como sumas de rangos) y actualizaciones en O(log n)
5.Teoría de grafosMedia

Un grafo conexo tiene 15 vértices y 22 aristas. ¿Cuántas aristas, k, hay que quitar para obtener un árbol generador?

|V| = 15|E| = 22
k =
6.Teoría de grafosDifícil
ABCDEF

¿Cuántos recorridos cerrados de longitud 2 empiezan y terminan en D? Un recorrido puede repetir vértices y aristas. Llama al número N.

M = matriz de adyacenciaL = 2
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: A · El problema de satisfacibilidad booleana (SAT) es NP-completo

Por qué esta es la respuesta

Cook y Levin demostraron de forma independiente que todo problema de NP se reduce a SAT en tiempo polinómico, así que SAT fue el primer problema NP-completo conocido.

Respuesta

A · El problema de satisfacibilidad booleana (SAT) es NP-completo
3.Estructuras de datos

Respuesta: A · Se reserva una tabla mayor y se vuelve a insertar cada clave

Por qué esta es la respuesta

Como el índice se calcula módulo el tamaño de la tabla, todas las claves deben redistribuirse en la tabla nueva y mayor; duplicando el tamaño, esto sigue siendo O(1) amortizado.

Respuesta

A · Se reserva una tabla mayor y se vuelve a insertar cada clave
4.Estructuras de datos

Respuesta: D · Responder consultas por rangos (como sumas de rangos) y actualizaciones en O(log n)

Por qué esta es la respuesta

Un árbol de segmentos almacena agregados de intervalos y permite consultas por rangos y actualizaciones puntuales en tiempo O(log n).

Respuesta

D · Responder consultas por rangos (como sumas de rangos) y actualizaciones en O(log n)
5.Teoría de grafos

Respuesta: k = 8

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.

Aristas de un árbol generador

15 − 1 = 14

Aristas que quitar

k = 22 − 14 = 8

Respuesta

k = 8
6.Teoría de grafos

Respuesta: N = 3

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 0
B: 1 0 1 1 1 0
C: 1 1 0 0 1 0
D: 0 1 0 0 1 1
E: 0 1 1 1 0 1
F: 0 0 0 1 1 0

Vecinos comunes

(M²)DD = 0·0 + 1·1 + 0·0 + 0·0 + 1·1 + 1·1 = 3

Respuesta

N = 3

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