TEMA 3 ESTRUCTURA DE DATOS

Question 1

¿Qué es un árbol completo en informática?

Answer 1

Un árbol completo es un árbol binario en el que todos los niveles están completamente llenos. SI ES BINARIO TODOS TIENEN DOS HIJOS.

Question 2

¿Qué es un montículo binario?

Answer 2

Es una estructura de datos tipo árbol binario completo que cumple la propiedad de montículo:

En un min-heap, cada nodo es menor o igual que sus hijos.

En un max-heap, cada nodo es mayor o igual que sus hijos.

Question 3

¿Qué es un min-heap?

Answer 3

Es un montículo binario donde el valor de cada nodo es menor o igual que los de sus hijos.
→ El menor elemento siempre está en la raíz.

Question 4

¿Qué es un max-heap?

Answer 4

Es un montículo binario donde el valor de cada nodo es mayor o igual que los de sus hijos.
→ El mayor elemento está en la raíz.

Question 5

¿Para qué se usan los montículos binarios?

Answer 5

Implementar colas de prioridad.

Algoritmos de ordenación heap sort.

Algoritmos de camino mínimo (como Dijkstra).

Programación de tareas o procesos por prioridad.

Question 6

¿Qué es un árbol binario de búsqueda?

Answer 6

Es un árbol binario en el que:
🔹 Cada nodo tiene un valor.
🔹 Los valores menores están en la subrama izquierda.
🔹 Los valores mayores están en la subrama derecha.
✔️ Permite búsqueda, inserción y eliminación en O(log n) (si está balanceado).

Question 7

¿Qué es el factor de equilibrio en un árbol binario (AVL)?

Answer 7

FactordeEquilibrio

📘 El factor de equilibrio (balance factor, AUTOBALANCEABLES) de un nodo en un árbol AVL (EL MAS CONOCIDO) es:
➡️ La diferencia entre la altura del subárbol izquierdo y la altura del subárbol derecho:

AlturaIzquierda
−
AlturaDerecha
FactordeEquilibrio=AlturaIzquierda−AlturaDerecha
🔢 Valores posibles:

✅ -1, 0, 1 → El árbol está equilibrado.

❌ < -1 o > 1 → El árbol está desequilibrado y necesita una rotación para balancearse.

🧠 Se usa para mantener el árbol balanceado después de inserciones o eliminaciones.

Question 8

❓ ¿Qué es un recorrido en profundidad (DFS)?

Answer 8

Es un método de recorrer un árbol o grafo desde la raíz hasta las hojas, explorando lo más profundo posible antes de retroceder.

Question 9

❓ Tipos de DFS ( recorridos en profundidad ) en árboles binario

Answer 9

Inorden (Inorder): Izquierda - Raíz - Derecha

Preorden (Preorder): Raíz - Izquierda - Derecha

Postorden (Postorder): Izquierda - Derecha - Raíz

Question 10

❓ ¿DFS ( recorridos en profundidad )usa pila o cola?

Answer 10

➡️ Usa pila (stack), ya sea explícita o mediante la recursión.

Question 11

En que tipo de Árbol encontraríamos una secuencia ordenada (A,B,C,D,E,F,G) en el recorrido INORDEN

Answer 11

En un Árbol Binario de Búsqueda

Question 12

Quien es la raiz en un PREORDEN?? 13,8,6,16,15,17

Answer 12

EL PRIMERO- 13

Question 13

Quien es la raiz en un POSTORDEN?? 6,8,15,17,16,13

Answer 13

EL ULTIMO -13

Question 14

❓ ¿Qué es un árbol B?

Answer 14

Es un árbol balanceado por niveles, usado para almacenamiento en disco o bases de datos.
Cada nodo puede tener múltiples claves e hijos (no binario).
Cuando se llena de claves, se divide y se promueve una clave al nodo padre.
Todas las hojas están a la misma profundidad (balanceado).
Cuando se llena de claves, se divide y se promueve una clave al nodo padre.

Question 15

Variantes de Arbol B??

Answer 15

Arbol B+: nodos internos solo contienen claves y punteros. Nodos hojas están enlazados entre sí.(IMP.)
Arbol *:garantiza una densidad de ocupación de 2/3.

Question 16

❓ ¿Qué es el orden de un grafo?

Answer 16

➡️ Es el **número de nodos (vértices) que tiene el grafo.

Question 17

❓ ¿Qué es el orden de un árbol (B o B+)?

Answer 17

➡️ Es el máximo número de hijos que puede tener un nodo interno.

Question 18

❓ ¿Es el “orden” lo mismo en árboles y grafos?

Answer 18

➡️ ❌ No.

En grafos → número de nodos.

En árboles B → número máximo de hijos por nodo.

Question 19

❓ ¿Qué es el grado de un grafo?

Answer 19

➡️ Es el mayor grado entre todos los nodos del grafo.

Question 20

❓ ¿Qué es el grado de un nodo en un grafo?

Answer 20

➡️ Número de aristas que conectan al nodo.

Question 21

❓ ¿Qué es el grado de un nodo en un árbol?

Answer 21

➡️ Número de hijos (nodos descendientes directos).

Question 22

❓ ¿Qué es el grado de un árbol?

Answer 22

➡️ Es el mayor grado entre todos sus nodos.

