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)
¿Cómo funciona el algoritmo de ordenación Mergesort?
Algoritmo de mezcla. Separar en 2 partes un vector, ordenar por separado cada una de las partes y luego mezclarlas manteniendo la ordenación. O(n log n)
¿Cómo funciona el algoritmo de selección?
Se busca el elemento más pequeño y se pone en la primera posición, se repite el proceso con el resto. O(n2)
¿Cómo funciona el algoritmo de burbuja (bubblesort)?
Comparar pares de elementos adyacentes e intercambiarlos entre si hasta ordenar todos. O(n2)
¿Cómo funciona el algoritmo Shellsort?
Comparar el elemento con el de un número de posiciones, según va actuando va acortando el salto. O(n log n)
¿Cómo funciona el algoritmo Quicksort (rápido)?
Se utiliza un pivote, los elementos menores se pasan a un lado y los mayor al otro. Se repite el proceso en cada uno de los lados n veces. Divide y vencerás. O(n log n)
¿Cómo funciona el algoritmo Radix sort?
Se ordena el array descomponiendo los números en dígitos, de más a menos significativos. Limitado sólo a enteros. O(k n)
¿Cuáles son las primitivas del tipo abstracto de datos Pila?
- push
- pop
- top
- isEmpty
¿Qué diferencia existen entre una estructura de datos y un tipo abstracto de datos?
El TAD es un modelo matemático (especificación), mientras que la estructura de datos es una implementación
¿Qué problema o deficiencia nos encontramos en una tabla Hash a la hora de ir registrando nuestros pares (clave, valor) ?
Que pueden dar colisiones, es decir, que para dos claves diferentes (debido a la funcion hash) estas se situen en la misma posicion dentro de la tabla.
¿En que consiste un montículo max-heap?
En una estructura de datos de tipo árbol en la cual el valor de un nodo es mayor que todos los que tiene por debajo (max-heap)
¿Cómo se llama a un grafo que tiene valores numéricos en las aristas?
ponderado
¿Qué es un grafo conexo? ¿y completo?
Conexo -→ Que todos sus vértices están conectados por un camino
Completo -→ Si cada par de vértices están conectados por una arista
¿Qué es el orden de un grafo?
El numero de vertices que tiene
¿Qué es un multigrafo?
Aquel que tiene mas de una arista entre dos mismos vértices
Nombre dos algoritmos para calcular el camino mínimo entre dos nodos en un grafo
Dijkstra
Bellman-Ford
Nombre dos algoritmos para calcular un árbol de recubrimiento mínimo en un grafo
Prim
Kruskal
¿Qué es FLAC?
Un formato/codec libre de audio sin perdidas (Free Lossless Audio Codec)
¿Qué es ID3 en el formato MP3?
Una etiqueta con metadatos que nos permite saber de ese audio el autor, álbum, etc (para catalogarlos)
