Hoja de ejercicios de Estructuras de datos con soluciones

¿Qué es un grafo dirigido?

1. AUn grafo en el que cada par de vértices distintos está unido por una arista
2. BUn grafo que no tiene ciclos
3. CUn grafo cuyas aristas tienen todas peso
4. DUn grafo cuyas aristas tienen un sentido de un vértice a otro

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

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

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

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

Los árboles AVL y los árboles rojo-negro garantizan:

1. ABúsqueda en tiempo constante en todos los casos
2. BUna altura O(log n) mediante el rebalanceo
3. CQue las claves se almacenen en orden de inserción
4. DQue ningún nodo tenga dos hijos

¿Cómo se inserta un elemento nuevo en un montículo binario?

1. ASe coloca en la raíz y se hace bajar (sift-down)
2. BSe inserta en su posición ordenada desplazando una posición a la derecha todos los elementos mayores
3. CSe reconstruye todo el montículo desde cero
4. DSe coloca al final del arreglo y se hace subir (sift-up) mientras viole la propiedad de montículo

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. C2i + 1
4. D(i + 1) mod n

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)

Para que una tabla hash funcione correctamente, ¿qué regla deben cumplir el hash y la igualdad?

1. ALas claves iguales deben tener valores hash iguales
2. BLos valores hash deben ser números primos
3. CValores hash iguales implican claves iguales
4. DLas claves distintas deben tener valores hash distintos