T3 ESTRUCTURA DE DATOS (EEDD) Flashcards by Raquel P

ESTRUCTURA DE DATOS ¿Cuál es la diferencia entre TAD y estructura de datos?

TAD (tipo abstracto de datos): modelo matemático para definir tipos de datos primitivos
Estructura de datos: concepto más concreto orientado a la implementación

➡️➡️➡️➡️
Un dato primitivo es una unidad BASICA de información como un número, carácter o booleano

How well did you know this?

Not at all

Perfectly

ESTRUCTURA DE DATOS ¿Cuáles son los tipos de TAD y sus implementaciones típicas?
“Lalo Saltó Quince Sets Para Tener Grandes Amigos”

🧠TAD= tipo abstracto de datos

Secuenciales (ordenados)
- list: array, lista enlazada
- stack: array, lista enlazada
- queue / double-ended queue (bicola): array, lista doblemente enlazada

Conjuntos
- set / multiset: árbol rojo-negro, tabla hash

Con prioridad
- priority queue (heap): montículo

Jerárquicos
- tree: estructura jerárquica (según tipo)

Relacionales
- graph: matriz, array de listas enlazadas

Claves y valores
- associative array (diccionario, mapa): tabla hash

Regla nemotécnica:
“Lalo Saltó Quince Sets Para Tener Grandes Amigos”
- list
- stack
- queue
- set / multiset
- priority queue
- tree
- graph
- associative array

How well did you know this?

Not at all

Perfectly

ESTRUCTURA DE DATOS ¿COMO son las estructuras primitivas como stack, queue y list? Menciona su comportamiento y operaciones más comunes.

list: almacena elementos en orden, accesibles por posición
- Respeta el orden de inserción
- Operaciones: “isEmpty”, “insertarDelante”, “insertarDetrás”, “head”, “tail”
➡️
stack: estructura LIFO, se apilan los elementos (último en entrar, primero en salir)
- Respeta el orden pero solo se accede al último
- Operaciones: “push”, “pop”, “isEmpty”, “top”
➡️
queue: estructura FIFO, entra por un extremo y sale por el otro
- Respeta el orden de llegada
- Operaciones: “enqueue”, “dequeue”, “isEmpty”, “top”

How well did you know this?

Not at all

Perfectly

ESTRUCTURA DE DATOS ¿Qué hace los set o multiseten cuanto a los datos?

set: conjunto sin elementos repetidos
multiset: permite elementos repetidos
No importa el orden

How well did you know this?

Not at all

Perfectly

ESTRUCTURA DE DATOS ¿Qué es una queue o double-ended queue (bicola)?

queue: entra por un extremo y sale por el otro (FIFO)
bicola: se puede insertar o eliminar por ambos extremos

How well did you know this?

Not at all

Perfectly

ESTRUCTURA DE DATOS ¿Qué es una priority queue o heap?

Cola donde cada elemento tiene una prioridad
- Se atiende primero el de mayor prioridad
- Suele implementarse con un montículo

How well did you know this?

Not at all

Perfectly

ESTRUCTURA DE DATOS ¿Qué es un tree?

Estructura jerárquica con nodos conectados
- Un nodo raíz y varios hijos
- Se usa para representar relaciones

How well did you know this?

Not at all

Perfectly

ESTRUCTURA DE DATOS ¿Qué es un graph?

Conjunto de nodos conectados entre sí por aristas
- Puede ser dirigido o no (con o sin flechas)
- Representa relaciones complejas

How well did you know this?

Not at all

Perfectly

ESTRUCTURA DE DATOS ¿Qué es un associative array o diccionario?

Estructura que relaciona una clave con un valor
- Como una agenda: buscas por nombre y obtienes el teléfono

How well did you know this?

Not at all

Perfectly

ESTRUCTURA DE DATOS ¿Qué diferencia hay entre head y tail en una lista?

head: es el primer elemento de la lista
tail: es todo lo que queda de la lista después del head

How well did you know this?

Not at all

Perfectly

ESTRUCTURA DE DATOS ¿Por qué en una pila o stack no se recorre, sino que se procesa? ¿Con que llamadas se procesan?

