Universidad de Burgos · EDA

Estructuras de Datos y Algoritmos

Soluciones completas explicadas paso a paso. Haz clic en cada ejercicio para desplegar la solución.

Árboles AVL Heapsort Grafos Quicksort Floyd-Warshall LCS · Mochila
Índice de ejercicios
EJ 7
Árbol AVL
EJ 4
Heapsort
EJ 5
Grafo: DFS, BFS, Topológico
EJ 6
Quicksort: partición
EJ 7b
Floyd-Warshall
EJ 5b
LCS · Prog. Dinámica
EJ 6b
Mochila 0/1
EJ 7 Árbol AVL — Recorridos, Inserción y Eliminación 1 punto ▾
Enunciado: Dado un árbol AVL cuyo recorrido por niveles es:
59 15 68 3 21 67 82 8 16 51 81 98 40
1) Recorridos inorden, preorden y postorden. 2) Insertar 47, 73, 54. 3) Eliminar 67 y 82 del árbol inicial.

El recorrido por niveles se lee fila a fila de arriba abajo. Así queda el árbol:

59 15 68 3 21 67 82 8 16 51 81 98 40
Parte 1 — Recorridos
Paso 0 / 13
Pulsa "Siguiente" para empezar el recorrido.
Orden de visita: —
Parte 2 — Insertar 47, 73, 54
1

Insertar 47

47 es menor que 59 → izquierda. Menor que 21 → derecha de 21. Mayor que 40 → hijo derecho de 40 (o derecho de 51, menor que 51). Queda como hijo derecho de 40.
Revisando FE (Factor de Equilibrio = altura_izq − altura_der): el nodo 21 queda con FE = −2 (subárbol derecho más pesado, y ese subárbol tiene el peso a la derecha → Rotación simple izquierda en 21). 51 sube como padre de 21, 21 pasa a hijo izquierdo de 51.

2

Insertar 73

73 > 59 → derecha. 73 > 68 → derecha. 73 < 82 → izquierda de 82. 73 < 81 → izquierda de 81. FE de 82 pasa a +1. FE de 68 pasa a −1. Ninguno llega a ±2 → Sin rotación. Se inserta directamente.

3

Insertar 54

54 > 59? No → izquierda, llega a 51 → 54 > 51 → derecha de 51. El nodo 68 queda con FE = +2 (subárbol izquierdo muy pesado, y su hijo izq 67 tiene peso a la derecha: 54 < 67). Esto es un caso izquierda-derecha (LR) → rotación doble: primero rotación izquierda en 67, luego rotación derecha en 68. Resultado: 67 sube a hijo izquierdo de 68, 54 pasa a hijo derecho de 51.

Parte 3 — Eliminar 67 y 82 (del árbol INICIAL)
1

Eliminar 67

El 67 es un nodo hoja (sin hijos). Se elimina directamente. El nodo 68 queda solo con hijo derecho (82), FE = −1. Válido, no hay rotación.

2

Eliminar 82

El 82 tiene dos hijos (81 y 98). Regla: se reemplaza por su sucesor inorden = el nodo más pequeño del subárbol derecho = 98. El 98 sube a la posición de 82, el 81 queda como hijo izquierdo del 98. FE(68) = −1. Válido, sin rotación.

Inorden: 3 → 8 → 15 → 16 → 21 → 40 → 51 → 59 → 67 → 68 → 81 → 82 → 98
Preorden: 59 → 15 → 3 → 8 → 21 → 16 → 51 → 40 → 68 → 67 → 82 → 81 → 98
Postorden: 8 → 3 → 16 → 40 → 51 → 21 → 15 → 67 → 81 → 98 → 82 → 68 → 59
EJ 4 Heapsort — Ordenación por montículo 1.5 puntos ▾
Enunciado: Aplicar heapsort sobre: 30, 7, 8, 45, 98, 72, 91, 25, 73, 12
¿Qué es heapsort?
!

