Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué es la memoización?

1. AEscribir comentarios junto a cada línea de código
2. BGuardar los resultados de las llamadas a funciones para responder desde memoria a las llamadas repetidas
3. CConvertir automáticamente la recursión en un bucle equivalente para que no haga falta pila de llamadas
4. DLiberar memoria cuando una función termina

¿Cuál es la complejidad temporal de la búsqueda lineal en un array no ordenado de n elementos (peor caso)?

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

¿Qué estrategia de diseño usa merge sort?

1. ADivide y vencerás
2. BFuerza bruta
3. CElección voraz
4. DProgramación dinámica

¿Por qué suele omitirse la base del logaritmo en la notación O grande, como en O(log n)?

1. ALos logaritmos siempre se redondean a enteros
2. BLa base solo importa para n pequeño
3. CLos logaritmos en distintas bases solo difieren en un factor constante
4. DTodos los logaritmos en informática tienen base 10, así que va implícita

¿Cuál es la complejidad temporal amortizada de añadir al final de un array dinámico que duplica su capacidad cuando está lleno?

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

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

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

Los caminos simples más cortos pueden hallarse en tiempo polinómico. ¿Qué se sabe de hallar el camino simple más largo entre dos vértices en un grafo general?

1. ASiempre puede resolverse en O(V + E)
2. BEs NP-difícil
3. CEs indecidible
4. DPuede resolverse con el algoritmo de Dijkstra con los pesos cambiados de signo

¿Qué afirmación sobre la notación o pequeña es correcta?

1. A2n = o(n), porque 2n crece despacio
2. Bn = o(n²), pero n no es o(n)
3. Cn² = o(n)
4. Dn = o(n), porque toda función es o pequeña de sí misma