Test Tema 10: Relaciones y árboles

Este test está basado en las 15 preguntas del cuestionario del tema. Tiene una sola respuesta correcta por pregunta. Selecciona tus respuestas y pulsa Comprobar respuestas para conocer tu nota, ver la explicación rápida de cada pregunta y consultar al final las soluciones explicadas paso a paso.

Criterio de puntuación

Las preguntas 1–10 valen 0,70 puntos cada una y las preguntas 11–15 valen 0,60 puntos cada una. La puntuación máxima es 9,00 puntos.

Cómo estudiar

Haz primero el test sin mirar las soluciones. Al corregirlo, lee la explicación rápida de cada pregunta y, si necesitas profundizar, despliega la explicación detallada paso a paso al final de la página.

0 de 15 respondidas ¡Empieza cuando quieras!

1. ¿Cuál de las siguientes afirmaciones describe correctamente una propiedad de una relación reflexiva?

A. Una relación reflexiva es una relación en la que cada par de elementos distintos está relacionado en ambas direcciones. B. Una relación reflexiva es una relación en la que cada elemento está relacionado consigo mismo. C. Una relación reflexiva es una relación que no tiene ciclos. D. Una relación reflexiva es una relación en la que no hay elementos relacionados.

2. ¿Qué es una relación simétrica?

A. Una relación en la que (a,b)∈R implica que (b,a)∈R. B. Una relación en la que (a,b)∈R implica que (a,a)∈R. C. Una relación en la que (a,a)∈R para todo a∈A. D. Una relación en la que no existen pares de elementos relacionados.

3. ¿Cuál es el recorrido en preorden de un árbol binario?

A. Recorrer la raíz, luego el subárbol izquierdo y finalmente el subárbol derecho. B. Recorrer primero los nodos hoja. C. Recorrer la raíz, luego el subárbol derecho y finalmente el subárbol izquierdo. D. Recorrer primero los nodos internos.

4. ¿Cuál es el recorrido en inorden de un árbol binario?

A. Recorrer el subárbol izquierdo, luego la raíz y finalmente el subárbol derecho. B. Recorrer la raíz, luego el subárbol izquierdo y finalmente el subárbol derecho. C. Recorrer la raíz, luego el subárbol derecho y finalmente el subárbol izquierdo. D. Recorrer primero los nodos hoja.

5. ¿Cuál es el recorrido en posorden de un árbol binario?

A. Recorrer el subárbol izquierdo, luego el subárbol derecho y finalmente la raíz. B. Recorrer la raíz, luego el subárbol izquierdo y finalmente el subárbol derecho. C. Recorrer el subárbol derecho, luego el subárbol izquierdo y finalmente la raíz. D. Recorrer primero los nodos internos.

6. ¿Cuál de los siguientes recorridos es un recorrido de amplitud?

A. Recorrer cada nivel del árbol de izquierda a derecha, comenzando por la raíz. B. Recorrer cada nivel del árbol de derecha a izquierda, comenzando por la raíz. C. Recorrer primero los nodos hoja y luego los nodos internos. D. Recorrer la raíz, luego el subárbol izquierdo y finalmente el subárbol derecho.

7. ¿Cuál de las siguientes afirmaciones describe correctamente una relación transitiva?

A. Si (a,b)∈R y (b,c)∈R, entonces (a,c)∈R. B. Si (a,b)∈R, entonces (b,a)∈R. C. Si (a,a)∈R para todo a∈A. D. Si (a,b)∈R para todo a,b∈A.

8. ¿Cuál de las siguientes propiedades no es necesaria para que una relación sea de equivalencia?

A. Reflexividad. B. Simetría. C. Transitividad. D. Antisimetría.

9. ¿Qué es una relación antisimétrica?

A. Una relación en la que (a,b)∈R y (b,a)∈R implican que a=b. B. Una relación en la que (a,b)∈R implica que (b,a)∈R. C. Una relación en la que (a,a)∈R para todo a∈A. D. Una relación en la que no existen pares de elementos relacionados.

10. ¿Cuál de las siguientes aplicaciones utiliza árboles en informática?

A. Búsqueda en bases de datos. B. Compresión de datos. C. Representación de expresiones algebraicas. D. Todas las anteriores.

11. ¿Cómo se utiliza un árbol binario de búsqueda (BST) en la informática?

A. Para ordenar elementos de manera eficiente. B. Para almacenar datos en un formato comprimido. C. Para realizar cálculos matemáticos complejos. D. Para representar relaciones jerárquicas simples.

12. ¿Cuál es una ventaja de utilizar un árbol AVL sobre un árbol binario de búsqueda estándar?

A. Los árboles AVL permiten ciclos. B. Los árboles AVL son más simples de implementar. C. Los árboles AVL mantienen un equilibrio que asegura tiempos de búsqueda eficientes. D. Los árboles AVL no requieren equilibrio.

13. ¿Cómo se utiliza un árbol de expresión en la evaluación de expresiones algebraicas?

