¡GoConqr estrena diseño! Cuéntanos qué te parece.

Regístrate gratis

Test

Backtracking

Vicente García D 12 preguntas

Hacer el test

Este test tiene tipos de pregunta que se abren en el reproductor de siempre.

Preguntas del test (12)

  1. 1If you need to solve a problem and you know how to solve it using a dynamic programming algorithm, but you also know how to solve it using a bakctracking-based algorithm, which one you should usually use?
    1. ANeither
    2. BDynamic programming
    3. CBacktracking
  2. 2For the Magic Square problem, with a size of n=3, how many ways to arrange the n^2 numbers are there using brute force?
    1. A3
    2. B9
    3. C362880
    4. D81
    5. E27
    6. Fabout 1000
  3. 3Many problems can be represented as abstract graphs. Nodes usually represent valid changes and edges usually represent the state of the problem. Thus, to solve the problem we must find a node or a path in the associated graph

    1. AVerdadero
    2. BFalso
  4. 4The implicit graph used for backtracking is usually depicted as a tree, called [blank_start]tree of states[blank_end].
    With the technique of backtracking we perform a [blank_start]depth-first[blank_end] search of the tree.
    The objective is to find the nodes (states) that are [blank_start]solutions[blank_end] to the problem.
    To that end, a exhaustive and systematic [blank_start]search[blank_end] in the solution space of the problem is performed
    1. Atree of states
    2. Bdepth-first
    3. Csolutions
    4. Dsearch
  5. 5There are usually two versions of backtracking algorithms. There can be:
    - "first solution" if we only need a solution to the problem
    - "all the solutions" if we need all the solutions, the best or the worst solution
    1. AVerdadero
    2. BFalso
  6. 6Indicate which ones can be usually complexities when working with backatracking
    1. AO(2^n)
    2. BO(4^n)
    3. CO(n^2)
    4. DO(n)
    5. EO(nlogn)
    6. FO(n!)
  7. 7Which complexity is the worst?
    1. AO(n!)
    2. BO(n^n)
    3. CO(10^n)
  8. 8The memory consumption with backtracking depends on the height of the tree of calls and the waste of stack for each recursive call
    1. AVerdadero
    2. BFalso
  9. 9With backtracking, the height of the tree of states is usually [blank_start]O(logn)[blank_end] when we have a behaviour by division and [blank_start]O(n)[blank_end] when we have a behaviour by substraction
    1. AO(logn)
    2. BO(n!)
    3. CO(n^n)
    4. DO(2^n)
    5. EO(nlogn)
    6. FO(n^2)
    7. GO(n)
    8. HO(1)
  10. 10Permutations using backtrackingImagen de la pregunta 10
    1. Asol[k]
    2. Bsol[i]
    3. Ck
    4. Di
    5. E(int j=0; j<n; j++)
    6. F(int i=0; i<n; i++)
    7. G(int j=0; j<level; j++)
    8. Hsol[level] = v[j];
    9. Isol[level] = v[i];
    10. Jsol[level+1] = v[j];
    11. Ksol[j] = v[level];
    12. Lmark[j] = false;
    13. Mmark[j] = true;
    14. Nmark[level] = false;
    15. Omark[level] = true;

Información

Descripción
Bachelor of Software Engineering - Algorithmics course - University of Oviedo
Idioma
English
Visitas
40
Valoración
Aún sin valoraciones
Valora este test
Valora este test

Escríbenos

¿Sobre qué es tu mensaje?

¿Qué te parece el nuevo diseño?

¿Te gusta?