Hoja de ejercicios de Estructuras de datos con soluciones

¿Qué es un grafo dirigido?

1. AUn grafo que no tiene ciclos
2. BUn grafo en el que cada par de vértices distintos está unido por una arista
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 tiempo necesario para cargar la tabla desde el disco
3. CEl número de elementos almacenados dividido entre el número de cubetas
4. DEl número de colisiones producidas hasta ahora

¿Qué es la raíz de un árbol?

1. AEl nodo superior que no tiene padre
2. BUn nodo sin hijos
3. CCualquier nodo intermedio
4. DEl nodo con el valor más grande

Una aplicación necesita búsquedas rápidas y además listar las claves en orden y responder consultas por rangos. ¿Qué estructura encaja mejor?

1. AUna tabla hash
2. BUna lista enlazada sin ordenar
3. CUna pila
4. DUn árbol binario de búsqueda balanceado

¿Qué tipo abstracto de datos usa el algoritmo de Dijkstra para elegir el siguiente vértice que procesar?

1. AUn conjunto sin orden
2. BUna cola de prioridad de mínimos
3. CUna cola FIFO
4. DUna pila

Un nodo de un árbol binario de búsqueda tiene subárbol derecho. ¿Dónde está su sucesor en orden?

1. AEn el nodo situado más a la izquierda de su subárbol derecho
2. BSiempre en su hijo derecho
3. CEn el nodo situado más a la derecha de su subárbol izquierdo
4. DSiempre en su padre

Un objeto se almacena como clave en un mapa hash y después se modifica un campo que usa su función hash. ¿Cuál es el resultado probable?

1. ANo cambia nada, porque el hash de una clave se calcula una sola vez al iniciar el programa
2. BLa búsqueda del objeto puede fallar porque está en la cubeta de su hash antiguo
3. CEl mapa lanza un error en el momento en que cambia el campo
4. DEl mapa mueve automáticamente la clave a su nueva cubeta

La estructura union-find (conjuntos disjuntos) con unión por rango y compresión de caminos tiene un coste amortizado por operación de:

1. AO(n)
2. BO(n²)
3. CExactamente O(log n)
4. DO(α(n)), la inversa de la función de Ackermann, que en la práctica es constante