Hoja de ejercicios de Estructuras de datos con soluciones

En un árbol, ¿qué son los nodos hermanos?

1. ANodos a la misma profundidad en subárboles distintos
2. BNodos que no tienen hijos
3. CUn nodo y su padre
4. DNodos que tienen el mismo padre

En una tabla hash, ¿qué es una colisión?

1. AQue la tabla se quede sin memoria
2. BQue dos claves iguales se almacenen dos veces
3. CQue una clave no se pueda pasar por la función hash
4. DQue dos claves distintas se asignen al mismo índice

¿Qué estructura de datos es la más adecuada para la función «deshacer» (undo) de un editor de texto?

1. AGrafo
2. BCola (queue)
3. CPila (stack)
4. DConjunto hash (hash set)

¿Qué ocurre cuando una tabla hash hace un rehash porque su factor de carga supera un umbral?

1. ASe eliminan las claves más antiguas para hacer sitio
2. BLas claves existentes se ordenan en su sitio
3. CSolo las claves que colisionan se mueven a una lista de desbordamiento nueva al final de la tabla
4. DSe reserva una tabla mayor y se vuelve a insertar cada clave

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

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

¿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(n²), porque cada elemento se mueve n veces
4. DO(log n), por la búsqueda binaria

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(α(n))
4. DO(1)

¿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