Guia de practica - Árboles binarios de búsqueda

1.

1. Para cada nodo, todos los elementos del subárbol izquierdo son mayores que el nodo.

2. Para cada nodo, todos los elementos del subárbol izquierdo son menores que el nodo y todos los del subárbol derecho son mayores.

3. Todos los nodos tienen exactamente dos hijos.

4. El árbol siempre está balanceado automáticamente.

2.

1. O(n)

2. O(log n)

3. O(n^2)

4. O(1)

3.

Respuesta: ____________________________________________

4.

1. Haciendo un recorrido preorden.

2. Haciendo un recorrido inorden.

3. Haciendo un recorrido postorden.

4. Recorriendo por niveles.

5.

1. Se reemplaza por su hijo izquierdo.

2. Se reemplaza por su hijo derecho.

3. Simplemente se elimina y su padre deja de apuntar a él.

4. Se reemplaza por el nodo más pequeño del subárbol derecho.

6.

1. Se borra el nodo y se asigna su hijo como hijo del padre.

2. Se intercambia el valor con su hijo y luego se elimina el hijo.

3. Se copia el valor del hijo al nodo padre.

4. No se puede eliminar, debe rebalancearse el árbol.

7.

1. El nodo más grande del subárbol izquierdo.

2. El nodo más pequeño del subárbol derecho.

3. El nodo padre del nodo a eliminar.

4. El nodo más a la izquierda del árbol completo.

8.

Respuesta: ____________________________________________

9.

1. Raíz=10, hijo izquierdo=12, hijo derecho=8

2. Raíz=5, hijo izquierdo=3, hijo derecho=7, y 3 tiene hijo izquierdo=4

3. Raíz=20, hijo izquierdo=10, hijo derecho=30, 10 tiene hijo izquierdo=5 y hijo derecho=15

4. Raíz=2, hijo izquierdo=1, hijo derecho=3, y 1 tiene hijo derecho=4

10.

1. Cuando el árbol está perfectamente balanceado.

2. Cuando el árbol se degenera en una lista enlazada (por ejemplo, insertando valores ordenados ascendentemente).

3. Cuando se usa inserción recursiva.

4. Cuando el árbol tiene más de 1000 nodos.

11.

Respuesta: ____________________________________________

12.

1. Inorden

2. Preorden

3. Postorden

4. Ninguno de los anteriores

13.

1. 20, 40, 30, 60, 80, 70, 50

2. 50, 30, 20, 40, 70, 60, 80

3. 20, 30, 40, 50, 60, 70, 80

4. 20, 40, 60, 80, 30, 70, 50

14.

1. El nodo más pequeño del subárbol izquierdo.

2. El nodo más grande del subárbol izquierdo.

3. El nodo padre más cercano con valor menor.

4. El nodo que está inmediatamente a la izquierda en la representación gráfica.

15.

1. Buscar un valor

2. Rotar el árbol (balanceo)

3. Eliminar un nodo

4. Insertar un nodo

16.

Respuesta: ____________________________________________

17.

1. La recursiva usa más memoria en la pila de llamadas.

2. La iterativa siempre es más rápida.

3. La recursiva no requiere comparaciones.

4. No hay diferencia.

18.

Respuesta: ____________________________________________

19.

1. El BST permite búsqueda O(log n) promedio, mientras que la lista enlazada requiere O(n) incluso si está ordenada.

2. El BST usa menos memoria.

3. La lista enlazada no puede almacenar datos ordenados.

4. No hay diferencia significativa.

20.

1. El recorrido inorden devuelve los elementos en orden ascendente.

2. La inserción siempre coloca el nuevo nodo como hoja.

3. La eliminación de un nodo con dos hijos siempre implica encontrar el sucesor inorden y reemplazarlo.

4. Un BST puede tener valores duplicados.