Guia de practica - Árboles binarios de búsqueda
Nombre: ___________________________
Fecha: ____________________________
Puntaje: __________________________
1.
¿Qué propiedad fundamental debe cumplir un árbol binario de búsqueda (BST)?
Para cada nodo, todos los elementos del subárbol izquierdo son mayores que el nodo.
Para cada nodo, todos los elementos del subárbol izquierdo son menores que el nodo y todos los del subárbol derecho son mayores.
Todos los nodos tienen exactamente dos hijos.
El árbol siempre está balanceado automáticamente.
2.
¿Cuál es la complejidad promedio de búsqueda en un BST con n nodos si está razonablemente balanceado?
O(n)
O(log n)
O(n^2)
O(1)
3.
Al insertar el valor 15 en un BST vacío, ¿en qué lugar se coloca? Escribe 'raiz', 'izquierda' o 'derecha' según corresponda.
Respuesta: ____________________________________________
4.
¿Cómo se obtienen los elementos de un BST en orden ascendente?
Haciendo un recorrido preorden.
Haciendo un recorrido inorden.
Haciendo un recorrido postorden.
Recorriendo por niveles.
5.
Cuando se elimina un nodo hoja de un BST, ¿qué ocurre?
Se reemplaza por su hijo izquierdo.
Se reemplaza por su hijo derecho.
Simplemente se elimina y su padre deja de apuntar a él.
Se reemplaza por el nodo más pequeño del subárbol derecho.
6.
Si un nodo a eliminar tiene un solo hijo, ¿cuál es el procedimiento correcto?
Se borra el nodo y se asigna su hijo como hijo del padre.
Se intercambia el valor con su hijo y luego se elimina el hijo.
Se copia el valor del hijo al nodo padre.
No se puede eliminar, debe rebalancearse el árbol.
7.
Para eliminar un nodo con dos hijos, se suele reemplazar su valor por el del sucesor inorden. ¿Qué es el sucesor inorden?
El nodo más grande del subárbol izquierdo.
El nodo más pequeño del subárbol derecho.
El nodo padre del nodo a eliminar.
El nodo más a la izquierda del árbol completo.
8.
En un BST, la distancia desde la raíz hasta un nodo se llama __. (responde en una palabra, minúsculas, sin tilde si aplica)
Respuesta: ____________________________________________
9.
¿Cuál de los siguientes árboles es un BST? (Considera que los valores son enteros)
Raíz=10, hijo izquierdo=12, hijo derecho=8
Raíz=5, hijo izquierdo=3, hijo derecho=7, y 3 tiene hijo izquierdo=4
Raíz=20, hijo izquierdo=10, hijo derecho=30, 10 tiene hijo izquierdo=5 y hijo derecho=15
Raíz=2, hijo izquierdo=1, hijo derecho=3, y 1 tiene hijo derecho=4
10.
¿En qué caso un BST puede tener un rendimiento tan malo como O(n) en búsqueda?
Cuando el árbol está perfectamente balanceado.
Cuando el árbol se degenera en una lista enlazada (por ejemplo, insertando valores ordenados ascendentemente).
Cuando se usa inserción recursiva.
Cuando el árbol tiene más de 1000 nodos.
11.
En un BST, los tres campos típicos de un nodo (además del valor) son: puntero al hijo izquierdo, puntero al hijo derecho y puntero al __.
Respuesta: ____________________________________________
12.
¿Qué recorrido visita primero la raíz, luego el subárbol izquierdo y luego el derecho?
Inorden
Preorden
Postorden
Ninguno de los anteriores
13.
Dado el siguiente BST: raíz=50, izquierdo=30 (con izquierdo=20, derecho=40), derecho=70 (con izquierdo=60, derecho=80). ¿Cuál es el resultado de un recorrido postorden?
20, 40, 30, 60, 80, 70, 50
50, 30, 20, 40, 70, 60, 80
20, 30, 40, 50, 60, 70, 80
20, 40, 60, 80, 30, 70, 50
14.
En un BST, el predecesor inorden de un nodo es:
El nodo más pequeño del subárbol izquierdo.
El nodo más grande del subárbol izquierdo.
El nodo padre más cercano con valor menor.
El nodo que está inmediatamente a la izquierda en la representación gráfica.
15.
¿Cuál de las siguientes NO es una operación común en un BST?
Buscar un valor
Rotar el árbol (balanceo)
Eliminar un nodo
Insertar un nodo
16.
¿Cómo se llama el valor mínimo de un BST? Escribe solo la palabra.
Respuesta: ____________________________________________
17.
La búsqueda en un BST se puede implementar de forma recursiva o iterativa. ¿Cuál es la principal diferencia en términos de uso de memoria?
La recursiva usa más memoria en la pila de llamadas.
La iterativa siempre es más rápida.
La recursiva no requiere comparaciones.
No hay diferencia.
18.
En un recorrido postorden de un BST, ¿cuál es el último nodo que se visita? (escribe 'raiz' o 'izquierdo' o 'derecho' según el orden)
Respuesta: ____________________________________________
19.
¿Qué ventaja tiene un BST sobre una lista enlazada ordenada para buscar un elemento?
El BST permite búsqueda O(log n) promedio, mientras que la lista enlazada requiere O(n) incluso si está ordenada.
El BST usa menos memoria.
La lista enlazada no puede almacenar datos ordenados.
No hay diferencia significativa.
20.
¿Cuál de las siguientes afirmaciones sobre un BST es FALSA?
El recorrido inorden devuelve los elementos en orden ascendente.
La inserción siempre coloca el nuevo nodo como hoja.
La eliminación de un nodo con dos hijos siempre implica encontrar el sucesor inorden y reemplazarlo.
Un BST puede tener valores duplicados.