Hoja de ejercicios de Estructuras de datos con soluciones

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

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

¿Cómo se almacenan en memoria los elementos de un arreglo?

1. AEn posiciones aleatorias elegidas por un hash
2. BEn un árbol de páginas de memoria
3. CDispersos y enlazados mediante punteros
4. DEn un bloque contiguo, uno tras otro

¿Qué estructura de datos funciona según el principio «último en entrar, primero en salir» (LIFO)?

1. ATabla hash
2. BPila (stack)
3. CCola (queue)
4. DLista enlazada

¿Por qué recorrer un arreglo suele ser en la práctica mucho más rápido que recorrer una lista enlazada de la misma longitud?

1. ARecorrer un arreglo es O(1) en total, mientras que recorrer una lista enlazada es O(n)
2. BLos elementos del arreglo son contiguos, así que aprovechan bien la caché de la CPU
3. CLos arreglos usan menos instrucciones para comparar valores
4. DLas listas enlazadas siempre almacenan los elementos en disco

¿Qué condición de equilibrio mantiene un árbol AVL en cada nodo?

1. AAmbos subárboles de cada nodo contienen exactamente el mismo número de nodos
2. BCada nodo está coloreado de rojo o de negro
3. CTodas las hojas están exactamente a la misma profundidad
4. DLas alturas de los subárboles izquierdo y derecho difieren como máximo en 1

¿Cuánta memoria utiliza una matriz de adyacencia para un grafo con V vértices?

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

¿Qué problema del sondeo lineal reduce principalmente el doble hashing?

1. ALa necesidad de almacenar las claves en la tabla
2. BEl coste O(n) de leer el valor de una clave
3. CEl agrupamiento primario, en el que se forman largas secuencias de posiciones ocupadas
4. DLa necesidad de una función hash

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)