Hoja de ejercicios de Estructuras de datos con soluciones

¿Qué estructura se utiliza normalmente para implementar una cola de prioridad?

1. AUna lista simplemente enlazada sin orden
2. BUn montículo (heap)
3. CUna pila (stack)
4. DUna cadena de caracteres

Un grafo está formado por:

1. ASolo claves y hashes
2. BFilas y columnas
3. CSolo una raíz y hojas
4. DVértices (nodos) conectados por aristas

En un árbol binario de búsqueda, los valores del subárbol izquierdo de un nodo son:

1. AMenores que el valor del nodo
2. BDe orden aleatorio
3. CMayores que el valor del nodo
4. DIguales al valor del nodo

¿Cuál es la altura en el peor caso de un árbol binario de búsqueda con n nodos si las claves se insertan en orden?

1. An (se convierte en una lista enlazada)
2. B√n
3. C1
4. Dlog₂ n

Las claves 50, 30, 70, 20, 40 se insertan en este orden en un árbol binario de búsqueda vacío. ¿Cuál es el hijo izquierdo de 30?

1. A50
2. B20
3. C40
4. D70

¿Cuánta memoria usa una lista de adyacencia para un grafo con V vértices y E aristas?

1. AO(V²)
2. BO(V × E)
3. CO(V + E)
4. DO(E²)

La estructura union-find (conjuntos disjuntos) con unión por rango y compresión de caminos tiene un coste amortizado por operación de:

1. AExactamente O(log n)
2. BO(n)
3. CO(n²)
4. DO(α(n)), la inversa de la función de Ackermann, que en la práctica es constante

Al insertar una clave en un árbol AVL, el subárbol izquierdo de un nodo queda demasiado alto, y la nueva clave fue al subárbol izquierdo de su hijo izquierdo (caso izquierda-izquierda). ¿Qué corrección se aplica?

1. AUna rotación simple a la derecha en el nodo desequilibrado
2. BRecolorear el nodo y su hijo
3. CUna rotación a la izquierda en el hijo y luego una rotación a la derecha en el nodo
4. DUna rotación simple a la izquierda en el nodo desequilibrado