B2-T3 (Primera parte) TAD Flashcards
¿Que es un TAD?
Tipo Abstracto de Datos.Es una descripción teórica de una colección de datos y las operaciones que pueden realizarse sobre ellos.
¿Que es una Estructura de datos?
Es una forma concreta de organizar y almacenar datos en la memoria de una computadora para que puedan ser usados de manera eficiente
¿Que es un Array (Arreglo)?
Contenedor de elementos de un mismo tipo almacenados en posiciones contiguas de memoria
¿Que es un Lista enlazada?
Estructura de datos compuesta de nodos donde cada nodo contiene un dato y una referencia (enlace) al siguiente nodo
¿Que es un Montículo (Heap)?
Estructura de árbol que satisface la propiedad de montículo (heap property). Donde el padre siempre es mayor o menor que sus hijos
¿Que es una Tabla hash?
Para mapear claves a posiciones en una tabla, permitiendo búsquedas, inserciones y eliminaciones eficientes.
¿Que es un Árbol binario de búsqueda (BST)?
Árbol donde cada nodo tiene como máximo dos hijos y cumple con la propiedad de que el hijo izquierdo es menor y el derecho es mayor que el nodo.
¿Que es un Grafo?
Representación de un conjunto de nodos (vértices) y las conexiones entre ellos (aristas).
¿Que es una Pila (stack) ?
Colección de elementos con una política de acceso LIFO (Last In - First Out)
¿Que es una Cola ?
colección de elementos con una política de acceso FIFO (First In - First Out)
¿Que es Arrays Asociativos - Diccionario - Mapa?
Es una colección de pares clave-valor donde cada clave es única y está asociada a un valor.
Definición de tabla Hash
Es una estructura de datos que implementa un TAD, como un diccionario o un mapa, que puede almacenar pares de clave-valor y permite operaciones eficientes de búsqueda
¿Como se llaman los elementos en los que un hash guarda la información?
slots o buckets
¿Que es resolución de conflictos por encadenamiento en tablas hash?
Es una técnica utilizada para manejar colisiones que ocurren cuando dos o más elementos se asignan a la misma posición en una tabla hash.
En el encadenamiento- cada posición o índice de la tabla hash no almacena directamente un solo elemento, sino que apunta a una lista vinculada (o alguna otra estructura de datos como una lista dinámica) que contiene todos los elementos que han sido hash a esa misma posición.
¿Que Técnicas existen para gestionar las colisiones?
Hashing Abierto y Hashing Cerrado
¿En que consiste la técnica de Hashing Abierto?
Cuando ocurre una colisión, el nuevo elemento se añade a la lista en la posición donde ha dado el conflicto
¿En que consiste la técnica de Hashing Cerrado?
cuando ocurre una colisión ,el nuevo elemento se coloca en otra posición de la tabla hash según una secuencia predefinida hasta encontrar una posición vacía.
¿Como es el coste de una busqueda en tablas Hash?
constante
¿Cual es la complejidad en los monticulos para hacer insercción y borrados?
O(log(n))
¿Que es una cola de prioridad?
cada elemento en la cola tiene una prioridad asociada, y los elementos se extraen de la cola en orden de prioridad en lugar de en el orden en que se insertaron.
Características de un árbol
-grafo acíclico
- conexo
-no dirigido
¿Que es un en un árbol?
nodo que no tiene descendientes
¿Que es Grado de un nodo en un árbol?
nº de descendientes directos de ese nodo
¿Que es Nivel en un árbol?
número de ramas que hay que recorrer para llegar de la raíz a un nodo.
¿Que es Altura de un nodo en un árbol?
Trayectoria más larga desde ese nodo a una hoja.
¿Que es Anchura de un nodo en un árbol?
Es el mayor valor del número de nodos que hay en un nivel.
¿Que es Factor de equilibrio (FE) de un nodo en un árbol?
Diferencia de altura entre subárbol izquierdo y derecho. Para un árbol AVL ,este valor debe ser -1 -0 o 1.
¿Que es Orden Orden en un árbol?
Número máximo teórico de hijos que puede tener un nodo.
¿Que es un árbol balanceado?
es una estructura de datos de árbol en la que la diferencia de altura entre los subárboles izquierdo y derecho de cualquier nodo no excede en más de una unidad
¿Que es unÁrbol de recubrimiento mínimo?
es un subgrafo que conecta todos los nodos siguiendo un camino cuyo coste de la suma del valor de las aristas es mínimo
¿Que es un Árbol Binario de búsqueda (ABB)?
- los valores en el subárbol izquierdo de un nodo son menores que el valor del nodo.
- Los valores en el subárbol derecho son mayores que el valor del nodo.
¿Cual es el rendimiento en un rbol Binario de búsqueda (ABB)?
log(n)
¿Que tipos de Árboles Equilibrados (auto-balanceable) conoces?
- AA
- rojo-negro
- splay
- árbol B
¿Que es un árbol AVL?
árbol binario de búsqueda (ABB) autobalanceado
¿Que es un Árbol B?
es una estructura de datos de árbol autoequilibrado en la que los nodos pueden tener más de dos hijos.
¿Que complejidad tienen las insercciones y borrados en los árboles B?
log(n)
¿Cuantas claves como mínimo tiene un arbol B?
m/2
¿Que es un Árbol B+?
- variante del árbol B
- nodos intermedios solo contienen claves y punteros
- nodos hojas están enlazados entre sí mediante una lista enlazada
¿Que es un Árbol B*?
variación del árbol B
- mayor densidad de ocupación=Garantizan la densidad de ocupación (⅔ * t). t= grado mínimo del árbol.
¿Que es un grafo dirigido o digrafo?
aquel en el que todas sus aristas tienen sentido o dirección
¿Que es un grafo conexo?
Si es posible llegar desde cualquier nodo del grafo a cualquier otro nodo a través de una secuencia de aristas (conexiones) sin importar cuán larga sea esa secuencia.
¿Que es un grafo Multigrafo?
Mas de una arista entre vertices
¿Que es un grafo Completo?
es un grafo simple donde cada par de vértices está conectado por una arista.
¿Que es un Un árbol recubridor mínimo?
subconjunto de las aristas que conecta todos los vértices sin ciclos y con el costo total más bajo posible.
¿Que es el camino mínimo entre dos vértices en un grafo ponderado?
Se refiere a la ruta menor coste entre dos vértices específicos
Listado de algoritmos sobre un árbol recubridor mínimo
PRIM - KRUSKAL
Listado de algoritmos sobre un árbol camino mas corto
-DIJKSTRA
- BELLMAN-FORD
- JOHNSON
- FLOYD-WARSHALL
- Algoritmo A*
¿Para que vale el algoritmo FORD-FULKERSON?
encontrar el flujo máximo en una red de flujo
¿Para que vale el algoritmo VITERBI?
hallar la secuencia más probable de estados ocultos
