ESTRUCTURA DE DATOS Flashcards
(62 cards)
¿Cuales 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 matematico (especificación), mientras que la estructura de datos es una implementación
¿Qué otros nombres recibe el tipo abstracto de datos “Array Asociativo” ?
Mapa o Correspondencia
Diccionario
¿Qué poblema 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 monticulo max-heap?
En una estructura de datos de tipo arbol en la cual el valor de un nodo es mayor que todos los que tiene por debajo (max-heap)
¿Qué es el grado de un nodo dentro de un arbol?
El numero de hijos directos que tiene ese nodo
¿Que es la profundidad de un nodo?
Numero de aristas desde la raiz a ese nodo
¿Que es la altura de un nodo?
La trayectoria más larga desde ese nodo a una hoja
¿Que tipo de recorrido en un arbol es el llamado Postorden?
Un recorrido en profundidad en el que cual primero se visita el subarbol Izquierdo, luego el subarbol Derecho y por ultimo la Raiz (IDR)
Nombre dos tipos de arboles binarios
ABB (Arbol binario de busqueda)
Arbol de Fibonacci
¿Qué es un arbol balanceado?
Aquel cuyo factor de equilibrio está en el rango [-1,0,1]
Nombre cuatro tipos de arboles auto-balanceados
AVL
Rojo-Negro
AA
Splay
En un arbol B+, ¿que contienen los nodos internos (no hojas)?
Solo las claves para poder navegar en las busquedas
¿Que se persigue en un arbol B* ?
Que haya un buen porcentaje de ocupacion en los nodos? Ej. 2/3
¿Qué peculiaridad tienen los nodos hoja (claves+datos) en un arbol B+?
Están enlazados entre si
Nombre las dos formas fundamentales de implementar un grafo
Matriz de adyacencia (nº de columnas/filas = nº de vertices)
Lista de adyacencia (Array de vertices + Listas enlazadas en cada posicion del array)
¿Como se llama a un grafo que tiene valores númericos en las aristas?
ponderado
¿Que 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
¿Que es el orden de un grafo?
El numero de vertices que tiene
¿Que es un multigrafo?
Aquel que tiene mas de una arista entre dos mismos vertices
Nombre dos algoritmos para calcular el camino minimo entre dos nodos en un grafo
Dijkstra
Bellman-Ford
Nombre dos algoritmos para calcular un arbol de recubrimiento minimo en un grafo
Prim
Kruskal
¿Para que sirve el algoritmo de Ford-Fulkerson?
Calcular camino en un grafo de tal forma que se maximiza el flujo
¿Para que sirve el algoritmo de Tarjan en un grafo?
Para identificar grupos de vertices que están fuertemente conectados