A. Los nodos representan operaciones y los hijos representan operandos. B. Los nodos representan operandos y los hijos representan operaciones. C. Los nodos y los hijos representan ciclos. D. Los nodos y los hijos representan relaciones reflexivas.

14. ¿Cuál es una aplicación de los árboles de decisión?

A. Para tomar decisiones basadas en datos mediante una estructura jerárquica de condiciones. B. Para representar datos en un formato comprimido. C. Para realizar cálculos matemáticos complejos. D. Para buscar datos en un formato desordenado.

15. Dado el árbol binario estándar del tema, ¿cuál es su recorrido en inorden?

A. D, B, E, A, C, F. B. A, B, D, E, C, F. C. D, E, B, A, F, C. D. A, B, C, D, E, F.

Comprobar respuestas Reiniciar test

Soluciones explicadas: aprende pregunta por pregunta

1. Respuesta correcta: B — Definición de Relación Reflexiva

Una relación binaria $R$ sobre un conjunto $A$ es **reflexiva** si todos y cada uno de los elementos de $A$ están relacionados consigo mismos: \[ \forall a \in A, \quad (a, a) \in R \] **Propiedad matricial:** Su matriz booleana asociada $M_R$ contiene exclusivamente $1$s en la diagonal principal ($M_{ii} = 1$).

2. Respuesta correcta: A — Definición de Relación Simétrica

Una relación $R$ sobre un conjunto $A$ es **simétrica** si la relación es reversible para cualquier par de elementos: \[ \forall a, b \in A, \quad (a, b) \in R \implies (b, a) \in R \] **Propiedad matricial:** La matriz booleana $M_R$ es traspuesta de sí misma ($M_R = M_R^T$).

3. Respuesta correcta: A — Recorrido en Preorden (RID)

El recorrido en **Preorden** es un algoritmo de exploración en profundidad (DFS) para árboles binarios que sigue la secuencia **RID**: 1. Visitar la **Raíz** ($R$). 2. Recorrer el subárbol **Izquierdo** ($I$) en preorden. 3. Recorrer el subárbol **Derecho** ($D$) en preorden.

4. Respuesta correcta: A — Recorrido en Inorden (IRD)

El recorrido en **Inorden** explora el árbol binario siguiendo la regla **IRD**: 1. Recorrer el subárbol **Izquierdo** ($I$) en inorden. 2. Visitar la **Raíz** ($R$). 3. Recorrer el subárbol **Derecho** ($D$) en inorden. *Aplicación:* En un Árbol Binario de Búsqueda (BST), el recorrido en inorden procesa los elementos en **orden estrictamente creciente**.

5. Respuesta correcta: A — Recorrido en Posorden (IDR)

El recorrido en **Posorden** explora el árbol binario según el esquema **IDR**: 1. Recorrer el subárbol **Izquierdo** ($I$) en posorden. 2. Recorrer el subárbol **Derecho** ($D$) en posorden. 3. Visitar la **Raíz** ($R$). *Aplicación:* Es el orden ideal para liberar la memoria de un árbol o evaluar expresiones algebraicas en notación postfija (Polaca Inversa).

6. Respuesta correcta: A — Recorrido en Amplitud (BFS)

El recorrido en **Amplitud** (o BFS - Breadth-First Search): - Explora el árbol **por niveles**, comenzando en el nivel 0 (raíz). - Procesa todos los nodos pertenecientes a un nivel de izquierda a derecha antes de descender al siguiente nivel. - Para su implementación en código se utiliza típicamente una estructura de datos tipo **Cola (FIFO)**.

7. Respuesta correcta: A — Definición de Relación Transitiva

Una relación $R$ sobre $A$ es **transitiva** si el encadenamiento de dos relaciones exige la existencia directa del atajo: \[ \forall a, b, c \in A, \quad ((a, b) \in R \land (b, c) \in R) \implies (a, c) \in R \]

8. Respuesta correcta: D — Propiedades para la Relación de Equivalencia

Una relación $R$ es de **equivalencia** si cumple simultáneamente: 1. **Reflexiva** 2. **Simétrica** 3. **Transitiva** La **antisimetría** es una propiedad requerida para las **relaciones de orden** (parcial o total), no para las de equivalencia.

9. Respuesta correcta: A — Definición de Relación Antisimétrica

Una relación $R$ sobre $A$ es **antisimétrica** si no permite relaciones bidireccionales entre elementos distintos: \[ \forall a, b \in A, \quad ((a, b) \in R \land (b, a) \in R) \implies a = b \] Es decir, si $a \neq b$, nunca pueden existir simultáneamente $(a, b) \in R$ y $(b, a) \in R$.

10. Respuesta correcta: D — Aplicaciones de Árboles en Informática

