B2 Tema 3 Estructura de datos Flashcards
¿Cuantas columnas tiene la tabla HASH?
Dos. Que son LLAVE Y VALOR.
¿Qué es una tabla Hash?
- También llamada, Mapa Hash.
- Es una ESTRUCTURA DE DATOS que implementa el TAD llamado Diccionario y que soporta de manera eficiente la operación de búsqueda.
- Se usan cuando hay que almacenar gran cantidad de información y también necesitamos acceder a ella y buscar un dato.
- El tiempo promedio de búsqueda es de O(1).
- Su estructura es clave=valor.
¿Como se introducen datos en la tabla hash?
- Se aplica una FUNCIÓN DE DISPERSIÓN o HASH, al valor que queremos introducir
- El resultado es un índice/ubicación válido para la tabla.
- El elemento se almacena en la posición de la tabla obtenido en el paso anterior.
¿Qué es una COLISIÓN en Hash?
Cuando a dos objetos se les asigna la misma posición en la tabla, como resultado de aplicar la función resumen (hash)
Qué dos técnicas hay para resolución de COLISIONES?
→ ENCADENAMIENTO SEPARADO o HASHING ABIERTO o DIRECCIONAMIENTO CERRADO, Agrega listas de objetos en las ubicaciones donde hay colisiones. Lo llamamos DIRECCIONAMIENTO CERRADO, por que vamos a la ubicación que le toca y no nos movemos de ahí.
→ DIRECCIONAMIENTO ABIERTO o HASHING CERRADO. En este caso sí que nos movemos de ubicación, hasta encontrar una libre. Esto se hace por medio de sondeos, que pueden ser, LINEALES, CUADRÁTICOS y de DOBLE HASHEO.
¿En qué consiste el Direccionamiento cerrado o hasing abierto (Encadenamiento separado)?
Decimos DIRECCIONAMIENTO CERRADO, por que no nos movemos de la ubicación que le ha tocado. Hay que meter el dato ahí por cojones.
Cuando varios elementos, comparten la misma ubicación, se genera una lista en esa ubicación y los elementos se van colocando en esa lista.
Di algunos Tipos Abstractos de Datos y sus implementaciones..
- Listas→Array, Lista enlazada
- Pilas o Stack→ Array, Lista enlazada
- Colas o Queue/Double-ended queue→ Array, Lista [doble] enlazada
- Grafos→Matriz, Array de listas enlazadas
- Árboles
- Diccionario→ Tablas HASH
- Set/Multiset, Árbol rojo-negro, Tabla Hash
- Priority Queue→ Montículo
- Associative Array→ Tabla Hash
¿Qué algoritmo usamos para las Stacks o pilas?
LIFO
Es como en las pilas de platos de la cocina. El último en entrar, es el primero en salir.
Solo un extremo de la pila es el que se modifica siempre y se llama “Tope”
¿Qué primitivas podemos usar para trabajar con las Pilas o Stacks?
- Pop, para eliminar un elemento del Tope de la pila.
- Peek, lee el último elemento insertado, sin borrarlo, es como un SELECT.
- Push, para añadir un elemento al Tope de la pila.
- IsEmpty, antes de aplicar POP, se usa Isempty, para comprobar que no esté vacía la pila.
¿Qué algoritmo usamos para las Colas o Queue?
FIFO
El primer elemento en entrar, es el primero en salir.
¿Qué primitivas podemos usar en las Colas o Queue?
- Enqueue, inserta por un extremo. El extremo donde se añade un elemento, se llama, BACK, TAIL o REAR.
- Dequeue, extrae por el extremo opuesto. El extremo por el que se saca un elemento de la cola, se llama, HEAD o FRONT.
- Isempty, comprueba si la cola está vacia.
- IsFull, comprueba si está llena.
- Peek, obtiene el valor de la cabeza de la cola, sin borrarlo.
¿Qué son los Monticulos?
- Son estructuras de datos, de tipo árbol, que cumple con la propiedad del montículo, como MAX-HEAP o MIN-HEAP.
- Son conjuntos de datos ORDENADOS.
- Se usan para COLAS DE PRIORIDAD
- Tiene una buena complejidad, rondando el O (Log (n))
¿Cual es la característica de un montículo máximo?
Que la raíz es la que tiene el mayor valor, por encima de sus hijos.
¿Cual es la característica de los Montículos Mínimos?
El valor de la raíz es siempre el de menor valor del árbol y de sus hijos.
¿Con qué otro nombre se conoce a los Montículos?
Heap.
¿Para qué son muy útiles los Montículos de máximos ó mínimos?
Para Colas de Prioridad
En un Árbol ¿Cual es el grado de un nodo?
Es el número de hijos DIRECTOS que tiene.
En un Árbol ¿Qué es la profundidad de un nodo?
Es el número de arístas que hay desde el nodo a la raíz.
¿Qué profundidad tiene el nodo Raíz?
Profundidad 0.
En un Árbol, ¿Cual es la altura de un nodo?
Se mide del nodo hacia abajo.
Es la trayectoria más larga desde ese nodo hasta la primera hoja.
La altura de un nodo hoja es igual a 0.
Se cuentan las arístas.
En un Árbol ¿Qué es el factor de equilibrio?
Es la diferencia de altura entre el subárbol izquierdo y el derecho.
¿Cual es la altura de un Árbol completo?
Es la altura de su nodo raíz.
En un Árbol, ¿Qué es una hoja?
Un nodo sin hijos.
Recorrido en profundidad de un Árbol.
PREORDEN (RID)
1º La Raíz
2º Subárbol izquierdo
3º Raíz del subárbol izquierdo
4º Si ya no hay subarbol a la izquierda, vamos al derecho.
5º Raíz del derecho
etc…
Recorrido en profundidad de un árbol:
INORDEN (IRD)
Es más o menos como leer, la primera hoja de la izquierda y luego raíz, hoja, raíz, hoja, raíz, y así.
1º Subárbol Izquierdo
2º Raíz
3º Subárbol Derecho
Recorrido en profundidad de un árbol:
POSTORDEN (IDR)
1º Subárbol Izquierdo
2º Subárbol Derecho
3º Raíz
¿Que nivel tiene un árbol vacío?
0
¿Qué es el órden de un árbol?
Es el límite máximo de hijos que puede tener un nodo.
¿Qué es un Árbol Binario Perfecto?
Aquel en el que todas las hojas están al mismo nivel.
¿Como es la búsqueda en Amplitud?
Se busca de forma lineal, de izquierda a derecha, pasando de un nivel, al siguiente y leyendo de izquierda a derecha. No es una función recursiva.
¿Qué son los GRAFOS dirigidos o DIGRAFOS?
Son aquellos cuyas aristas tienen un sentido definido.
A diferencia de los No Dirigidos.
¿Qué es un GRAFO CONEXO?
Aquel en el que todos los Vertices están conectados por caminos.
¿Qué es un árbol de recubrimiento mínimo?
En un grafo, CONEXO y NO DIRIGIDO, ES AQUEL SUBÁRBOL QUE CONECTA TODOS LOS NODOS Y QUE PESA LO MISMO O MENOS QUE LOS OTROS SUBÁRBOLES.
