Hoja de ejercicios de Estructuras de datos con soluciones

¿Cuál es la principal diferencia entre un arreglo estático y un arreglo dinámico?

1. AUn arreglo dinámico puede crecer trasladándose a un bloque de memoria mayor
2. BUn arreglo dinámico almacena sus elementos en nodos enlazados para poder crecer de uno en uno
3. CUn arreglo estático tiene un acceso por índice más lento
4. DUn arreglo estático solo puede almacenar números

En una lista simplemente enlazada, ¿qué contiene el puntero al siguiente del último nodo?

1. ANull (ningún nodo)
2. BLa dirección del primer nodo
3. CEl número de nodos de la lista
4. DLa dirección del nodo anterior

La profundidad de un nodo en un árbol es:

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

En una tabla hash con direccionamiento abierto, ¿cuál es el factor de carga máximo posible?

1. A0,5
2. B2
3. C1
4. DNo hay máximo

¿Cuál es el coste de insertar un elemento en medio de un arreglo de n elementos?

1. AO(1), porque se conoce el índice
2. BO(n), porque los elementos posteriores deben desplazarse
3. CO(log n), por la búsqueda binaria
4. DO(n²), porque cada elemento se mueve n veces

¿Cuántos nodos tiene un árbol binario perfecto de altura h, contando la altura en aristas?

1. A2h + 1
2. Bh²
3. C2^h+1 − 1
4. D2^h

Debes conservar los k valores más pequeños de un flujo de n números usando O(k) de memoria. ¿Qué enfoque funciona en un tiempo O(n log k)?

1. AUna cola FIFO con los últimos k valores
2. BUn arreglo ordenado con los n valores
3. CUn max-heap de tamaño k, sustituyendo su raíz cuando llega un valor menor
4. DUn min-heap que contiene los n valores, del que se extraen al final los k menores

La complejidad temporal de decrease-key en un montículo binario (conociendo la posición del elemento) es:

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