Bloque2-Tema3-Estructuras de datos Flashcards
Que es un tipo abstracto mde datos?
Modelo matematico para definir tipo de datos (Primitivas)
Un tad va con sus primitivas. Las primitivas definen al tipo abstracto de datos
Que es una estructura de datos?
Concepto mas concreto orientado a la implementacion.
Implementacion tipicas de una Lista?
Array, Lista enlazada.
Implementacion tipicas de un set/Multiset?
Arbol rojo negro, tabla hash.
Implementacion tipicas de una cola o una bicola.
Array, lista [doble] enlazada.
Implementaciones tipicas de una pila?
Array, lista enlazada.
Implementaciones tipicas de una priority queue
Monticulo.
Implementacion tipicas de un grafo?
Matriz, array de listas enlazadas.
Implementaciones tipicas de un array asociativo (Diccionario, Mapa)?
Tabla hash.
Que es una bicola?
Los elementos se pueden insertar o eliminar por el principio o por el final.
Cual es una estructura LIFO?
Pila
Cual es una estructura FIFO?
Cola
Primitivas de una pila?
Push, pop, isEmpty, Top,
Primitivas de una cola?
Enqueu, dequeue, isEmpty, peek.
Primitivas de una lista?
IsEmpty, InsertarDelante, InsertarDetras, head, tail.
Que es una tabla hash?
Una tabla hash, matriz asociativa, hashing, mapa hash, tabla de dispersión o tabla fragmentada es una estructura de datos que implementa el tipo de dato abstracto llamado Diccionario.
Asocia llaves o claves con valores.
Que puede suceder si una funcion hash de una tabla hash esta mal diseñada?
Que se produzcan colisiones.
Direccionamiento cerrado o hashing abierto
Cada casilla en el array referencia a una lista con los registros insertados que colisionan en dicha casilla.
Direccionamiento abierto o hashing cerrado
Las tablas hash de direccionamiento abierto pueden almacenar los registros directamente en el array. Las colisiones se resuelven mediante un sondeo del array, en el que se buscan diferentes localidades del array (secuencia de sondeo) hasta que el registro es encontrado o se llega a una casilla vacía, indicando que no existe esa llave en la tabla.
Que es un monticulo?
Estructura basa en arbol que cumple con la propiedad del monticulo.
Hay Max_Heap y MIn_Heap. En Max Heap el valor superior es mayor o igual que todos los que tiene por dbeajo.
Tiene una complejidad de O(log(n))
Si se implementa con un arbol binario-> Monticulo binario.
Que contiene una tabla hash?
La propia tabla(Con indices y valores) + zona de colisiones.
Hablando de arboles, que es el grado de un nodo?
Numero de hijos directos.
Hablando de arboles, que es la profundidad de nodo?
Nº de aristas desde la raiz al nodo.
Nodo raiz = 0
Que es la altura de un nodo?
Trayectoria mas larga desde ese nodo a una hoja.
Que es el factor de equilibrio(FE)?
Diferencia altura entre subarbol izquierdo y derecho.
Que tipos de recorridos en profundidad conoces?
Preorden(Raiz, Izquierda, Derecha)
Inorden(Izquierda, Raiz, Derecha)
PostOrden(Izquierda, Derecha, Raiz)
Tipos de arboles?
-Arboles binarios
-Arboles equilibrados(Autobalanceados)
-Arboles B
-Arboles B+
-Arboles B*
Tipos de arboles binarios?
-Arbol binario de busqueda (Si lo recorres en inorden dan los elementos ordenados)
-Arbol de Fibonacci (Caso particular de AVL)-> Se llama árbol de Fibonacci a una variante de árbol binario con la propiedad que el orden de un nodo se calcula como la sucesión de Fibonacci.
Que es un arboles equilibrados(Autobalanceados)?
Un arbol dond el factor de equilibrio es -1, 0 o 1.
Que tipos de arboles equilibrados(Autobalanceados) conoces?
-AVL
-AA
-Rojo Negro
-Splay
-Arbol B
Que es un arbol B?
Un arbol donde cada nodo puede tener mas de dos hijos(Orden) M.
-Mantiene los datos ordenadores
-Inserciones y borrados en tiempo log(n)
-Cada nodo tiene como maximo M hijos.
-Cada nodo(excepto la raiz) tiene como minimo M/2 claves.
Caracteristicas de los arboles B+?
- Nodos internos solo contienen claves y punteros.
-Los nodos hojas estan enlazados entre si.
Que es un arbol B*?
Uno que garantiza al menos una densidad de ocupacion de 2/3.
Donde empieza el nivel de un arbol, en 0 o en 1?
-No hay consenso si empieza en 0 o 1. Asi que ojo en el examen. Mirate la imagen par entender el nivel.
Altura del arbol: profundidad maxima de un nodo + 1
Que es el peso de un arbol?
Numero total de nodos de un arbol.
Que es el orden de un arbol?
Es el numero maximo de hijos que puede tener un nodo. Por lo que el orden limita al grado.
Cuando esta unn arbol binario lleno?
Cuando todos los nodos tienen 0 o 2 hijos.
Que hace la primitiva crear(constructor)
Crea la pila vacia.
Tipos de grafos?
-Dirigidos o digrafo-> Las aristan tienen un sentido definido.
-No digiridos.
-Grafo conexo
-Multigrafo-Mas de una arista entre dos vertices.
-Grafo etiquetado/ponderado-> Peso numero en aristas.
Que es un grafo conexo?
un grafo conexo o conectado es un grafo en que todos sus vértices están conectados por un camino o por un semicamino
Que es un grafo dirigido?
Las aristan tienen un sentido definido.
Que es un multigrafo?
Cuando hay mas de una arista entre dos vertices.
Que es un grafo ponderado.
Es un grafo en el que las aristas tienen un valor o peso asociado.
Que es el orden del grafo?
Numero de vertices.