Porque solo se accede al último elemento insertado (LIFO)
No se navega por todos los elementos como en una lista
Se procesa elemento a elemento usando “push” (apilar) y “pop” (desapilar)

How well did you know this?

Not at all

Perfectly

ESTRUCTURA DE DATOS ¿Qué es un montículo, un max heap y un min heap? ¿La elementos mantienen su orden?

Un montículo es una estructura de árbol casi completo usada para implementar colas con prioridad
El orden se mantiene en todos los niveles del árbol
En un max heap, cada nodo padre es mayor o igual que sus hijos
En un min heap, cada nodo padre es menor o igual que sus hijos

How well did you know this?

Not at all

Perfectly

ESTRUCTURA DE DATOS ¿Qué es una cola de prioridad?

Estructura donde cada elemento tiene una prioridad asociada
- Se atiende primero el de mayor prioridad, no el que llegó antes
- Suele implementarse con un montículo (heap)

How well did you know this?

Not at all

Perfectly

ARBOLES ¿Qué es un nodo? ¿Cuál es la diferencia entre raíz, rama y hoja?

Un nodo es un elemento que forma parte de un árbol y contiene un valor y enlaces a otros elementos
La raíz es el primer elemento del árbol, del que parten todos los demás
Una rama es un elemento que tiene descendientes
Una hoja es un elemento sin descendientes

How well did you know this?

Not at all

Perfectly

ARBOLES ¿Qué es el grado de un nodo y el grado/orden de un árbol?

El grado de un NODO es el número de hijos directos que tiene
(Si un nodo no tiene hijos, su grado es 0)
—
El grado de un árbol (también llamado orden) es el número MÁXIMO de hijos que puede tener alguno de sus nodos

‼️‼️ los grados pueden cambiar

How well did you know this?

Not at all

Perfectly

ARBOLES ¿Qué es el peso de un nodo⚪️ y de un árbol🌳?

Study These Flashcards

El peso de un nodo⚪️ es el número de descendientes que tiene (sin contar el propio nodo⚪️)
El peso de un árbol🌳 es el número total de nodos⚪️ que contiene

ARBOLES ¿Qué es la profundidad de un nodo?

Study These Flashcards

Es el número de aristas desde la RAIZ hasta la EL NODO POR EL QUE PREGUNTAMOS.
La raíz tiene profundidad 0
Cada nivel más abajo, suma 1 a la profundidad

🧠➡️ Es como si estuviéramos en un edificio y quiero buscar mi coche en el parking y preguntara ¿Como de profunda está tu plaza de aparcamiento? Siendo la raíz la planta 0 del edificio.

ARBOLES ¿Qué es la altura de un nodo?

Study These Flashcards

La altura va DESDE EL NODO QUE PREGUNTAMOS hasta la hoja más lejana

🧠➡️ Nos preguntaríamos a nosotros mismos: ¿Cómo de alto está el nodo?
Como si hablásemos de un edificio y quiero preguntar en qué piso vives.

ARBOLES ¿Qué es un árbol binario? ¿Y un árbol binario de búsqueda en relación a los valores de los subarboles?

Study These Flashcards

Un árbol binario es un árbol donde cada nodo puede tener como máximo 2 hijos (uno izquierdo y uno derecho)
‼️ También puede tener 0 y 1 hijos.
Un árbol binario de búsqueda es un árbol binario en el que:
- Los valores del subárbol izquierdo son menores que el nodo
- Los valores del subárbol derecho son mayores que el nodo
Esto permite buscar valores de forma eficiente

ARBOLES En los árboles AVL ¿Qué tiene que ver el factor de equilibrio con un árbol binario de búsqueda? ¿De cuanto tiene que ser la diferencia para que un árbol se considere equilibrado?

Study These Flashcards

El factor de equilibrio se aplica a los árboles binarios de búsqueda para mantenerlos balanceados
Es la diferencia entre la altura del subárbol izquierdo y la altura del subárbol derecho
Si esta diferencia es 0, 1 o -1, el árbol está equilibrado
Si la diferencia es mayor, puede ser necesario hacer rotaciones (como en árboles AVL)

