ESTRUCTURA DE DATOS Flashcards
¿En qué consiste un max-heap?
Un árbol binario (montículo) cuya raiz es el elemento mayor de todos los del árbol
NOTA: Esta propiedad se cumple en cualquier nivel
¿A que TAD pertenecen las primitivas push y pop?
TAD Pila (LIFO)
¿En qué consiste una “colisión” en una tabla Hash?
Una colisión se da cuando aplicando el algoritmo de hash a la distintas “keys” dan el mismo resultado (índice de la tabla)
Definición de grado de un nodo y orden del árbol
a) grado(nodo) –> nº de hijos que tiene un nodo en un momento determinado (limitado por el orden del árbol)
b) orden(árbol) –> nº MÁXIMO de hijos que PUEDE tener cualquier nodo
Definición de altura y profundidad de un nodo
a) altura(nodo) –> nº de aristas desde ese nodo hasta el nodo hoja mas alejado
b) profundidad(nodo) –> nº de aristas desde ese nodo hasta la raíz
¿En qué consiste un árbol AVL?
Es una implementación de árbol que mantiene automáticamente un factor de equilibrio entre 0,+1 o -1 (autobalanceable)
¿Para qué sirve el algoritmo de Kruskal?
Algoritmo que sirve para generar un ÁRBOL DE RECUBRIMIENTO MÍNIMO (árbol que conecta a todos los nodos con coste GLOBAL/SUMA MÍNIMO)
¿En qué consiste el grado de un vértice en un grafo?
Nº de aristas incidentes
¿Para qué sirve el algoritmo de Dijkstra?
Algoritmo que sirve para calcular el CAMINO MÍNIMO de UN NODO al resto (caso particular seria entre DOS NODOS)
¿Cuáles son dos características de los árboles B+?
a) Nodos hoja están entrelazados
b) Nodos internos solo contienen claves y punteros
