Hoja de ejercicios de Estructuras de datos con soluciones

¿Qué estructura de datos es la más adecuada para la función «deshacer» (undo) de un editor de texto?

1. AGrafo
2. BCola (queue)
3. CConjunto hash (hash set)
4. DPila (stack)

La profundidad de un nodo en un árbol es:

1. AEl número de nodos de su subárbol
2. BEl número de aristas desde ese nodo hasta la hoja más profunda
3. CEl número de hijos de ese nodo
4. DEl número de aristas desde la raíz hasta ese nodo

¿En qué orden visita los nodos un recorrido en postorden de un árbol binario?

1. AEl subárbol derecho, luego el nodo y luego el subárbol izquierdo
2. BEl subárbol izquierdo, luego el nodo y luego el subárbol derecho
3. CEl nodo, luego el subárbol izquierdo y luego el subárbol derecho
4. DEl subárbol izquierdo, luego el subárbol derecho y luego el nodo

En una cola circular almacenada en un arreglo de capacidad n, ¿cómo se calcula la posición siguiente al índice i?

1. A(i + 1) mod n
2. Bi + 1
3. C(i − 1) mod n
4. D2i + 1

Un árbol binario tiene la raíz 1 con hijo izquierdo 2 e hijo derecho 3; el nodo 2 tiene los hijos 4 (izquierdo) y 5 (derecho). ¿Cuál es el recorrido en postorden?

1. A5 4 3 2 1
2. B4 2 5 1 3
3. C4 5 2 3 1
4. D1 2 4 5 3

Tienes una referencia a un nodo situado en medio de una lista. ¿En qué lista puedes eliminarlo en O(1)?

1. AUna lista doblemente enlazada
2. BUn arreglo dinámico
3. CUn arreglo ordenado
4. DUna lista simplemente enlazada

Sin unión por rango ni compresión de caminos, ¿cuál es el coste en el peor caso de un solo find en una estructura union-find con n elementos?

1. AO(log n)
2. BO(n)
3. CO(1)
4. DO(α(n))

¿Cuál es la principal ventaja de una skip list sobre una lista enlazada ordenada?

1. ANo usa memoria adicional
2. BAlmacena las claves sin orden
3. CBúsqueda garantizada en O(1), porque cada nodo guarda un puntero a todos los demás nodos
4. DBúsqueda esperada en O(log n) gracias a varios niveles de punteros hacia delante