Hoja de ejercicios de Estructuras de datos con soluciones

En un grafo, ¿qué es un ciclo?

1. AUn camino que empieza y termina en el mismo vértice
2. BUna arista con peso cero
3. CUn vértice sin aristas
4. DUn camino que visita todos los vértices

¿Qué hace una función hash en una tabla hash?

1. AOrdena las claves de la tabla
2. BCuenta cuántas claves hay almacenadas
3. CAsigna una clave a un índice de la tabla
4. DCifra los valores de la tabla

¿En qué orden visita los nodos un recorrido en postorden de un árbol binario?

1. AEl subárbol derecho, luego el nodo y luego el subárbol izquierdo
2. BEl nodo, luego el subárbol izquierdo y luego el subárbol derecho
3. CEl subárbol izquierdo, luego el subárbol derecho y luego el nodo
4. DEl subárbol izquierdo, luego el nodo y luego el subárbol derecho

Tienes una referencia a un nodo situado en medio de una lista. ¿En qué lista puedes eliminarlo en O(1)?

1. AUn arreglo dinámico
2. BUna lista simplemente enlazada
3. CUna lista doblemente enlazada
4. DUn arreglo ordenado

¿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(E)
2. BO(log V)
3. CO(V + E)
4. DO(V²)

¿Por qué podría un servidor elegir su función hash al azar de entre una familia universal?

1. APara que la tabla hash quede ordenada
2. BPara eliminar la necesidad de redimensionar la tabla
3. CPara que sea muy improbable que un atacante pueda elegir muchas claves que colisionen todas
4. DPara garantizar que dos claves nunca puedan colisionar, sean cuales sean las claves que envíe un atacante

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

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