Tareas

Apunte de Cátedra

ESTRUCTURAS
DE
DATOS
Analista de Sistemas y
Licenciatura en Sistemas
Lic. Verónica L. Vanoli
Dra. Sandra I. Casas
Universidad Nacional de la Patagonia Austral
Unidad Académica Río Gallegos

Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos
Docente: Lic. Verónica L. Vanoli
Indice
ANALISIS DE ALGORITMOS
1.- Introducción2.- Soporte matemático
3.- Modelo
4.- ¿Qué analizar?
5.- Cálculo del tiempo de ejecución
5.1.- Un ejemplo sencillo
5.2.- Reglas generales
5.3.- Soluciones al problema de la suma de la subsecuencia máxima
5.4.- Logaritmos en el tiempo de ejecución
5.5.- Verificación del análisis

1
1
1
3
3
5
5
5
7
11
14

ARBOLES
1.- Introducción
2.- Terminología fundamental
2.1.- Orden delos nodos
2.2.- Recorridos de un árbol
2.2.1.- Recorrido en profundidad
2.2.2.- Recorrido en anchura
2.3.- Arboles etiquetados
3.- Arboles binarios
3.1.- TDA árbol binario. Definición
3.2.- Implementaciones de árboles binarios
3.2.1.- Mediante arreglos
3.2.2.- Mediante referencias
3.3.- Arboles binarios de expresión
3.4.- Arboles binarios de búsqueda
3.5.- Arboles binarios balanceados3.5.1.- Arboles binarios balanceados AVL
3.5.1.1.- Inserción en árboles binarios balanceados AVL
3.5.1.2.- Borrado en árboles binarios balanceados AVL
3.5.1.3.- Implementación de árboles binarios balanceados AVL
4.- Arboles multicamino
4.1.- TDA árbol multicamino. Definición
4.2.- Implementaciones de árboles multicamino
4.2.1.- Mediante arreglos
4.2.2.- Mediante listas de hijos
4.2.3.-Basada en árboles binarios
4.3.- Arboles multicamino B
4.3.1.- Búsqueda en árboles multicamino B
4.3.2.- Inserción en árboles multicamino B
4.3.3.- Borrado en árboles multicamino B
4.3.4.- Implementación de árboles multicamino B
4.4.- Arboles multicamino B+
4.4.1.- Búsqueda en árboles multicamino B+
4.4.2.- Inserción en árboles multicamino B+
4.4.3.- Borrado en árboles multicamino B+
4.5.-Arboles multicamino Trie
4.5.1.- Representaciones de árboles multicamino Trie

16
16
16
17
18
18
19
20
20
20
21
21
23
23
24
26
26
26
27
28
32
32
32
32
33
34
35
36
37
37
39
45
46
46
46
47
48

i

Carrera: Analista de Sistemas y Licenciatura en Sistemas
Asignatura: Estructuras de Datos
Docente: Lic. Verónica L. Vanoli
Indice
4.5.2.- Búsqueda, insercióny borrado de árboles multicamino Trie
4.5.3.- Implementación de árboles multicamino Trie
5.- Bosques

49
50
52

GRAFOS
1.- Introducción
2.- Terminología fundamental
2.1.- Representación gráfica de grafos
2.2.- Definiciones básicas en grafos dirigidos
3.- TDA. Grafo
4.- Implementaciones de grafos
4.1.- Mediante matrices de adyacencia
4.2.- Mediante listas de adyacencia
5.-Operaciones sobre grafos
5.1.- Recorridos
5.1.1.- Recorrido en profundidad
5.1.2.- Recorrido en anchura
5.2.- Algoritmos de caminos mínimos
5.2.1.- Algoritmo de Dijkstra
5.2.2.- Algoritmo de Floyd-Warshall
5.2.3.- Algoritmo de Bellman-Ford
5.2.4.- Algoritmo de Ford-Fulkerson
5.2.5.- Algoritmo de Kruskal y Prim
5.3.- Algoritmo de Fleury (recorridos eulerianos)

54
54
54
54
55
59
59
5961
63
63
63
65
66
67
69
70
71
71
71

ALGORITMOS DE ORDENACION
1.- Introducción
2.- Algoritmos básicos de ordenación
2.1.- Ordenación por inserción
2.2.- Ordenación por selección
2.3.- Ordenación por intercambio (burbuja)
2.4.- Ordenación por intercambio (burbuja mejorado)
3.- Algoritmos avanzados de ordenación
3.1.- Ordenación por mezcla (mergesort)
3.2.- Ordenación mediantemontículos (heapsort)
3.3.- Ordenación rápida de Hoare (quicksort)
3.4.- Ordenación por incrementos (shellsort)
3.5.- Ordenación por sacudida o vibración (shakersort)
4.- Otros algoritmos avanzados de ordenación
4.1.- Ordenación por urnas (binsort)
4.2.- Ordenación por residuos (radixsort)

73
73
73
73
75
76
77
77
77
78
80
82
83
84
84
84

ALGORITMOS DE BUSQUEDA
1.-...