Metoda Backtracking

18 Questions | Total Attempts: 1187

SettingsSettingsSettings
Please wait...
Metoda Backtracking

Se adreseaza elevilor de clasa a XI, profil matematica informatica, intensiv informatica sau pentru pregatirea examenului de bacalaureat, disciplina informatica


Questions and Answers
  • 1. 
    Un algoritm de tip backtracking genereaza in ordine lexicografica, toate sirurile de 5 cifre 0 si 1 cu proprietatea ca nu exista mai mult de doua cifre de 0 consecutive. Primele sase solutii generate sunt: 00100, 00101, 00110, 00111, 01001, 01010. Care este cea de-a opta solutie?
    • A. 

      01110

    • B. 

      01100

    • C. 

      01011

    • D. 

      01101

  • 2. 
    Un algoritm backtracking genereaza toate sirurile alcatuite din cate 6 cifre binare (0 si 1). Numarul tuturor solutiilor generate va fi egal cu :
    • A. 

      64

    • B. 

      32

    • C. 

      16

    • D. 

      12

  • 3. 
    Aplicand metoda backtracking pentru a genera toate permutarile celor n elemente ale unei multimi, o solutie se memoreaza sub forma unui tablou unidimensional x1, x2, ..., xn. Daca sunt deja generate valori pentru componentele x1, x2, ..., xk-1, iar pentru componenta xk (1 <k<n) au fost testate toate valorile posibile si nu a fost gasita niciuna convenabila, atunci:
    • A. 

      Se incearca alegerea unei valori pentru componenta xk-1.

    • B. 

      se incearca alegerea unei noi valori pentru componenta x1, oricare ar fi valoarea k.

    • C. 

      se incheie algoritmul.

    • D. 

      Se incearca alegerea unei valori pentru componenta xk+1.

  • 4. 
    Daca se utilizeaza metoda backtracking pentru a genera toate numerele naturale, in ordine strict crescatoare, formate din 4 cifre pare distincte, care dintre numerele de mai jos trebuie, eliminate astfel incat cele ramase sa reprezinte o succesiune de numere corect generate? 1) 2068; 2) 2084; 3) 2088; 4) 2468; 5) 2086; 6) 2406
    • A. 

      numai 3)

    • B. 

      atat 3) cat si 5)

    • C. 

      Atat 3) cat si 4)

    • D. 

      numai 4)

  • 5. 
    Se considera multimea {1, 7, 5, 16, 12}. Se genereaza prin metoda backtracking toate submultimile sale formate din exact 3 elemente: primele patru solutii generate sunt, in ordine: {1, 7, 5}, {1, 7, 16}, {1, 7, 12}. Care dintre solutii trebuie eliminate din sirul urmator astfel incat cele ramase sa apara in sir in ordinea generarii lor: {1, 16, 12}, {5, 16, 12}, {7, 5, 16}, {7, 5, 12}
    • A. 

      {1, 16, 12}

    • B. 

      {5, 16, 12}

    • C. 

      {7, 5, 16}

    • D. 

      {7, 5, 12}

  • 6. 
    Se considera algoritmul care genereaza in ordine strict crescatoare toate numerele formate cu 5 cifre distincte alese din multimea {1, 0, 5, 7, 9} in care cifra din mijloc este 0.Selectati numarul care precede si numarul care urmeaza secventei de numere generate: 19075; 51079; 51097
    • A. 

      19057, 57019

    • B. 

      15079, 71059

    • C. 

      19057, 59071

    • D. 

      15097, 71095

  • 7. 
    Daca pentru generarea tuturor submultimilor unei multimi A = {1, 2, ..., n} cu 1 ≤ n ≤ 10, se utilizeaza un algoritm backtracking astfel incat se afiseaza in ordine, pentru n=3, submultimile {}, {1}, {2}, {3},{1, 2}, {1,3}, {2,3}, {1, 2, 3}, atunci, utilizand exact acelasi algoritm pentr n = 4, in sirul submultimilor generate, solutia a 7-a va fi:
    • A. 

      {1,3}

    • B. 

      {4}

    • C. 

      {1,2,3}

    • D. 

      {1,4}

  • 8. 
    Produsul cartezia {1,2,3}x{2,3} este obtinut cu ajutorul unui algoritm backtracking care genereaza perechile (1,2), (1,3), (2,2), (2,3), (3,2) si (3,3). Care este numarul perechilor obtinute prin utilizarea aceluiasi algoritm la generarea produsului cartezian {1, 2, 3, 4, 5}x{a, b, c, d}?
    • A. 

      9

    • B. 

      20

    • C. 

      10

    • D. 

      6

  • 9. 
    Se genereaza toate sirurile strict crescatoare de numere naturale nenule mai mici sau egale cu 4, avand primul termen 1 sau 2, ultimul termen 4 si cu diferenta dintre oricare doi termeni aflati pe pozitii consecutive cel mult 2, obtinandu-se solutiile (1, 2, 3,4), (1, 2, 4), (1, 3, 4), (2, 3, 4), (2, 4). Folosind aceeasi metoda generam toate sirurile strict crescatoare de numere naturale nenule mai mic sau egale cu 6, avand primul termen 1 sau 2, ultimul termen 6 si diferenta dintre oricare doi termeni aflati pe pozitii consecutive cel mult 2, care dintre afirmatiile urmatoare este adevarata:
    • A. 

      Imediat dupa solutia (1, 3, 4, 5, 6) se genereaza solutia (2, 3, 4, 5, 6)

    • B. 

      Penultima solutie generata este (2, 3, 5, 6)

    • C. 

      Imediat dupa solutia (1, 2, 4, 6) se genereaza solutia (1, 3, 4, 6)

    • D. 

      In total sunt generate 13 solutii.

  • 10. 
    Avand la dispozitie cifrele 0, 1 si 2 putem genera, in ordine crescatoare, numerele care au suma cifrelor egala cu 2 astfel: 2, 11, 20, 101, 110, 200, etc. Folosind acest algoritm generati numerele cu cifrele 0, 1 si 2 care au suma cifrelor egala cu 3. Care va fi al saptelea numar din aceasta generare?
    • A. 

      120

    • B. 

      1002

    • C. 

      201

    • D. 

      210

  • 11. 
    Generarea tuturor cuvintelor de 4 litere, fiecare litera putand fi orice element din multimea {a, c, e, m, v, s}, se realizeaza cu ajutorul unui algoritm echivalent cu algoritmul de generare a:
    • A. 

      Produsului cartezian

    • B. 

      Combinarilor

    • C. 

      Partitiilor unei multimi

    • D. 

      Permutarilor

  • 12. 
    Folosind un algoritm de generare putem obtine numere naturale de k cifre care au suma cifrelor egala cu un numar natural s introdus de la tastatura, unde s si k sunt numere naturale nenule. Astfel pentru valorile k = 2 si s = 6 se genereaza numerele: 15, 24, 33, 42, 51, 60. Care vor fi primele 4 numere ce se vor genera pentru k = 3 si s=8?
    • A. 

      800, 710, 620, 530

    • B. 

      107, 116, 125, 134

    • C. 

      125, 233, 341, 431

    • D. 

      116, 125, 134, 143

  • 13. 
    Se considera multimile A = {1, 2, 3}, B = {1}, C = {2, 3, 4}. Elementele produsului cartezian AxBxC se genereaza, in ordine astfel: (1, 1, 2), (1, 1, 3), (1, 1, 4), (2, 1, 2), (2, 1, 3), (2, 1, 4), (3, 1, 2), (3, 1, 3), (3, 1, 4). Daca prin acelasi algoritm se genereaza produsul cartezian al multimilor AxBxC, unde A ={a, b}, B ={a}, C = {b, c, d}, atunci cel de-al cincilea element generat este:
    • A. 

      (a, a, d)

    • B. 

      (a, a, c)

    • C. 

      (b, a, b)

    • D. 

      (b, a, c)

  • 14. 
    Pentru a determina toate modalitatile de a scrie numarul 8 ca suma de numere naturale nenule distincte (abstractie facand de ordinea termenilor) se foloseste metoda backtracking obtinandu-se, in ordine, toate solutiile 1+2+5, 1+3+4, 1+7, 2+6, 3+5. Aplicand exact acelasi procedeu, se determina solutiile pentru scrierea numarului 10. Cate solutii de forma 1+ ... exista?
    • A. 

      3

    • B. 

      4

    • C. 

      5

    • D. 

      6

  • 15. 
    Se considera multimile A = {1, 2, 3}, B = {1}, C = {2, 3, 4}. Elementele produsului cartezian AxBxC se genereaza, folosind metoda backtracking, in ordinea (1, 1, 2), (1, 1, 3), (1, 1, 4), (2, 1, 2), (2, 1, 3), (2, 1, 4), (3, 1, 2), (3, 1, 3), (3, 1, 4). Daca prin acelasi algoritm se genereaza produsul cartezian al multimilor AxBxC unde A = {x, y}, B = {x, u}, c = {x, y, z}, atunci cel de-al saptelea element generat este:
    • A. 

      (y, u, x)

    • B. 

      (y, x, x)

    • C. 

      (y, x, z)

    • D. 

      (y, y, z)

  • 16. 
    Generarea tuturor sirurilor formate din trei elemente, fiecare element putand fi oricare numar din multimea {1, 2, 3}, se realizeaza cu ajutorul unui algoritm echivalent cu algoritmul de generare a:
    • A. 

      Permutarilor

    • B. 

      Combinarilor

    • C. 

      Produsului cartezian

    • D. 

      Aranjamentelor

  • 17. 
    In utilizarea metodei backtracking pentru a genera toate cuvintele alcatuite din doua litere ale multimii {a, c, e, q}, astfel incat sa nu existe doua consoane alaturate, cuvintele se genereaza in urmatoarea ordine: aa, ac, ae, aq, ca, ce, ea, ec, ee, eq, qa, qe. Daca se utilizeaza exact aceeasi metoda pentru a genera cuvinte formate din 4 litere ale multimii {a, b, c, d, e, f}, astfel incat sa nu existe doua consoane alaturate in cuvant, care este penultimul cuvant generat?
    • A. 

      Fefa

    • B. 

      Fafe

    • C. 

      Feef

    • D. 

      Fefe

  • 18. 
    Utilizand metoda backtracking se genereaza toate numerele formate doar din trei cifre astfel incat fiecare numar sa aiba cifrele distincte. Cifrele fiecarui numar sunt din multimea {12, 2, 3, 4}. acest algoritm genereaza numerele, in aceasta ordine: 123, 124, 132, 134, 213, 214, 231, 234, 312, 314, 321, 324, 412, b413, 421, 423, 431, 432. Daca utilizam acelasi algoritm pentru a genera toate numerele de 4cifre, fiecare numar fiind format din cifre distincte din multimea {1, 2, 3, 4, 5}, precizati care este numarul generat imedia dupa 4325.
    • A. 

      4351

    • B. 

      5123

    • C. 

      4521

    • D. 

      4321

Back to Top Back to top