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 hallar el valor más grande de un array no ordenado de n números?

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

¿Qué algoritmo de ordenación intercambia repetidamente elementos adyacentes que están en el orden incorrecto?

1. AQuicksort
2. BOrdenamiento por montículos (heap sort)
3. COrdenamiento de burbuja (bubble sort)
4. DOrdenamiento por mezcla (merge sort)

La programación dinámica es útil cuando un problema tiene:

1. ASubproblemas superpuestos y subestructura óptima
2. BSolo entradas aleatorias
3. CNingún subproblema en absoluto, así que puede resolverse en un solo paso
4. DUn único bucle

¿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(1)
2. BO(n)
3. CO(n²)
4. DO(log n)

¿Cuánto espacio de pila usa una función factorial recursiva sencilla fact(n) = n × fact(n − 1)?

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

La ordenación topológica solo es posible en:

1. AGrafos no dirigidos
2. BGrafos completos
3. CGrafos dirigidos acíclicos (DAG)
4. DGrafos con pesos negativos

¿Qué estableció el teorema de Cook-Levin?

1. AP no es igual a NP
2. BTodo problema NP puede resolverse en tiempo exponencial
3. CEl problema de satisfacibilidad booleana (SAT) es NP-completo
4. DEl problema de la parada es indecidible