Hoja de ejercicios de Estructuras de datos con soluciones

En una lista simplemente enlazada, ¿qué contiene el puntero al siguiente del último nodo?

1. ALa dirección del nodo anterior
2. BEl número de nodos de la lista
3. CNull (ningún nodo)
4. DLa dirección del primer nodo

En un árbol binario de búsqueda, los valores del subárbol izquierdo de un nodo son:

1. AMayores que el valor del nodo
2. BDe orden aleatorio
3. CIguales al valor del nodo
4. DMenores que el valor del nodo

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. CNodos que tienen el mismo padre
4. DUn nodo y su padre

¿Cuánto se tarda en comprobar si existe la arista (u, v) con una matriz de adyacencia?

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

¿Cuál es el coste de insertar un elemento en medio de un arreglo de n elementos?

1. AO(n²), porque cada elemento se mueve n veces
2. BO(log n), por la búsqueda binaria
3. CO(n), porque los elementos posteriores deben desplazarse
4. DO(1), porque se conoce el índice

¿Cuánta memoria usa una lista de adyacencia para un grafo con V vértices y E aristas?

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

Al insertar una clave en un árbol AVL, el subárbol izquierdo de un nodo queda demasiado alto, y la nueva clave fue al subárbol izquierdo de su hijo izquierdo (caso izquierda-izquierda). ¿Qué corrección se aplica?

1. ARecolorear el nodo y su hijo
2. BUna rotación a la izquierda en el hijo y luego una rotación a la derecha en el nodo
3. CUna rotación simple a la derecha en el nodo desequilibrado
4. DUna rotación simple a la izquierda en el nodo desequilibrado

Bajo el supuesto de hashing uniforme simple, ¿cuál es el tiempo esperado de una búsqueda en una tabla hash con encadenamiento, n claves y m cubetas?

1. AO(log n)
2. BO(n)
3. CO(1 + α), donde α = n / m
4. DO(m)