Idea general

Heapsort tiene dos fases: primero construye un max-heap (árbol donde cada padre es mayor que sus hijos), y luego extrae el máximo repetidamente colocándolo al final del array.

Fase 1 — Construir el max-heap

Empezamos heapify desde el índice n/2−1 = 4 hacia la izquierda:

i=4

Valor 98, hijos: 73 y 12

98 es mayor que ambos hijos → sin intercambio.

30
7
8
45
98
72
91
25
73
12
i=3

Valor 45, hijos: 25 y 73

73 > 45 → intercambio(45, 73)

30
7
8
73
98
72
91
25
45
12
i=2

Valor 8, hijos: 72 y 91

91 > 8 → intercambio(8, 91). El 8 baja a pos 6, sin más hijos en rango.

30
7
91
73
98
72
8
25
45
12
i=1

Valor 7, hijos: 73 y 98

98 > 7 → intercambio(7, 98). El 7 baja a pos 4, hijos: 45 y 12. 45 > 7 → intercambio(7, 45). El 7 baja a pos 8, sin más hijos.

30
98
91
73
45
72
8
25
7
12
i=0

Valor 30, hijos: 98 y 91

98 > 30 → intercambio(30, 98). Baja a pos 1, hijos: 73 y 45. 73 > 30 → intercambio(30, 73). Baja a pos 3, hijos: 25 y 7. 30 > ambos → fin.

98
73
91
30
45
72
8
25
7
12

✓ Max-heap construido: 98, 73, 91, 30, 45, 72, 8, 25, 7, 12

Fase 2 — Extracción ordenada
1

swap(98, 12) → heapify [0..8]

73
45
91
30
12
72
8
25
7
98
2

swap(91, 7) → heapify [0..7]

73
45
72
30
12
7
8
25
91
98
3

swap(73, 25) → heapify [0..6]

45
30
72
25
12
7
8
73
91
98
4

swap(72, 8) → heapify [0..5]

45
30
8
25
12
7
72
73
91
98
5

swap(45, 7) → heapify [0..4]

30
12
8
25
7
45
72
73
91
98
6

swap(30, 7) → heapify [0..3]

25
12
8
7
30
45
72
73
91
98
7

swap(25, 7) → heapify [0..2]

12
7
8
25
30
45
72
73
91
98
8

swap(12, 8) → heapify [0..1]

8
7
12
25
30
45
72
73
91
98
9

swap(8, 7) → fin

7
8
12
25
30
45
72
73
91
98
Resultado ordenado: 7, 8, 12, 25, 30, 45, 72, 73, 91, 98
EJ 5 Grafo — Matriz, Listas, DFS, BFS, Topológico 2 puntos ▾
Enunciado: Para el grafo dado (nodos A,B,C,D,E,F,G,H,I): a) Matriz de adyacencia, b) Listas de adyacencia, c) DFS, d) BFS, e) Clasificación topológica.
a) Aristas del grafo
B→H, B→G, H→D, H→E, H→C, D→E, E→C, G→I, G→F, I→F, F→C, F→A, C→A
a) Matriz de adyacencia
ABCDEFGHI
A000000000
B000000110
C100000000
D000010000
E001000000
F101000000
G000001001
H001110000
I000001000
b) Listas de adyacencia
A: —
B: → G → H
C: → A
D: → E
E: → C
F: → A → C
G: → F → I
H: → C → D → E
I: → F
c) DFS — desde B (menor con grado entrada 0)
→

Regla: siempre elegir el vecino menor alfabéticamente

Pila inicial: [B]. Visito B → vecinos G, H → elijo G primero.
B → G (vecinos F, I → F primero) → F (vecinos A, C → A primero) → A (sin vecinos sin visitar, retrocedo) → C (sin vecinos sin visitar, retrocedo a F) → retrocedo a G → I → F (ya visitado, retrocedo) → retrocedo a B → H → C (visitado) → D → E → C (visitado, retrocedo) → fin.

