Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Cuánto vale log₂ 1024?

1. A10
2. B512
3. C32
4. D12

¿Qué es la memoización?

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

¿Cuál es la complejidad temporal de la búsqueda binaria en un array ordenado?

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

¿Cuál es el tiempo de ejecución del radix sort LSD sobre n enteros de d dígitos en base k?

1. AO(n²)
2. BO(d(n + k))
3. CO(dn log k)
4. DO(n log n)

¿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(n)
4. DO(1)

¿Qué algoritmo de ordenación es estable?

1. AOrdenamiento por selección (versión habitual)
2. BQuicksort (versión in situ habitual)
3. CHeap sort
4. DMerge sort

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

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

El problema de la mochila 0/1 resuelto con programación dinámica requiere un tiempo O(nW). ¿Por qué se llama pseudopolinómico?

1. APorque n siempre es pequeño
2. BPorque el algoritmo es aleatorizado y su tiempo de ejecución varía con cada entrada
3. CPorque solo funciona para W = 0
4. DW es un número, así que el tiempo es exponencial en el número de bits empleados para escribir W