1.

Iniţializarea componentei x[k] se realizează :

a) Când se trece de pe nivelul k-1 pe nivelul k;
b) Când se trece de pe nivelul k+1 pe nivelul k;
c) Când pe nivelul k+1 au fost testate toate valorile posibile.

2. După găsirea unei soluţii, pasul următor este:

a) Se revine la nivelul anterior;
b) Se rămâne la acelaşi nivel, testându-se următoarea valoare disponibilă;
c) Se încheie algoritmul.

3. Dacă pentru nivelul k oarecare al vectorului soluţie am verificat toate valorile :

a) Algoritmul se încheie;
b) Se revine pe nivelul anterior;
c) Se trece pe nivelul următor.

4. În ce condiţii se revine la componenta anterioară lui k?

a) După ce s-a găsit o valoare pentru componenta k care îndeplineşte condiţiile de continuare;
b) Dacă valoarea testată pentru componenta k nu îndeplineşte condiţiile de continuare;
c) Dacă s-au testat toate valorile posibile pentru componenta k.

5. Algoritmul backtracking se încheie dacă :

a) S-au testat toate valorile posibile pentru ultimul nivel;
b) S-au testat toate valorile posibile pentru primul nivel;
c) Pe un nivel oarecare k nu am găsit nici o valoare care să verifice condiţiile de căutare.

6. Pentru a genera toate numerele naturale cu exact 4 cifre şi care au cifrele în ordine strict
descrescătoare, se poate utiliza un algoritm echivalent cu cel pentru generarea:
a. aranjamentelor de 4 obiecte luate câte 10
b. combinărilor de 10 obiecte luate câte 4
c. permutărilor a 10 obiecte
d. permutărilor a 4 obiecte

7. Utilizând metoda backtracking, se generează toate numerele impare de cel mult trei cifre din
mulţimea {0, 1, 2, 3}. Primele 8 soluţii generate sunt, în această ordine: 1, 101, 103, 11, 111,
113, 121, 123. Cea de a 12-a soluţie generată este:
 a. 13 b. 31 c. 133 d. 201

8. Utilizând metoda backtracking se generează toate grupele de accesorii pentru tenis de câmp din
mulțimea {bentiță, fileu, grip, manșete, mingi, rachetă, racordaj, șapcă}. Accesoriile au
preţurile următoare, exprimate în lei: bentiță - 40, fileu - 400, grip - 30, manșete - 30, mingi
- 10, rachetă - 400, racordaj - 70, șapcă - 60. Într-o grupă accesoriile sunt distincte, nu
contează ordinea lor și costă, în total, exact 500 de lei. Primele trei soluții generate sunt, în această
ordine: (bentiță, fileu, grip, manșete), (bentiță, fileu, șapcă), (bentiță, grip, manșete,
rachetă). A cincea soluție generată este:
a. (bentiță, rachetă, șapcă) b. (fileu, grip, mingi, șapcă)
c. (grip, rachetă, racordaj) d. (manșete, mingi, rachetă, șapcă)

9. Utilizând metoda backtracking se generează toate posibilitățile de a forma șiraguri din câte 4 pietre
prețioase din mulțimea {rubin,opal,safir,smarald,topaz}, astfel încât pe oricare două poziții
alăturate să nu se afle două pietre din submulțimea {rubin,safir,topaz}. Primele opt șiraguri
generate sunt, în această ordine, (rubin,opal,rubin,opal), (rubin,opal,rubin,smarald),
(rubin,opal,opal,rubin), (rubin,opal,opal,opal), (rubin,opal,opal,safir),
(rubin,opal,opal,smarald), (rubin,opal,opal,topaz), (rubin,opal,safir,opal).
Ultimul șirag generat este:
a. (topaz,smarald,topaz,topaz) b. (topaz,smarald,topaz,opal)
c. (topaz,smarald,topaz,smarald) d. (topaz,smarald,smarald,topaz)

