Tema 3 - Estructuras de datos y algoritmos Flashcards
Que es un TAD
Tipo abstracto de datos, es un modelo matemático para definir tipos de datos (primitivas)
List es un TAD que se implementa con…
Arrays y Listas enlazadas
Set y Multiset son TAD que se implementan con…
Arbol rojo-negro y tabla hash
Queue y Double ended queue son TAD que se implementan con…
Arrays y listas enlazadas
Stack es un TAD que se implementan con
Arrays y listas enlazadas
Priority Queue (Heap) es un tad que se implementa con para…
Monticulo
Graph es un tad que se implementa con…
Matrices y arrays de listas enlazadas
Associative array es un tad que se implementan con…
Tablas hash
Cual es el modelo de una pila(stack)
LIFO (Last In First Out)
Cual es el modelo de una cola (queue)
FIFO (First In First Out)
Push, pop, isEmpty y top son funciones utilizadas en…
Stack(Pila)
enqueue, dequeue, isEmpty y top son funciones utilizadas en…
Queue (Cola)
isEmpty, insertarDelante, insertarDetras, head y tail son funciones utilizadas en…
Listas
Con tail cogemos el elemento nº
N-1
Que es una tabla hash
Estructura de datos con dos entradas (clave y valor) vamos guardando los distintos objetos. Si quiero saber donde van a ir colocados necesito una funcion hash.
A que se le llama colision en las tablas hash
Cuando dos objetos coinciden en la misma posición de la tabla.
Ejemplo: queremos poner DNI’s en la tabla y coincide que ambos estan en el mismo lugar de la tabla
Se utilizaba para hacer caches, indices…
Que es un montículo
Estructura de informacion en forma de arbol que cumple la propiedad del monticulo.
La raiz es la mayor de todos los que hay por debajo de ella y asi sucesivamente.
Sirve para implementar una cola con prioridad (el de máxima prioridad sería la raiz del arbol).
Si son implementados con un arbol binario se le denomina monticulo binario.
Si se implementa con un array los hijos del nodo N seran 2n y 2n + 1
A que se le denomina el grado de un nodo de un árbol
El nº de hijos directos que tiene (o numero de subarboles)