Tema 3 Estructura de Datos y Algoritmos Flashcards
Definición de TAD
Tipo abstracto de datos.
- Una estructura de datos y los métodos para operar sobre ella.
- Ejemplo: Una pila y los métodos apilar, desapilar, ordenar.
Definición de estructura de datos
Métodos que permiten un almacenamiento eficiente de la información. Una estructura de datos es un conjunto de variables de un determinado tipo agrupados y organizados para representar un comportamiento.
Tipos de estructuras de datos internas
Estáticas (tamaño de memoria fijo definido en tiempo de compilación)
- Arrays/Matrices.
- Registros, uniones.
Dinámicas (tamaño de memoria definido en tiempo de ejecución)
- Listas.
- Pilas (solo se puede extraer el último elemento insertado) LIFO.
- Colas. FIFO
- Árboles.
- Grafos.
Dentro de la estructura de árbol, ¿qué es la raíz?
Elemento que no tiene antecesor
Dentro de la estructura de árbol, ¿qué es una rama?
Arista entre dos nodos
Dentro de la estructura de árbol, ¿qué es el grado?
Se denomina grado de un nodo al número de hijos de dicho nodo.
El grado de un árbol es el mayor grado de los nodos que contiene.
Dentro de la estructura de árbol, ¿qué es la altura y la profundidad?
Si el árbol es vacío su altura es 0; y. si el árbol no es vacío su altura es 1 más que el máximo de las alturas de sus hijos.
Profundidad de un nodo es la longitud del camino único que va desde la raíz hasta ese nodo.
Tipos de árboles
- Árbol binario: un máximo de dos hijos por nodo.
- Árbol AVL: árbol binario ordenado. Los árboles AVL están siempre equilibrados de tal modo que, para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa.
- Árbol binario de búsqueda: es un árbol binario que cumple que el subárbol izquierdo de cualquier nodo (si no está vacío) contiene valores menores que el que contiene dicho nodo, y el subárbol derecho (si no está vacío) contiene valores mayores.
- Árbol B+: árbol binario con los nodos hoja enlazados en una lista. Son árboles balanceados pero que pueden tener más de dos hijos por nodo. Muy útil para búsquedas.
Recorridos de árboles
Preorden: Nodo – Izquierda – Derecha.
Inorden: Izquierda – Nodo – Derecha.
Postorden: Izquierda – Derecha – Nodo.
Amplitud: recorrer los nodos por niveles.
¿Qué es un algoritmo?
Secuencia lógica de pasos a seguir para obtener una solución.
Tipos de algoritmos de búsqueda
- Secuencial.
- Binaria o dicotómica.
- Transformación de claves o Hash.
¿Cómo funciona el algoritmo de búsqueda secuencial?
Examinar uno a uno los elementos del array hasta dar con el buscado. Si el array se encuentra ordenado se puede optimizar. O(n)
¿Cómo funciona el algoritmo de búsqueda binaria o dicotómica?
Sólo se puede aplicar a arrays ordenados. Buscamos el elemento central, si el elemento buscado es mayor miramos a la derecha y si es menor a la izquierda. Repetir la operación con el subarray hasta localizar el elemento. O(log n)
¿Cómo funciona el algoritmo de búsqueda por transformación de claves (hashing)
Asignas a cada elemento un índice, sacado de una función de conversión (función hash). Cuando se quiera buscar algo usamos esos índices para saber dónde buscar. Hash = clave - valor
¿Cómo funciona el algoritmo de ordenación Heapsort?
Algoritmo de montículo. Se utiliza un montículo que contiene el menor/mayor elemento, en una segunda iteración se ordenan los elementos usando dicho montículo. O(n log n)