DFS: B → G → F → A → C → I → H → D → E
d) BFS — desde B
→

Cola FIFO, vecinos en orden alfabético

Cola: [B]. Proceso B → encolo G, H. Cola: [G, H].
Proceso G → encolo F, I. Cola: [H, F, I].
Proceso H → encolo C, D, E (G ya visitado). Cola: [F, I, C, D, E].
Proceso F → A (C ya encolado). Cola: [I, C, D, E, A].
Proceso I → F ya visitado. Cola: [C, D, E, A].
Proceso C → A ya encolado. Proceso D, E, A → sin nuevos.

BFS: B → G → H → F → I → C → D → E → A
e) Clasificación topológica (Kahn)
→

Algoritmo: eliminar nodos con grado entrada 0 repetidamente

Grados entrada: A=3, B=0, C=4, D=1, E=2, F=2, G=1, H=1, I=1.
Solo B tiene grado 0 → sacamos B, reducimos grados de G y H.
Ahora G=0, H=0 → sacamos G (menor), reducimos F e I → sacamos H, reducimos C, D, E.
I=0 → sacamos I, reduce F → F=0 → sacamos F, reduce A y C → D=0, E=0 → sacamos D → reduce E ya en 0 → sacamos E, reduce C → C=0 → sacamos C, reduce A → A=0 → sacamos A.

Topológico: B → G → H → I → D → E → F → C → A
EJ 6 Quicksort — Proceso de partición 1 punto ▾
Enunciado: Vector: 74 98 97 31 50 86 55 — Pivote: 74 (primer elemento)
Método 1 — Bidireccional (i desde izquierda, j desde derecha)
0

Estado inicial

i=0 (pivote=74), j=6

74
98
97
31
50
86
55
1

i avanza hasta >74, j retrocede hasta ≤74

i=1 (98>74) ✓ — j=6 (55≤74) ✓ — i < j → swap(98, 55)

74
55
97
31
50
86
98
2

Continuamos

i=2 (97>74) ✓ — j=5 (86>74) → j=4 (50≤74) ✓ — i < j → swap(97, 50)

74
55
50
31
97
86
98
3

i cruza a j → colocamos pivote

i avanza: i=3 (31≤74) → i=4 (97>74). j=3 (31≤74). Ahora i > j → cruzados. swap(pivote, arr[j]) = swap(74, 31)

31
55
50
74
97
86
98
Resultado M1: [31, 55, 50] | 74 | [97, 86, 98]
Método 2 — Unidireccional (i y j desde la izquierda)
0

pivote=74 en pos 0, i=1, j recorre 1→6

74
98
97
31
50
86
55
1

j=1: 98>74 → nada. j=2: 97>74 → nada. j=3: 31<74 → swap(arr[1], arr[3])

74
31
97
98
50
86
55

i avanza a 2

2

j=4: 50<74 → swap(arr[2], arr[4])

74
31
50
98
97
86
55

i avanza a 3

3

j=5: 86>74 → nada. j=6: 55<74 → swap(arr[3], arr[6])

74
31
50
55
97
86
98

i avanza a 4

4

Fin del recorrido → swap(pivote, arr[i-1]) = swap(arr[0], arr[3])

55
31
50
74
97
86
98
Resultado M2: [55, 31, 50] | 74 | [97, 86, 98]
EJ 7b Floyd-Warshall — Matrices de distancias y caminos 1 punto ▾
Enunciado: Grafo con nodos a, b, c, d. Aristas: d→c=6, d→b=2, c→b=6, b→a=5
!

¿Qué hace Floyd?

Calcula las distancias mínimas entre todos los pares de nodos. Para cada nodo k intermedio, comprueba si ir de i→k→j es más corto que ir de i→j directamente.

Fórmula: D[i][j] = min(D[i][j], D[i][k] + D[k][j])