Los árboles son estructuras de datos no lineales fundamentales empleadas en: - **Bases de datos:** B-Trees y B+Trees para la indexación y optimización de búsquedas en disco. - **Compresión de datos:** Árboles de Huffman para codificación de longitud variable sin prefijo. - **Compiladores y cálculo:** Árboles de expresión sintáctica abstracta (AST) para parser y compilación.

11. Respuesta correcta: A — Árbol Binario de Búsqueda (BST)

Un **BST** (Binary Search Tree) es un árbol binario estructurado según la propiedad de orden: - Para cualquier nodo $x$, las claves de su subárbol izquierdo son menor que su clave ($\text{clave}(izq) < \text{clave}(x)$). - Las claves de su subárbol derecho son mayor que su clave ($\text{clave}(der) > \text{clave}(x)$). Esto permite buscar, insertar y eliminar elementos en tiempo $O(h)$, donde $h$ es la altura del árbol.

12. Respuesta correcta: C — Ventajas de los Árboles AVL

Un **árbol AVL** (Adelson-Velsky y Landis) es un BST autoequilibrado donde: - Para cada nodo, la diferencia entre la altura del subárbol izquierdo y la del subárbol derecho (factor de equilibrio) es como máximo $1$ (sólo puede ser $-1, 0, 1$). - Al realizar inserciones o borrados, si se rompe el equilibrio se realizan **rotaciones de nodos**. - Garantiza una altura óptima de $h = O(\log n)$, evitando la degradación a listas enlazadas de los BST estándar.

13. Respuesta correcta: A — Árboles de Expresión

En un **árbol de expresión**: - Los **nodos internos** representan los operadores matemáticos o lógicos (ej. $+$, $-$, $*$, $/$). - Las **hojas** (nodos terminales) representan los operandos (constantes numéricas o variables). - Su evaluación en **posorden** produce la notación postfija y calcula el valor de la expresión de forma jerárquica.

14. Respuesta correcta: A — Árboles de Decisión

En aprendizaje automático y toma de decisiones, un **árbol de decisión**: - Presenta en sus nodos internos preguntas o condiciones sobre los datos/atributos. - Presenta en las ramas las posibles respuestas a dicha prueba. - Presenta en sus hojas la decisión final, categoría o valor predicho.

15. Respuesta correcta: A — Recorrido Inorden de ejemplo

Estructura habitual de referencia: - Raíz: $A$ - Subárbol izquierdo de $A$: Raíz $B$, con hijo izquierdo $D$ e hijo derecho $E$. - Subárbol derecho de $A$: Raíz $C$, con hijo derecho $F$. **Cálculo Inorden (IRD):** 1. Subárbol Izquierdo de $A$ (Raíz $B$): - Subárbol Izquierdo de $B \to D$ - Raíz $B \to B$ - Subárbol Derecho de $B \to E$ - *Resultado subárbol izq:* $D, B, E$ 2. Raíz principal $\to A$ 3. Subárbol Derecho de $A$ (Raíz $C$): - Subárbol Izquierdo de $C \to \emptyset$ - Raíz $C \to C$ - Subárbol Derecho de $C \to F$ - *Resultado subárbol der:* $C, F$ **Secuencia completa:** $D, B, E, A, C, F$.

---

Chuleta final: lo imprescindible para aprobar

1. Relaciones y propiedades

• Reflexiva: \(\forall a, (a, a) \in R\). Diagonal de la matriz llena de \(1\)s.
• Simétrica: \((a, b) \in R \implies (b, a) \in R\). Matriz simétrica (\(M = M^T\)).
• Antisimétrica: \((a, b) \in R \land (b, a) \in R \implies a = b\).
• Transitiva: \((a, b) \in R \land (b, c) \in R \implies (a, c) \in R\).
• Relación de Equivalencia: Reflexiva + Simétrica + Transitiva.
• Relación de Orden: Reflexiva + Antisimétrica + Transitiva.

2. Recorridos de Árboles Binarios

Recorrido	Regla Mnemotécnica	Secuencia de Exploración
Preorden	**R**aíz **PRE**viamente	R**aíz \(\to\) **I**zquierda \(\to\) **D**erecha (**RID)
Inorden	R**aíz **EN medio	I**zquierda \(\to\) **R**aíz \(\to\) **D**erecha (**IRD)
Posorden	**R**aíz **POST**eriormente	I**zquierda \(\to\) **D**erecha \(\to\) **R**aíz (**IDR)
Amplitud	Por Niveles (BFS)	De arriba a abajo, de izquierda a derecha (Usa Cola/FIFO)

3. Tipos de Árboles y Complejidad

• BST (Binary Search Tree): Claves \(Izquierdas < Raíz < Claves Derechas\). Inorden da elementos ordenados.
• Árbol AVL: BST autoequilibrado mediante rotaciones. Factor de equilibrio \(\in \{-1, 0, 1\}\). Operaciones garantizadas en \(O(\log n)\).
• Árbol de Expresión: Operadores en nodos internos, operandos en hojas.
• Árbol de Decisión: Condiciones en nodos internos, clasificaciones/predicciones en hojas.