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é significa que un problema tenga subestructura óptima?

  1. AEl problema tiene exactamente una solución óptima, que comparten todos sus subproblemas
  2. BUna solución óptima puede construirse a partir de soluciones óptimas de sus subproblemas
  3. CEl problema puede resolverse en tiempo constante
  4. DTodos los subproblemas tienen el mismo tamaño
2.Algoritmos y complejidadDifícil

Los caminos simples más cortos pueden hallarse en tiempo polinómico. ¿Qué se sabe de hallar el camino simple más largo entre dos vértices en un grafo general?

  1. AEs indecidible
  2. BPuede resolverse con el algoritmo de Dijkstra con los pesos cambiados de signo
  3. CSiempre puede resolverse en O(V + E)
  4. DEs NP-difícil
3.Estructuras de datosMedia

¿Qué estructura de datos usa un programa en ejecución para llevar el control de las llamadas a funciones activas y sus variables locales?

  1. ALa cola de memoria del heap
  2. BUna tabla hash de funciones
  3. CLa pila de llamadas
  4. DUn árbol binario de búsqueda de marcos
4.Estructuras de datosDifícil

Para cada elemento de un arreglo quieres el siguiente elemento mayor a su derecha, en un tiempo total O(n). ¿Qué estructura ayuda?

  1. AUna pila que guarda los elementos que esperan su respuesta
  2. BUn árbol binario de búsqueda reconstruido para cada elemento
  3. CUna tabla hash con todos los elementos
  4. DUna cola que contiene todos los pares de elementos
5.Teoría de grafosMedia

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

K4
H =
6.Teoría de grafosDifícil
ABCDE

¿Cuántos recorridos de longitud 2 van de E a C? 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: B · Una solución óptima puede construirse a partir de soluciones óptimas de sus subproblemas

Por qué esta es la respuesta

La subestructura óptima es necesaria para que tanto los algoritmos voraces como la programación dinámica den respuestas correctas.

Respuesta

B · Una solución óptima puede construirse a partir de soluciones óptimas de sus subproblemas
2.Algoritmos y complejidad

Respuesta: D · Es NP-difícil

Por qué esta es la respuesta

Un camino simple más largo de longitud V − 1 es un camino hamiltoniano, un problema NP-completo; en grafos dirigidos acíclicos, en cambio, puede resolverse en tiempo lineal.

Respuesta

D · Es NP-difícil
3.Estructuras de datos

Respuesta: C · La pila de llamadas

Por qué esta es la respuesta

Cada llamada apila un marco de pila y cada retorno lo desapila; por eso la llamada más reciente termina primero.

Respuesta

C · La pila de llamadas
4.Estructuras de datos

Respuesta: A · Una pila que guarda los elementos que esperan su respuesta

Por qué esta es la respuesta

Recorriendo de izquierda a derecha, se desapila cada elemento de la pila menor que el actual (el actual es su respuesta) y luego se apila este; cada elemento se mueve como máximo dos veces.

Respuesta

A · Una pila que guarda los elementos que esperan su respuesta
5.Teoría de grafos

Respuesta: H = 3

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 = (4 − 1)!/2 = 6/2 = 3

Respuesta

H = 3
6.Teoría de grafos

Respuesta: N = 1

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

Vecinos comunes

(M²)EC = 0·1 + 1·1 + 1·0 + 1·0 + 0·1 = 1

Respuesta

N = 1

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