WorksheetsEXTRAORDINARIO DE ALGORITMIA Y ESTRUCTURA DE DATOS II
Total questions: 20
Worksheet time: 10mins
Nombre completo
¿Cuál es la suma de las primeras 3 aristas seleccionadas por el algoritmo de Prim al aplicarlo al siguiente grafo, tomando el vértice z como raíz del árbol?
14
11
8
¿El algoritmo de Prim siempre selecciona todas las aristas de menor costo del grafo para construir el árbol abarcador mínimo?
SI
No
El problema del viajante puede resolverse correctamente planteando estos esquemas de programación:
Sólo programación dinámica
Empleando cualquiera de estos: Voraz y Backtracking
Sólo Backtracking
El siguiente problema tiene una solución óptima empleando:
Backtracking
Algoritmos voraces
Ambos
Si aplicamos un esquema de backtracking que nos garantice la solución óptima sobre un problema, entonces
Obtendremos una solución factible
Puede que no encuentre ninguna solución aunque esta exista
Ninguna de las anteriores
El backtracking se emplea en la resolución de problemas de optimización en los que se pretende encontrar:
Todas las soluciones que satisfagan unas restricciones.
Una solución que satisfaga unas restricciones y optimice una cierta función objetivo.
Ambas son correctas.
En el método voraz, aunque las decisiones son irreversibles, se puede asegurar que:
Siempre obtendremos la solución óptima
Siempre se obtiene una solución factible
Sólo se obtiene la solución óptima para algunos problemas
¿A qué se refiere el método divide y vencerás?
A descomponer en subproblemas un problema dado
A dar soluciones que satisfagan todas las restricciones propuestas.
A construir un problema con partes
El resultado de aplicar el algoritmo de Prim al grafo de la Figura 1 es el árbol abarcador mínimo mostrado en la Figura 2.
SI
NO
¿Cuál es la principal diferencia entre el algoritmo de Prim y el de Kruskal al construir un árbol abarcador mínimo?
Kruskal siempre elige la arista de mayor peso.
Prim comienza desde un vértice y Kruskal desde una arista.
Prim solo funciona en grafos dirigidos.
¿Qué característica define a los algoritmos voraces en la resolución de problemas de optimización?
Evalúan todas las posibles soluciones antes de decidir.
Toman decisiones basadas en la mejor opción local en cada paso.
Siempre requieren retroceder para corregir decisiones.
¿Para qué tipo de problemas es más adecuado emplear el método de backtracking?
Problemas donde se busca una única solución óptima sin restricciones
Problemas con múltiples restricciones y necesidad de explorar varias alternativas
Problemas que solo requieren una solución aproximada
¿Cuál de los siguientes métodos es el más eficiente para encontrar el árbol abarcador mínimo en un grafo denso?
Backtracking
Algoritmo de Kruskal
Algoritmo de Prim
¿Qué técnica de programación se utiliza comúnmente para resolver el problema del viajante cuando el número de ciudades es pequeño?
Programación dinámica
Divide y vencerás
Voraz
¿En qué situación el método voraz puede no encontrar una solución óptima?
Cuando existen restricciones que afectan el resultado final
Cuando todas las decisiones locales conducen a la solución global
Cuando el problema es de tipo árbol abarcador mínimo
¿Cuál de los siguientes problemas se resuelve óptimamente utilizando un algoritmo voraz?
El problema de la mochila fraccionaria
El problema del viajante
El problema de las N reinas
¿Qué sucede si en el algoritmo de Kruskal se agregan aristas que forman un ciclo?
No afecta el resultado final
Se viola la propiedad de árbol y el resultado no es correcto
El árbol abarcador mínimo sigue siendo válido
¿Cuál es la principal ventaja de la programación dinámica sobre el método voraz?
Siempre utiliza menos memoria
Permite encontrar soluciones aproximadas rápidamente
Puede resolver problemas con subestructuras superpuestas y decisiones dependientes
¿Cuál de los siguientes algoritmos es más adecuado para encontrar el camino más corto entre dos nodos en un grafo ponderado?
Algoritmo de Dijkstra
Algoritmo de Kruskal
Algoritmo de Prim
