Estructuras de datos y algoritmos: problemas de práctica y preguntas de examen

Notación O grande, el tiempo de ejecución de los algoritmos habituales y las ventajas e inconvenientes de arrays, listas enlazadas, árboles, tablas hash y grafos.

Practica esta asignatura gratisPracticar esta asignaturaHacer un simulacro de examen5 problemas gratis cada día. Sin tarjeta.

Pack de repaso (PDF)Hojas de fórmulas, pasos de los métodos y problemas de práctica con soluciones completas, listos para imprimir.

Temas de esta asignatura

  1. Algoritmos y complejidadtérminos y datos clave · aplicar los conceptos · casos y análisisopción múltiple
  2. Estructuras de datostérminos y datos clave · aplicar los conceptos · casos y análisisopción múltiple
  3. Teoría de grafosgrados y aristas · caminos eulerianos y árboles · caminos mínimos y árboles generadorescálculos

Consejos para el examen de Estructuras de datos y algoritmos

  • En bucles anidados, multiplica el número de iteraciones; en bucles consecutivos, quédate con el término mayor.
  • Conoce el coste de búsqueda, inserción y borrado de cada estructura de datos.
  • Reducir la entrada a la mitad en cada paso da un tiempo logarítmico.

Ejemplos resueltos

Algoritmos y complejidadFácil

¿Qué notación describe una cota superior del crecimiento?

  1. AOmega grande (Big Omega)
  2. BOmega pequeña (little omega)
  3. CO grande (Big O)
  4. DTheta grande (Big Theta)
Mostrar pistas
  1. «Como mucho».
  2. Ahora hay dos respuestas incorrectas tachadas. Una de las dos que quedan es la correcta.
Mostrar la respuesta y la explicación

Por qué esta es la respuesta

O da una cota superior, Ω una cota inferior y Θ una cota ajustada.

Respuesta

C · O grande (Big O)
Estructuras de datosMedia

¿Cómo funciona extract-min en un min-heap binario?

  1. ASe elimina el último elemento del arreglo
  2. BSe mueve el último elemento a la raíz y se hace bajar (sift-down)
  3. CSe elimina la raíz y se desplazan todos los elementos una posición a la izquierda
  4. DSe buscan en todas las hojas el nuevo mínimo
Mostrar pistas
  1. Mantén el árbol completo y luego corrige el orden.
  2. Ahora hay dos respuestas incorrectas tachadas. Una de las dos que quedan es la correcta.
Mostrar la respuesta y la explicación

Por qué esta es la respuesta

El último elemento ocupa el hueco de la raíz y se intercambia con su hijo menor hasta que se cumple la propiedad de montículo, lo que cuesta O(log n).

Respuesta

B · Se mueve el último elemento a la raíz y se hace bajar (sift-down)

Cómo funciona la práctica

  • «Practicar esta asignatura» mezcla problemas de todos sus temas, como en un examen real.
  • Cada problema tiene valores nuevos, así aprendes el método y no una respuesta.
  • ¿Te has atascado? Abre primero una pista pequeña y la explicación completa solo cuando la necesites.
  • Los simulacros de examen son cronometrados y no tienen pistas; al final recibes tu nota y una revisión completa.

Asignaturas relacionadas

Fundamentos de informáticaMatemática discretaRedes de computadores
Practica esta asignatura gratisPracticar esta asignaturaHacer un simulacro de examen5 problemas gratis cada día. Sin tarjeta.