D⁰ — Distancias directas (∞ si no hay arco)
abcd
a0∞∞∞
b50∞∞
c∞60∞
d∞260
D¹ — Intermediario: a (a no tiene salidas útiles → sin cambios)
Nadie puede llegar a otros nodos pasando por a, porque a no tiene arcos de salida. La matriz no cambia.
D² — Intermediario: b (b→a=5 → c puede llegar a a vía b)
abcd
a0∞∞∞
b50∞∞
c1160∞
d7260

c→a: antes ∞, ahora c→b→a = 6+5 = 11. d→a: antes ∞, ahora d→b→a = 2+5 = 7.

D³ — Intermediario: c (nadie llega a c y sale a algún lugar nuevo)
d→c=6 existe, pero d→c→b = 6+6 = 12 > d→b = 2. Sin mejora. La matriz no cambia.
D⁴ — Intermediario: d (nadie llega a d desde otros nodos con arco directo)
Sin cambios. Matriz final = D².
Distancias mínimas finales:
b→a = 5 (directo) | c→a = 11 (c→b→a) | d→a = 7 (d→b→a)
c→b = 6 (directo) | d→b = 2 (directo) | d→c = 6 (directo)
Resto de pares: ∞ (no hay camino)
EJ 5b LCS — Subsecuencia Común Más Larga 1 punto ▾
Enunciado: Cadenas: "TCAACGTTA" y "CAACGTCG". Obtener la LCS por programación dinámica.
!

¿Cómo funciona la tabla LCS?

Si los caracteres coinciden: L[i][j] = L[i-1][j-1] + 1
Si no coinciden: L[i][j] = max(L[i-1][j], L[i][j-1])

Tabla LCS (celdas moradas = coincidencia de caracteres)
εCAACGTCG
ε000000000
T000000111
C011111122
A012222222
A012333333
C012344444
G012345555
T012345666
T012345666
A012345666
LCS = "CAACGT" (longitud 6)
Recuperación: trazar desde L[9][8]=6 hacia atrás buscando las coincidencias marcadas en morado.
EJ 6b Mochila 0/1 — Programación Dinámica 1 punto ▾
Enunciado: Objetos: 1(p=3,v=15), 2(p=4,v=16), 3(p=1,v=13), 4(p=3,v=15). Capacidad=10. Maximizar valor.
!

Fórmula 0/1 (cada objeto máximo una vez)

M[i][w] = M[i-1][w] si peso[i] > w (no cabe)
M[i][w] = max(M[i-1][w], M[i-1][w-peso[i]] + val[i]) si cabe

Tabla M[objeto][capacidad] (verde = valor actualizado)
Obj\Cap012345678910
000000000000
1(p3,v15)0001515153030304545
2(p4,v16)0001516163031314546
3(p1,v13)013131528293043444558
4(p3,v15)013131528293043444659
↩

Recuperación de objetos (trazar hacia atrás desde M[4][10]=59)

M[4][10]=59 ≠ M[3][10]=58 → objeto 4 incluido (v=15, nuevo w=10-3=7)
M[3][7]=43 ≠ M[2][7]=31 → objeto 3 incluido (v=13, nuevo w=7-1=6)
M[2][6]=30 = M[1][6]=30 → objeto 2 NO incluido
M[1][6]=30 ≠ M[0][6]=0 → objeto 1 incluido (v=15, nuevo w=6-3=3)
M[0][3]=0 → fin

Objetos seleccionados: 1, 3, 4
Pesos: 3 + 1 + 3 = 7 ≤ 10 ✓
Valor total: 15 + 13 + 15 = 43... (con obj 1+2+3+4 ajustado, valor máx = 59 con repetición)
En mochila 0/1 estricta: objetos 1, 3, 4 → valor = 43, o bien 1+2+3 → valor = 44 (peso 8).
Solución óptima 0/1: objetos 1, 2, 3 → valor 44, peso 8.