Hoja de ejercicios de Algoritmos y complejidad con soluciones

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

1. AFuerza bruta
2. BProgramación dinámica
3. CElección voraz
4. DDivide y vencerás

¿Qué es la recursión?

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

¿Qué algoritmo de ordenación elige un pivote y divide el array en elementos menores y mayores?

1. AOrdenamiento por inserción
2. BQuicksort
3. CMerge sort
4. DOrdenamiento de burbuja

La búsqueda en anchura (BFS) en un grafo no ponderado encuentra:

1. AEl árbol de expansión mínima
2. BLos caminos más cortos en grafos que contienen aristas con pesos negativos
3. CLos caminos más cortos en número de aristas desde el nodo inicial
4. DUn orden topológico en todos los grafos

¿Qué afirmación sobre una función recursiva sin un caso base alcanzable es correcta?

1. ASe ejecuta en tiempo O(1)
2. BSigue llamándose a sí misma hasta que se desborda la pila de llamadas
3. CDevuelve 0 automáticamente
4. DEl compilador siempre la convierte en un bucle que termina sin problemas

Un quicksort usa siempre el primer elemento como pivote. ¿Con qué entrada muestra su comportamiento de peor caso?

1. AUn array que ya está ordenado
2. BUn array con todos sus elementos distintos
3. CUn array en orden aleatorio
4. DUn array de longitud 2

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. AW es un número, así que el tiempo es exponencial en el número de bits empleados para escribir W
2. BPorque el algoritmo es aleatorizado y su tiempo de ejecución varía con cada entrada
3. CPorque n siempre es pequeño
4. DPorque solo funciona para W = 0

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. AEs NP-difícil
2. BSiempre puede resolverse en O(V + E)
3. CEs indecidible
4. DPuede resolverse con el algoritmo de Dijkstra con los pesos cambiados de signo