10. Utilizând metoda backtracking, se generează toate modalitățile de a pregăti clătite, folosind, într-o
anumită ordine, toate ingredientele din mulțimea {făină, lapte, ouă} pentru aluat, apoi unul dintre
ingredientele din mulțimea {ciocolată, dulceață, urdă} pentru umplutură, și, la final, unul dintre
ingredientele din mulțimea {cașcaval, mărar, frișcă} pentru ornare, având în vedere următoarele
restricții: frișca se poate folosi numai împreună cu ciocolata și dulceața, iar mărarul și cașcavalul numai
împreună cu urda. Primele cinci soluții generate sunt, în această ordine: (făină, lapte, ouă,
ciocolată, frișcă), (făină, lapte, ouă, dulceață, frișcă), (făină, lapte, ouă, urdă,
cașcaval), (făină, lapte, ouă, urdă, mărar), (făină, ouă, lapte, ciocolată, frișcă).
Indicați a șaptea soluție generată.
a. (ouă, lapte, făină, urdă, mărar) b. (lapte, făină, ouă, ciocolată, frișcă)
c. (făină, ouă, lapte, dulceață, frișcă) d. (făină, ouă, lapte, urdă, cașcaval)

11. În câte dintre permutările mulţimii {’L’, ’I’, ’C ’, ’E ’, ’U’} vocala ’E’ apare pe prima poziţie?
12. Daca se construieste, utilizand backtracking, produsul cartezian AxBxC pentru multimile A={1,2,3},
B={1,2} si C={1,2,3,4}, care dintre urmatoarele triplete nu face parte din acest produs?
a. (3,2,1) b) (1,3,2) c) (1,2,3) d) (1,1,1)
13. Utilizând metoda backtracking se generează, în ordine crescătoare, toate numerele de câte 5 cifre, toate
din mulțimea {1,2} cu proprietatea că nu există mai mult de două cifre 1 pe poziţii consecutive. Primele
5 soluţii generate sunt, în această ordine: 11211, 11212, 11221, 11222, 12112. Indicaţi cea de a 8-a
soluţie generată.
a. 12122 b. 12211 c. 12212 d. 12221
14. Utilizând metoda backtracking se generează toate posibilitățile de a forma șiraguri din câte 3 mărgele de
culori distincte din mulțimea {roșu,galben,verde,albastru,violet}. Două șiraguri sunt distincte dacă diferă
prin cel puțin o culoare a mărgelelor sau prin ordinea acestora. Primele patru soluții generate sunt, în
această ordine: (roșu, galben, verde), (roșu, galben, albastru), (roșu, galben, violet), (roșu, verde, galben).
Indicați a zecea soluție generată.

a. (galben,roșu,verde) b. (roșu,albastru,violet) c. (roșu,violet,verde) d. (roșu,violet,galben)

15. Utilizând metoda backtracking, se generează toate numerele impare de cel mult trei cifre din mulţimea
{5, 6, 7, 8}. Primele 8 soluţii generate sunt, în această ordine: 5, 55, 555, 557, 565, 567, 57, 575. Cea de
a 12-a soluţie generată este:

a. 65 b. 67 c. 587 d. 655
16. Un algoritm generează, în ordine lexicografică, toate şirurile alcătuite din câte n cifre binare ( 0 şi 1 ).
Ştiind că pentru n=5 , primele 4 soluţii generate sunt 00000 , 00001 , 00010 , 00011 , precizaţi care sunt
ultimele 3 soluţii generate, în ordinea obţinerii lor.
00000 , 00001 , 00010 , 00011 , 00100, 00101, 00110, 00111, 01000, 01001, 01010, 01011, 01100,
01101, 01110, 01111, 11101, 11110, 11111

17. Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patru litere din
mulţimea A={a,b,c,d,e} , cuvinte care nu conţin două vocale alăturate. Primele opt cuvinte generate sunt,
în ordine: abab , abac , abad , abba , abbb , abbc, abbd ,abbe . Care sunt ultimele cuvinte generate?

18. Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a scrie numărul 9 ca sumă a cel
puţin două numere naturale nenule distincte. Termenii descompunerii sunt în ordine strict crescătoare.
Soluţiile se generează în ordinea: 1+2+6, 1+3+5, 1+8, 2+3+4, 2+7, 3+6 şi 4+5. Se aplică exact aceeaşi
metodă pentru scrierea lui 12 . Scrieţi în ordine toate soluţiile de forma 2+... ?

19. Utilizând metoda backtracking se generează în ordine lexicografică toate anagramele cuvântului caiet
(cuvinte formate din aceleași litere, eventual în altă ordine). Care este a șasea soluție?
a) actie b) catei c) actei d) catie