Hoja de ejercicios de Estructuras de datos con soluciones

En un árbol, ¿qué es una hoja?

1. AUn nodo sin hijos
2. BEl nodo con el valor más grande
3. CUn nodo sin padre
4. DUn nodo con exactamente un hijo

La profundidad de un nodo en un árbol es:

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

¿Qué es el factor de carga de una tabla hash?

1. AEl número de colisiones producidas hasta ahora
2. BEl número de cubetas dividido entre la longitud media de las claves almacenadas
3. CEl tiempo necesario para cargar la tabla desde el disco
4. DEl número de elementos almacenados dividido entre el número de cubetas

¿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. ALos arreglos usan menos instrucciones para comparar valores
2. BLas listas enlazadas siempre almacenan los elementos en disco
3. CLos elementos del arreglo son contiguos, así que aprovechan bien la caché de la CPU
4. DRecorrer un arreglo es O(1) en total, mientras que recorrer una lista enlazada es O(n)

Un recorrido en orden (in-order) de un árbol binario de búsqueda visita las claves en:

1. AOrden por niveles
2. BOrden de inserción
3. CSiempre orden descendente
4. DOrden ascendente

¿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. A1
2. Bn (se convierte en una lista enlazada)
3. C√n
4. Dlog₂ n

En el algoritmo de Kruskal para el árbol de expansión mínima, ¿para qué se usa la estructura union-find?

1. APara comprobar si los dos extremos de una arista ya están conectados
2. BPara ordenar las aristas por peso
3. CPara elegir el vértice inicial
4. DPara almacenar la distancia actual de cada vértice al origen durante la búsqueda

¿Por qué no se pueden eliminar elementos de un filtro de Bloom estándar simplemente poniendo a cero sus bits?

1. AEsos bits pueden pertenecer también a otros elementos, lo que causaría falsos negativos
2. BLos filtros de Bloom almacenan los elementos completos, que ya no pueden volver a localizarse una vez aplicado el hash
3. CEliminar elevaría la tasa de falsos positivos al 100%
4. DLos bits de un filtro de Bloom no pueden cambiarse después de crearlo