Tabla de contenido
Capítulo 1 Introducción 1
1.1 Conceptos básicos de estructura de datos 1
1.1.1 Conceptos básicos y terminología 1
1.1.2 Tres Elementos de la Estructura de Datos 2
1.1.3 Preguntas seleccionadas de esta sección 3
1.1.4 Respuestas y explicaciones 4
1.2 Algoritmos y Evaluación de Algoritmos 4
1.2.1 Conceptos Básicos de Algoritmos 4
1.2.2 Medición de la Eficiencia del Algoritmo 5
1.2.3 Preguntas Seleccionadas en esta Sección 6
1.2.4 Respuestas y Análisis 8
Resumen 11
Pensando 11
Capítulo 2 Tabla Lineal 12
2.1 Definición y operaciones básicas de listas lineales 12
2.1.1 Definición de Lista Lineal 12
2.1.2 Operaciones básicas de tablas lineales 13
2.1.3 Preguntas Seleccionadas en esta Sección 13
2.1.4 Respuestas y Análisis 14
2.2 Representación Secuencial de Listas Lineales 14
2.2.1 Definición de Lista de Secuencia 14
2.2.2 Implementación de operaciones básicas sobre listas de secuencias 15
2.2.3 Preguntas Seleccionadas de esta Sección 18
2.2.4 Respuestas y Análisis 20
2.3 Representación enlazada de listas lineales 30
2.3.1 Definición de una lista enlazada simple 30
2.3.2 Implementación de operaciones básicas en listas enlazadas simples 31
2.3.3 Lista Doblemente Enlazada 35
2.3.4 Lista Enlazada Circular 37
2.3.5 Lista Enlazada Estática 37
2.3.6 Comparación de Lista de Secuencia y Lista Enlazada 38
2.3.7 Preguntas Seleccionadas de esta Sección 39
2.3.8 Respuestas y Análisis 45
Resumen 62
Pensando Expansión 63
Capítulo 3 Pilas, Colas y Arreglos 64
3.1 Pila 64
3.1.1 Conceptos Básicos de Pila 64
3.1.2 Estructura de Almacenamiento Secuencial de Pila 65
3.1.3 Estructura de almacenamiento en cadena de la pila 68
3.1.4 Preguntas Seleccionadas de esta Sección 68
3.1.5 Respuestas y Análisis 71
3.2 Cola 78
3.2.1 Conceptos básicos de colas 78
3.2.2 Estructura de almacenamiento secuencial de cola 78
3.2.3 Estructura de almacenamiento encadenado de colas 81
3.2.4 Cola de doble extremo 82
3.2.5 Preguntas Seleccionadas de esta Sección 84
3.2.6 Respuestas y Análisis 87
3.3 Aplicación de pilas y colas 92
3.3.1 Aplicación de la pila en el emparejamiento de paréntesis 92
3.3.2 El uso de pilas en la evaluación de expresiones 93
3.3.3 Aplicación de la pila en la recursión 95
3.3.4 Aplicación de Colas en Recorrido por Niveles 96
3.3.5 Aplicación de Colas en Sistemas Informáticos 97
3.3.6 Preguntas Seleccionadas de esta Sección 97
3.3.7 Respuestas y Análisis 100
3.4 Arreglos y Matrices Especiales 104
3.4.1 Definición de Arreglo 104
3.4.2 Estructura de Almacenamiento de Arreglos 104
3.4.3 Almacenamiento Comprimido de Matrices Especiales 105
3.4.4 Matrices Dispersas 107
3.4.5 Preguntas Seleccionadas de esta Sección 108
3.4.6 Respuestas y Análisis 109
Resumen 111
Pensando 112
Capítulo 4 Cadena 113
*4.1 Definición e implementación de cadenas 113
4.1.1 Definición de Cadena 113
4.1.2 Estructura de Almacenamiento de Cadenas 114
4.1.3 Operaciones básicas con cadenas 115
4.2 Coincidencia de Patrones de Cadenas 115
4.2.1 Algoritmo de Búsqueda Simple de Patrones 115
4.2.2 Algoritmo de Búsqueda de Patrones de Cadenas - Algoritmo KMP 116
4.2.3 Optimización Adicional del Algoritmo KMP 121
4.2.4 Preguntas Seleccionadas de esta Sección 122
4.2.5 Respuestas y Análisis 123
Resumen 127
Pensando 127
Capítulo 5 Árboles y Árboles Binarios 128
5.1 Conceptos básicos de árboles 128
5.1.1 Definición de un árbol 128
5.1.2 Terminología básica 129
5.1.3 Propiedades de los Árboles 130
5.1.4 Preguntas Seleccionadas de esta Sección 131
5.1.5 Respuestas y Análisis 131
5.2 El concepto de árbol binario 134
5.2.1 Definición y características principales de árbol binario 134
5.2.2 Estructura de Almacenamiento de Árboles Binarios 136
5.2.3 Preguntas Seleccionadas de esta Sección 137
5.2.4 Respuestas y Análisis 140
5.3 Recorrido de Árbol Binario y Árboles Binarios Enhebrados 145
5.3.1 Recorriendo un Árbol Binario 145
5.3.2 Árbol Binario Enhebrado 151
5.3.3 Preguntas Seleccionadas de esta Sección 154
5.3.4 Respuestas y explicaciones 160
5.4 Árboles y bosques 179
5.4.1 Estructura de Almacenamiento de Árboles 179
5.4.2 Transformación entre árboles, bosques y árboles binarios 181
5.4.3 Recorriendo Árboles y Bosques 182
5.4.4 Preguntas seleccionadas de esta sección 183
5.4.5 Respuestas y explicaciones 185
5.5 Aplicaciones de Árboles y Árboles Binarios 201
5.5.1 Árbol de Huffman y Codificación de Huffman 201
5.5.2 Union-Find 194
5.5.3 Preguntas Seleccionadas de esta Sección 196
5.5.4 Respuestas y Análisis 198
Resumen 204
Pensando 204
Capítulo 6 Figura 206
6.1 Conceptos básicos de grafos 206
6.1.1 Definición de Gráfico 206
6.1.2 Preguntas Seleccionadas de esta Sección 210
6.1.3 Respuestas y Análisis 211
6.2 Almacenamiento de Grafos y Operaciones Básicas 214
6.2.1 Método de la Matriz de Adyacencia 214
6.2.2 Método de Lista de Adyacencia 215
6.2.3 Lista de Enlaces Cruzados 217
6.2.4 Multilista de Adyacencia 217
6.2.5 Operaciones básicas en grafos 218
6.2.6 Preguntas Seleccionadas de esta Sección 219
6.2.7 Respuestas y Análisis 222
6.3 Recorrido de Grafos 227
6.3.1 Búsqueda en Anchura 227
6.3.2 Búsqueda en Profundidad 230
6.3.3 Recorrido de Grafos y Conectividad de Grafos 231
6.3.4 Preguntas Seleccionadas de esta Sección 231
6.3.5 Respuestas y Análisis 234
6.4 Aplicación de Grafos 239
6.4.1 Árbol de Expansión Pequeño 239
6.4.2 Ruta Corta 242
6.4.3 Expresión de Descripción de Grafo Acíclico Dirigido 246
6.4.4 Ordenamiento Topológico 246
6.4.5 Ruta Crítica 248
6.4.6 Preguntas Seleccionadas de esta Sección 251
6.4.7 Respuestas y Análisis 260
Resumen 275
Pensando 276
Capítulo 7 Búsqueda 277
7.1 Conceptos básicos de búsqueda 277
7.2 Búsqueda Secuencial y Binaria 278
7.2.1 Búsqueda Secuencial 278
7.2.2 Búsqueda Binaria 280
7.2.3 Búsqueda de Bloques 281
7.2.4 Preguntas Seleccionadas de esta Sección 282
7.2.5 Respuestas y Análisis 285
7.3 Búsqueda en árbol 291
7.3.1 Árbol Binario Ordenado (BST) 291
7.3.2 Árboles Binarios Balanceados 295
7.3.3 Árboles Rojo-Negro 299
7.3.4 Preguntas Seleccionadas de esta Sección 305
7.3.5 Respuestas y Análisis 309
7.4 Árboles B y Árboles B+ 319
7.4.1 Árbol B y sus operaciones básicas 319
7.4.2 Conceptos Básicos de Árboles B+ 322
7.4.3 Preguntas Seleccionadas de esta Sección 323
7.4.4 Respuestas y explicaciones 325
7.5 Tabla Hash 331
7.5.1 Conceptos Básicos de Tablas Hash 331
7.5.2 Método de construcción de función hash 331
7.5.3 Métodos para lidiar con conflictos 332
7.5.4 Búsqueda hash y análisis de rendimiento 334
7.5.5 Preguntas Seleccionadas de esta Sección 335
7.5.6 Respuestas y Análisis 338
Resumen 343
Pensando Expansión 344
Capítulo 8 Ordenamiento 345
8.1 Conceptos básicos de ordenamiento 346
8.1.1 Definición de Ordenamiento 346
8.1.2 Preguntas Seleccionadas de esta Sección 346
8.1.3 Respuestas y Análisis 347
8.2 Ordenamiento por Inserción 347
8.2.1 Ordenamiento por Inserción Directa 347
8.2.2 Ordenamiento por Inserción Binaria 349
8.2.3 Ordenamiento Shell 349
8.2.4 Preguntas Seleccionadas de esta Sección 351
8.2.5 Respuestas y Análisis 352
8.3 Ordenamiento por Intercambio 355
8.3.1 Ordenamiento de Burbuja 355
8.3.2 Ordenamiento Rápido 356
8.3.3 Preguntas Seleccionadas de esta Sección 359
8.3.4 Respuestas y Análisis 361
8.4 Ordenamiento por Selección 366
8.4.1 Ordenamiento por Selección Simple 366
8.4.2 Ordenamiento por Montículos 366
8.4.3 Preguntas Seleccionadas de esta Sección 369
8.4.4 Respuestas y explicaciones 371
8.5 Ordenamiento por Mezcla, Ordenamiento Radix y Ordenamiento por Conteo 417
8.5.1 Ordenamiento por Mezcla 377
8.5.2 Ordenamiento Radix 379
*8.5.3 Ordenamiento por Conteo 380
8.5.4 Preguntas Seleccionadas de esta Sección 382
8.5.5 Respuestas y Análisis 384
8.6 Comparación y Aplicación de Varios Métodos de Ordenamiento Interno 387
8.6.1 Comparación de Métodos de Ordenamiento Interno 387
8.6.2 Aplicación de métodos de ordenamiento interno 388
8.6.3 Preguntas Seleccionadas de esta Sección 389
8.6.4 Respuestas y Análisis 391
8.7 Ordenamiento Externo 394
8.7.1 Conceptos Básicos de Ordenamiento Externo 408
8.7.2 Método de ordenamiento externo 394
8.7.3 Fusión Equilibrada Multi-vía y Árbol de Perdedores 395
8.7.4 Ordenamiento por Permutación-Selección (Generación de Segmentos de Fusión Iniciales) 406
8.7.5 Árbol Merge 397
8.7.6 Preguntas Seleccionadas de esta Sección 399
8.7.7 Respuestas y Análisis 400
Resumen 404
Pensando 405
Referencias 406
......