Parcial 1 Algoritmia 2018

56 Questions | Total Attempts: 21

SettingsSettingsSettings
Please wait...
Parcial 1 Algoritmia 2018

.


Questions and Answers
  • 1. 
    Un algoritmo recursivo basado en el esquema divide y vencerás ...
    • A. 

      Será más eficioente cuanto más equitativa sea la división en subproblemas

    • B. 

      Las demás opciones son verdaderas

    • C. 

      Nunca tnedrá una complejidad exponencial

  • 2. 
    Indicad cuál de estas tres expresiones es falsa:
    • A. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

  • 3. 
    ¿Cuál de estas tres expresiones es falsa?
    • A. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

  • 4. 
    Indica cuál es la complejidad en el peor caso de la función replace
    • A. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

  • 5. 
    ¿Cuál es la complejidad temporal de la siguiente función recursiva?
    • A. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

  • 6. 
    Sea f(n) la solución de la relación  de recurrencia f(n)=2f(n/2)+1;f(1)=1. Indicad cuál de estas tres expresiones es cierta:
    • A. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

  • 7. 
    Considerad estos dos fragmentos:
    • A. 

      El coste temporal asintótico del primer programa en el caso peor es más alto que en el segundo.

    • B. 

      El coste temporal asintótico, tanto en el caso mejor como en el peor, de los dos programas es el mismo.

    • C. 

      El coste temporal asintótico del segundo programa en el caso peor es más alto que el primero

  • 8. 
    Indica cuál es la complejidad, en función de n, del fragmento siguiente:
    • A. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

  • 9. 
    Indica cuál es la complejidad en función de n, donde k es una constante (no depende de n), del fragmento siguiente:
    • A. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

  • 10. 
    Pertenece 3n2+3 a O(n3)?
    • A. 

      Solo para c=1 y nO=5

    • B. 

      No

    • C. 

  • 11. 
    La complejidad temporal en el mejor de los casos...
    • A. 

      Las demás opciones son verdaderas

    • B. 

      ...es el tiempo que tarda el algoritmo en resolver la talla más pequeña que se le puede presentar

    • C. 

      ...es una función de la talla que tiene que estar definida para todos los posibles valores de ésta.

  • 12. 
    La versión de Quicksort que utiliza como pivote la mediana del vector...
    • A. 

      ...se comporta mejor cuando el vector ya está ordenado

    • B. 

      ...se comporta peor cuando el vector ya está ordenado

    • C. 

      ...El hecho de que el vector estuviera previamente ordenado o no, no influye en la complejidad temporal de este algoritmo.

  • 13. 
    Dada la siguiente relación de recurrencia, ¿Qué cota es verdadera?
    • A. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

  • 14. 
    Un problema de tamaño n puede transformarse en tiempo O(n2) en nueve de tamaño n/3; por otro lado, la solución al problema cuando la talla es 1 requiere un tiempo constante. ¿Cuál de estas clases de coste temporal asintótico es la más ajustada?
    • A. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

  • 15. 
    Indica cuál es la complejidad, en función de n, del siguiente fragmento de código:
    • A. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

  • 16. 
    Sea f(n) la solución de la relación de recurrencia f(n)=2f(n-1)+1. f(n)=1. Indicad cuál de estas tres expresiones es cierta:
    • A. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

  • 17. 
    Un programa con dos bucles anidados uno dentro del otro, El primero hace n iteraciones aproximadamente y el segundo la mitad, tarda un tiempo Seleccione una:
    • A. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

  • 18. 
    ¿Cuál es la complejidad temporal de la siguiente función recursiva?
    • A. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

  • 19. 
    Los algoritmos de ordenación Quicksort y Mergesort tienen en común...
    • A. 

      ...que se ejecuta en tiempo O(n)

    • B. 

      ...que ordenan el vector sin usar espacio adicional

    • C. 

      ...que aplican la estrategia de divide y vencerás

  • 20. 
    Indica cuál es la complejidad de la función siguiente:
    • A. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

  • 21. 
    Indicad cuál de estas tres expresiones es falsa:
    • A. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

  • 22. 
    ¿Cuál de estos tres problemas de optimización no tiene, o no se le conoce, una solución voraz óptima?
    • A. 

      El árbol de cobertura de coste mínimo de un grafo conexo

    • B. 

      El problema de la mochila discreta o sin fraccionamiento

    • C. 

      El problema de la mochila continua o con fraccionamiento

  • 23. 
    Los algoritmos de programación dinámica hacen uso...
    • A. 

      ..de que la solución óptima se puede construir añadiendo a la solución el elemento óptimo de los elementos restantes, uno a uno

    • B. 

      ...de que se puede ahorrar cálculos guardando resultados anteriores en un almacén

    • C. 

      ...de una estrategia trivial consistente en examinar todas las soluciones posibles

  • 24. 
    Which one do you like?
    • A. 

      La recursión puede ser infinita y por tanto es necesario organizarla según el esquema iterativo de programación dinámica

    • B. 

      Se repiten muchos cálculo y ello se puede evitar haciendo uso de una estrategia voraz

    • C. 

      Se repiten muchos cálculos y ello se puede evitar usando programación dinámica

  • 25. 
    Sea f(n) la solución de la relación de recurrencia f(n)=2f(n/2)+n:f(1)=1. Seleccione una
    • A. 

      Option 1

    • B. 

      Option 2

    • C. 

      Option 3

Back to Top Back to top