Question 23

❓ ¿Cuáles son las formas comunes de representar un grafo?

Answer 23

➡️ Matriz de adyacencia y lista de adyacencia.

Question 24

❓ ¿Qué es una matriz de adyacencia? (MA)

Answer 24

➡️ Una tabla 𝑛×𝑛 donde cada celda indica si hay una arista entre dos nodos. y sobre todo destacar que desperdicia memoria si hay muchos nodos.

Question 25

❓ ¿Qué es una lista de adyacencia?(LA)

Answer 25

➡️ Cada nodo tiene una lista con los nodos a los que está conectado. Array de vertices + listas enlazadas.

Question 26

Los Algoritmos de Camino Minimo mas importantes??

Answer 26

DIJKSTRA, JOHNSON, BELLMAN-FORD, VITERBI, FLOYD-WARSHALL, A*

Question 27

Qué es un árbol de camino mínimo?

Answer 27

Un árbol que conecta un nodo origen con todos los demás, usando caminos de menor peso o distancia desde ese nodo.

Question 28

❓ ¿Qué hace el algoritmo de Dijkstra?

Answer 28

➡️ Encuentra el camino más corto desde un nodo a todos los demás (pesos positivos).🚫 No funciona con pesos negativos.

Question 29

❓ ¿Qué hace Bellman-Ford?

Answer 29

➡️ Encuentra el camino más corto (incluso con pesos negativos) y detecta ciclos negativos.

Question 30

❓ ¿Qué hace Floyd-Warshall?

Answer 30

➡️ Calcula caminos más cortos entre todos los pares de nodos.

Question 31

❓ ¿Para qué sirve Johnson?

Answer 31

➡️ Encuentra caminos más cortos entre todos los pares ✅ Funciona con pesos negativos, pero sin ciclos negativos. Usa Bellman-Ford para reetiquetar los pesos. Aplica Dijkstra desde cada nodo. 🧠 Eficiente en grafos dispersos.

Question 32

❓ ¿Qué hace Viterbi?

Answer 32

➡️ Encuentra la secuencia más probable de estados ocultos (en modelos HMM). Es el camino mas probable en un modelo probabilistico.➡️ Reconocimiento de voz, NLP, bioinformática.

Question 33

❓ ¿Cómo funciona A*?

Answer 33

➡️ Videojuegos, mapas, robótica. ✅ Rápido y óptimo si la heurística es admisible. ℎ(𝑛) h(n): estimación hasta el objetivo (heurística)

Question 34

Algoritmos de Recubrimiento mínimo??

Answer 34

PRIM y KRUSTAL

Question 35

¿Qué es un árbol de recubrimiento mínimo?

Answer 35

Un árbol que conecta todos los nodos del grafo con el menor peso total, sin importar los caminos individuales.

Question 36

¿Cómo funciona el algoritmo de Kruskal?

Answer 36

Caminos mas óptimos para maximizar flujo, el que conecta todos los nodos con peso mínimo total. Ordena aristas por peso (menor a mayor). Añade aristas si no forman ciclo (Union-Find). Complejidad: O(E log E).

Question 37

¿Cómo funciona el algoritmo de Prim?

Answer 37

Encontrar el árbol de expansión mínima en un grafo conectad, no dirigido y ponderado.

Question 38

Tipos de accesos a ficheros?

Answer 38

Acceso Secuencial, directo, indexado, Hibrido o ISAM.

Question 39

¿Qué es el acceso secuencial a ficheros?

Answer 39

Los datos se leen o escriben en orden, uno tras otro, desde el inicio hasta el final. Es el tipo más simple y común.

Question 40

¿En qué consiste el acceso directo o aleatorio a ficheros?

Answer 40

Permite acceder directamente a una posición específica del fichero, sin leer los datos anteriores. Requiere conocer la ubicación del dato.

Question 41

¿Qué es el acceso indexado a ficheros?

Answer 41

Usa un índice (como en un libro) para localizar rápidamente bloques o registros dentro del fichero. Combina eficiencia y flexibilidad. Un fichero para el índice y otro para datos. Se busca la clave en el índice (ordenado) y nos da la posición en el archivo.

Question 42

¿Qué es el acceso híbrido o ISAM?

Answer 42

ISAM combina acceso secuencial e indexado. Usa un índice jerárquico para localizar rápidamente un bloque y luego accede secuencialmente dentro de ese bloque. Es ideal para ficheros grandes que necesitan búsquedas rápidas y recorrido ordenado. Ejemplo: MyISAM de MySQL.

Question 43

¿En qué consiste la ordenación externa de ficheros?

Answer 43

Se usa cuando el fichero no cabe en memoria. Se divide en partes pequeñas, se ordenan internamente, y luego se mezclan en disco (Merge externo).

Question 44

¿En qué consiste la mezcla natural?

Answer 44

etecta y usa automáticamente las subsecuencias ordenadas ya existentes en el fichero. Reduce el número de runs iniciales y mejora el rendimiento.

Question 45

¿Qué es la mezcla directa en ordenación externa?

Answer 45

Es un método de ordenación externa que no detecta runs naturales. Divide el fichero en bloques de tamaño fijo, los ordena individualmente en memoria y luego los mezcla sistemáticamente en varias fases.