ARBOLES ¿Cuáles son ejemplos de árboles autobalanceados?
Alicia Regaba Árboles Silvestres Bambús y Bananos

Study These Flashcards

Son árboles que se ajustan solos para mantenerse equilibrados y rápidos.

Ejemplos:
- AVL: realiza rotaciones tras insertar/eliminar para mantener el equilibrio
- Las rotaciones pueden afectar incluso a la raíz
- Rojo-Negro: permite cierto desequilibrio, pero sigue reglas estrictas de color
- AA: simplificación del árbol rojo-negro
- Splay: reorganiza el árbol tras acceder a un nodo, llevándolo hacia la raíz
- Árbol B
- Árbol B+: variante del Árbol B

Regla nemotécnica:

Alicia Regaba Árboles Silvestres Bambús y Bananos

ARBOLES ¿Qué son los recorridos preorden, inorden y postorden en un árbol binario?

Study These Flashcards

Son formas de visitar todos los nodos de un árbol binario, en distintos órdenes:

Preorden (RID):
- Primero se visita la Raíz, luego el Izquierdo y después el Derecho
Inorden (IRD):
- Primero el subárbol Izquierdo, luego la Raíz, y al final el Derecho
Postorden (IDR):
- Primero el subárbol Izquierdo, luego el Derecho, y al final la Raíz

🔗 Explicación en vídeo:
https://www.youtube.com/watch?v=Jo2euX89Oz8&ab_channel=AprendeSinEspinas

🧭 ¿Dónde empezamos?:
Imagina un círculo con 3 puntos:
- Punto oeste: preorden
- Punto sur: inorden
- Punto este: postorden

ARBOLES B ¿Qué es un árbol B o multicamino?

Study These Flashcards

Es un tipo de árbol balanceado diseñado para trabajar eficientemente con grandes cantidades de datos y acceso en disco.

Características:
- Cada nodo puede tener más de dos hijos
- Los datos están siempre ordenados
- Mantiene el equilibrio automáticamente al insertar o eliminar
- También se llama árbol de búsqueda de múltiples caminos
- Cada nodo (excepto la raíz) debe tener al menos m/2 claves, donde m es el orden del árbol

ARBOLES B ¿Qué es un árbol B+?

Study These Flashcards

Es una variante del árbol B optimizada para operaciones de lectura, muy usada en bases de datos.

Características:
- Los nodos internos solo almacenan claves de guía
- Los nodos hojas están enlazadas entre sí como una lista para facilitar el recorrido secuencial

**GRAFOS** ¿Qué es un `grafo` y cuáles son sus tipos? *`Diana No Puede Memorizar`*

Un `grafo` es una estructura formada por `nodos` (vértices) y `aristas` que los conectan. Tipos de grafos: - `Dirigido`: las aristas tienen `dirección` - `No dirigido`: las aristas no tienen dirección - `Ponderado`: las aristas tienen un `peso` - `Multigrafo`: puede tener varias aristas entre los mismos dos nodos Regla nemotécnica: “Diana No Puede Memorizar” D → Dirigido N → No dirigido P → Ponderado M → Multigrafo

**GRAFOS** ¿Qué es el `orden` de un `grafo`?

- Es el número total de `vértices` que tiene el grafo - Se representa como `n` - Es una medida fundamental para describir su tamaño

**GRAFOS** ¿Qué es el `grado` de un `vértice` (nodo) en un grafo?

- Es el número de `aristas` que inciden sobre ese `vértice` - En un grafo `no dirigido`: número total de conexiones - En un grafo `dirigido`: - `Grado de entrada`: aristas que llegan al vértice - `Grado de salida`: aristas que salen del vértice

**GRAFOS** ¿Cómo se pueden `representar` los grafos de manera ordenada y sencilla utilizando `listas` y `matrices` adyacentes?

