Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué es la recursión?

1. AUn método de ordenación
2. BUna función que se llama a sí misma con entradas más pequeñas
3. CUn bucle que nunca termina
4. DUn tipo de estructura de datos

¿Cuáles son los tres pasos de un algoritmo de divide y vencerás?

1. ADividir, vencer, combinar
2. BAdivinar, comprobar, repetir
3. COrdenar, buscar, devolver
4. DLeer, calcular, escribir

¿Cuál es la complejidad temporal en el peor caso del ordenamiento por mezcla (merge sort)?

1. AO(n log n)
2. BO(n)
3. CO(n²)
4. DO(log n)

¿Cómo construye el algoritmo de Prim un árbol de expansión mínima?

1. AEjecuta una búsqueda en anchura y se queda con el árbol BFS
2. BElimina la arista más cara hasta que no quedan ciclos
3. COrdena todas las aristas por peso y añade cada una salvo que forme un ciclo en el bosque
4. DHace crecer un único árbol desde un vértice inicial, añadiendo la arista más barata que sale del árbol

¿Cuál es la complejidad temporal del algoritmo de Bellman-Ford en un grafo con V vértices y E aristas?

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

¿Qué algoritmo de ordenación es estable?

1. AQuicksort (versión in situ habitual)
2. BHeap sort
3. COrdenamiento por selección (versión habitual)
4. DMerge sort

Un problema es NP-completo si:

1. AEstá fuera de NP pero es más difícil que todos los problemas NP, como el problema de la parada
2. BSe puede resolver en tiempo polinómico
3. CEs imposible de resolver
4. DEstá en NP y todo problema NP se reduce a él en tiempo polinómico

¿Qué cota es correcta para log(n!)?

1. AΘ(log n)
2. BΘ(n)
3. CΘ(n log n)
4. DΘ(n²)