Hoja de ejercicios de Estructuras de datos con soluciones

¿Qué hace la operación peek (o top) en una pila?

1. ADevuelve el elemento del fondo de la pila
2. BElimina todos los elementos de la pila
3. CElimina el elemento de la cima y lo devuelve
4. DDevuelve el elemento de la cima sin eliminarlo

En la representación de un grafo mediante listas de adyacencia, ¿qué se almacena para cada vértice?

1. AUna fila de V valores booleanos
2. BEl camino más corto a todos los demás vértices
3. CEl número total de aristas del grafo
4. DUna lista de sus vértices vecinos

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

1. AEl número de colisiones producidas hasta ahora
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 cubetas dividido entre la longitud media de las claves almacenadas

¿Cuánto tarda la búsqueda de una palabra de longitud L en un trie con un alfabeto fijo?

1. AO(n), donde n es el número de palabras
2. BO(log n), donde n es el número de palabras
3. CO(L), independientemente de cuántas palabras haya almacenadas
4. DO(L × n)

Un árbol binario tiene la raíz 1 con hijo izquierdo 2 e hijo derecho 3; el nodo 2 tiene los hijos 4 (izquierdo) y 5 (derecho). ¿Cuál es el recorrido en preorden?

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C1 2 3 4 5
4. D4 5 2 3 1

En una cola circular almacenada en un arreglo de capacidad n, ¿cómo se calcula la posición siguiente al índice i?

1. A2i + 1
2. Bi + 1
3. C(i + 1) mod n
4. D(i − 1) mod n

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(m)
4. DO(1 + α), donde α = n / m

¿Cuál es el tiempo de ejecución de la búsqueda en anchura en un grafo con V vértices almacenado como matriz de adyacencia?

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