1. `Lista de adyacencia:` - **Parte izquierda**: muestra un grafo con nodos y aristas. - **Parte derecha**: presenta la lista de adyacencia correspondiente, donde cada nodo tiene una lista de sus vecinos directos 📸 https://shorturl.at/B8vOU 2. `Matriz de adyacencia:` Es una `tabla (matriz)` donde: • Las `filas` representan los vértices de `origen`. • Las `columnas` representan los vértices de `destino`. • Cada celda indica si hay una conexión (arista) entre ellos. 📸 https://shorturl.at/eKA9Q

**GRAFOS** ¿Cuáles son algunos `algoritmos DE CAMINO MÍNIMO` clásicos de grafos?

- `Dijkstra`: calcula el `camino mínimo` desde un `vértice origen` hasta todos los demás (no admite pesos negativos) - `Bellman-Ford`: también calcula caminos mínimos y **sí admite pesos negativos** - `Floyd-Warshall`: calcula el `camino mínimo entre todos los pares de vértices`

**GRAFOS** ¿Qué hacen los algoritmos `Kruskal` y `Prim`?

Ambos buscan **generar** un `árbol de recubrimiento/expansión mínima` (spanning tree). - `Kruskal`: - Elige siempre la `arista más baratas sueltas` para ir uniendo todos los nodos. - Une vértices sin formar ciclos - `Prim`: - Empieza desde un `vértice/nodo` **EN CONCRETO** - Añade el vértice más cercano sin formar ciclos

**GRAFOS** ¿Kruskal y Prim son algoritmos de `spanning tree`? ¿Como es un **MST**?

Sí, ambos generan un `árbol de expansión mínima`. Un `spanning tree`: - Conecta todos los vértices - Usa solo las aristas necesarias (`sin ciclos`) - Tiene el menor peso posible 📸 https://shorturl.at/TgnvM

**GRAFOS** ¿Qué hace el algoritmo de `Tarjan`?

Busca `grupos de nodos` en un grafo donde: - Todos los nodos del grupo están `conectados entre sí` en ambas direcciones. Es decir, puedes ir de uno a otro y volver sin salir del grupo 📸 https://shorturl.at/pMGiL

**GRAFOS** ¿Qué hace el algoritmo de `Ford-Fulkerson`?

Sirve para calcular cuánta cantidad de `flujo máximo` puede pasar de un punto a otro en una red (como una red de tuberías)

**FICHEROS** ¿Qué es el `acceso secuencial`?

Es cuando se accede a los datos `uno tras otro`, en el mismo orden en que están guardados. Ejemplo: como leer un casete desde el principio hasta el final.

**FICHEROS** ¿Qué es el `acceso indexado`?

Es cuando se usa un `índice` para saber `dónde está` cada dato. Ejemplo: como usar el índice de un libro para ir directamente a la página que quieres.

**FICHEROS** ¿Qué es el `acceso directo`?

Es cuando se va directamente a una posición concreta del fichero, `sin pasar por los anteriores`. Ejemplo: como buscar un canal concreto en una tele sin tener que ir uno por uno.

**EXTRA** ¿Qué es una `tabla HASH`? ¿Cuando se produce una `colisión`?

Es un `TAD` (tipo abstracto de datos) Una `tabla HASH` almacena pares `clave-valor`. Usa una `función hash` para transformar `la clave (o dato)` en una posición dentro de una tabla. Una `colisión` ocurre cuando **dos claves distintas generan el mismo índice**. En ese caso, hay que aplicar una estrategia para guardar ambas (como encadenamiento o sondeo)." ✅ Ejemplo de cómo funciona una tabla HASH: Supón que quieres guardar el nombre "Ana" en una tabla HASH que tiene 5 posiciones. 1. Primero se usa una función hash que convierte "Ana" en un número. 2. Ese número se ajusta para que encaje dentro del tamaño de la tabla, es decir, se transforma en un valor entre 0 y 4 (porque la tabla tiene 5 posiciones). 3. Por ejemplo, "Ana" se guarda en la posición 2. Luego quieres guardar "Luis", y su número también se transforma en la posición 2

T3 ESTRUCTURA DE DATOS (EEDD) Flashcards

(37 cards)