Tema 3. Estructura de datos y algoritmos Flashcards
(32 cards)
¿En qué consiste un Max Heap
CADA NODO siempre es más grande que los que tiene debajo
¿A qué TAD pertenecen las primitivas Push y Pop?
A una pila (stack)
¿En qué consiste una colisión en una tabla Hash?
Una colisión se da cuando aplicando el algoritmo hash a las distintas keys, dan el ismo resultado en el índice de la tabla
Definición de grado de un nodo y orden del arbol
Grado de un NODO: Número de hijos EN ESE MOMENTO
Orden del ÁRBOL: Número de hijos MÁXIMO que puede tener
Definición de altura y profundidad de un nodo
Altura: El número de aristas desde ese nodo hasta el nodo hoja más alejado (trayectoria más larga)No
Profundidad: El número de aristas desde ese nodo a la raíz
¿En qué consiste un árbol AVL?
Es una implementación de árbol binario de búsqueda que mantiene automáticamente un factor de equilibrio entre -1, 0 o +1 (autobalanceable)
¿Para qué sirve el algoritmo de Kruskal?
Árbol de recubrimiento que conecta todos los nodos con coste dlobal/suma mínimo
¿En qué consiste el grado de un vértice en un grafo?
Número de aristas incidentes
¿Para qué sirve el algoritmo de Dijkstra?
Para calcular el camino mínimo desde un nodo a todos los otros nodos
¿Cuáles son las características de los árboles B+?
Nodos internos solo contienen claves y punteros, hojas están enlazadas entre sí.
¿Cuáles son las características de los árboles B*?
Garantiza una densidad de ocupación de 2/3 (árbol B sólo 1/2).
¿Para qué sirve el algoritmo FLOYD-WARSHALL.?
En un grafo ponderado, encuentra caminos más cortos entre todos los nodos.
¿Qué es un algoritmo?
Conjunto de reglas que, aplicadas sistemáticamente a un conjunto de datos apropiados de entrada, resuelven un problema en un NÚMERO FINITO de pasos elementales. UN ALGORITME DEBE TERMINAR Y TENER UNA ENTRADA Y SALIDA
Algoritmo de Burbuja
O(n2). Va desplazando al final del array el nº más grande a base de comparaciones e intercambios entre elementos adyacentes. Mejor caso O(n) si la lista ya está ordenada.
Algoritmo de Inserción directa
O(n2). Busca donde insertar el dato y desplaza los siguientes elementos. Si hace una búsqueda binaria: Inserción binaria.
Algoritmo de Mergesort
O(n log (n)). Es recursivo. Divide la lista en sublistas hasta llegar al caso más sencillo para comparar. Luego mezcla las sublistas para obtener una lista ordenada.
Algoritmo de Quicksort
O(n log (n)). Es recursivo. Elegimos un pivote. En la primera pasada, los menores del pivote se colocan a la izquierda y los mayores a la derecha. Segunda pasada: hacemos 2 llamadas de T(n/2). Peor caso O(n2) si el pivote es el menor o el mayor de los valores.
Algoritmo de Heapsort (o Montículos)
O(n log (n)). Se meten los datos en un montículo Max-Heap y luego se realizan N llamadas a EliminarMax().
Algoritmo de Radix Sort
O(n K). Se basa en el número de cifras de los números a ordenar. LSD usa el dígito menos significativo y MSD el más significativo.
Algoritmo de Selección
siempre O(n2). Primero busca el mínimo y lo coloca el primero. Luego busca el siguiente mínimo y lo coloca después
Algoritmo de Bucket Sort (o BinShort):
O(n). Distribuye los números en casilleros y dentro de cada casillero aplicas el criterio que sea
¿Qué es y en qué consiste la técnica de Backtracking?
Técnica de diseño de algoritmos basada en explorar todo el “árbol” de posibles soluciones (prueba y error): Alias: Fuerza bruta
Nota: Una posible optimización para no “repetir” cálculos sería Ramificación y Poda
¿Qué requisito tiene el algoritmo de la búsqueda binaria y qué complejidad computacional tiene?
Requisitos: Que los datos estén ordenados (array, árbol…)
Complejidad: O(log n)
Ordene de más eficiente a menos estas complejidades temporales: n! , nlogn , n^2 , 2^n
nlogn , n^2 , 2^n , n!
