1. 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.
Câte dintre cuvintele generate încep cu litera b şi se termină cu litera e ?
Raspuns:
babe, bace, bade, bbbe, bbde, bbce, bebe, bcce, bcde, bdbe, bdce, bdde, bebe, bece, bede.
3 X 5 = 15

2.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 este ultimul cuvânt generat?
edda,eddb,eddc,eddd,edde,edeb,edec,eded
Raspuns : eded – ultimul cuv. generat

3.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 este penultimul cuvânt generat?
edda,eddb,eddc,eddd,edde,edeb,edec,eded
Raspuns : edec

4.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 este antepenultimul cuvânt generat?
edda,eddb,eddc,eddd,edde,edeb,edec,eded
Raspuns : edeb

5.Folosind modelul combinărilor se generează numerele naturale cu câte trei cifre distincte din mulţimea {1,2,3,7} , numere cu cifrele în ordine strict crescătoare, obţinându-se, în ordine: 123 , 127 , 137 , 237 . Dacă se utilizează exact aceeaşi metodă pentru a genera numerele naturale cu patru cifre distincte din mulţimea {1,2,3,4,5,6,7,8} , câte dintre numerele generate au prima cifră 2 şi ultima cifră 7 ?
2345, 2346, 2347, 2348, 2456, 2457, 2458, 2567, 2568, 2578
Raspuns: 3 numere

6.Utilizând metoda backtracking sunt generate numerele de 3 cifre, având toate cifrele distincte şi cu proprietatea că cifrele aflate pe poziţii consecutive sunt de paritate diferită. Ştiind că primele şase soluţii generate sunt, în această ordine, 103 , 105 , 107 , 109 , 123 , 125 , care este a zecea soluţie generată?
103 , 105 , 107 , 109 , 123 , 125 ,127 ,129 , 143 , 145
Raspuns: 145

7.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 zero pe pozitii consecutive. Primele 7 solutii generate sunt : 00100, 00101, 00110, 00111, 01001, 01010, 01011. Care este a 8-a solutie generata de acest algoritm ?
Raspuns: 01110 a 8-a solutie

8.Folosind tehnica bactracking un elev a scris un program care generează toate numerele de câte n cifre ( 0<n≤9 ), cifrele fiind în ordine strict crescătoare. Dacă n este egal cu 5 , scrieți în ordine crescătoare toate numerele având cifra unităților 6 , care vor fi generate de program.
Raspuns: 12346, 12356, 12456, 13456, 23456

9.Câte numere cu exact două cifre pot fi construite folosind doar cifre pare distincte? Enumeraţi umerele generate.
20, 40, 60, 80, 24, 26, 28, 42, 46, 48, 62, 64, 68, 82, 84, 86
Raspuns: 16 numere

10.Un algoritm generează în ordine crescătoare toate numerele de n cifre, folosind doar cifrele 3 , 5 şi 7 . Dacă pentru n=5 , primele 5 soluţii generate sunt 33333 , 33335 , 33337 , 33353 , 33355 , precizaţi care sunt ultimele 3 soluţii generate, în ordinea generării.
Raspuns: 77773, 77775, 77777

11.Un algoritm generează în ordine descrescătoare toate numerele de 5 cifre, fiecare dintre ele având cifrele în ordine strict crescătoare. Ştiind că primele 5 soluţii generate sunt 56789 , 46789 , 45789 , 45689 , 45679 , precizaţi care sunt ultimele 3 soluţii generate, în ordinea generării.
Raspuns: 12347, 12346, 12345

12.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
Raspuns: 11101, 11110, 11111

13.Un algoritm generează în ordine crescătoare, toate numerele de n cifre ( n<9 ), cu cifre distincte, care nu au două cifre pare alăturate. Dacă pentru n=5 , primele 5 soluţii generate sunt 10325 , 10327 , 10329 , 10345 , 10347 , precizaţi care sunt următoarele 3 soluţii generate, în ordinea obţinerii lor.
10325, 10327, 10329, 10345, 10347 ,10349,10365,10367
Raspuns: 10349, 10365, 10367

14.Un algoritm generează în ordine descrescătoare, toate numerele de n cifre ( n<9 ), cu cifrele în ordine strict crescătoare, care nu au două cifre pare alăturate. Dacă pentru n=5 , primele 5 soluţii generate sunt 56789 , 45789 , 45679 , 45678 , 36789 , precizaţi care sunt următoarele 3 soluţii generate, în ordinea obţinerii lor.
56789, 45789, 45679, 45678, 36789, 35679, 35678, 34789, 34679 Raspuns: 35679, 35678, 34789

15.Algoritmul de generare a tuturor numerelor de 5 cifre nenule, fiecare având cifrele ordonate strict crescător, este echivalent cu algoritmul de generare a:
a. submulţimilor unei mulţimi cu 5 elemente
b. produsului cartezian a unor mulţimi de cifre
c. aranjamentelor de 9 elemente luate câte 5
d. combinărilor de 9 elemente luate câte 5
Raspuns: d.

16.Generând şirurile de maximum 3 caractere distincte din mulţimea {A,B,C,D,E} , ordonate lexicografic, obţinem succesiv: A , AB , ABC , ABD ,…. Ce şir va fi generat imediat după BAE ?
a. BCA
b. CAB
c. BC  
d. BEA
Raspuns: c.

17.Pentru generarea tuturor mulţimilor de câte 5 cifre, având la dispoziţie cifrele de la 1 la 9 , se poate utilza un algoritm echivalent cu algoritmul de generare a:
a. permutărilor de 5 elemente
b. submulţimilor mulţimii{1,2,3,4,5,6,7,8,9}
c. combinărilor de 9 elemente luate câte 5
d. aranjamentelor de 9 elemente luatecâte 5
Raspuns: b.

18.Utilizand metoda backtracking  se genereaza permutarile cuvantului INFO. Daca primele 3 solutii generate sunt : FINO, FION, FNIO care este a 5-a solutie ?
INFO – 1234
FINO – 3124
FION – 3142
FNIO – 3214
FNOI – 3241
Raspuns: FNOI -> a 5-a solutie

19. Folosind un algoritm de generare putem obţine numere naturale de k cifre care au suma cifrelor egală cu un număr natural s . Astfel, pentru valorile k=2 şi s=6 se generează, în ordine, numerele: 15 , 24 , 33 , 42 , 51 , 60 .
Care va fi al treilea număr generat pentru k=4 şi s=5 ?
a. 1301
b. 1022
c. 2201
d. 1031
Raspuns: a)

20. Completarea unui bilet de LOTO presupune colorarea a 6 numere din cele 49 înscrise pe bilet. O situaţie statistică pe o anumită perioadă de timp arată că cele mai frecvente numere care au fost extrase la LOTO sunt: 2, 20, 18, 38, 36, 42, 46, 48 . Câte bilete de 6 numere se pot completa folosind doar aceste valori ştiind că numărul 42 va fi colorat pe fiecare bilet.
a. 21
b. 6!
c. 42
d. 56
Raspuns: a)

21. Pentru generarea tuturor mulţimilor de câte 5 cifre, având la dispoziţie cifrele de la 1 la 9 , se poate utilza un algoritm echivalent cu algoritmul de generare a:
a. permutărilor de 5 elemente
b. submulţimilor mulţimii {1,2,3,4,5,6,7,8,9}
c. combinărilor de 9 elemente luate câte 5
d. aranjamentelor de 9 elemente luate câte 5
Raspuns: c)

22. 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+... ?
Raspuns: 2+3+7*2+4+6 ; 2+10

23. Se utilizează un algoritm pentru a genera în ordine lexicografică inversă toate permutările mulţimii { 1 , 2 , 3 , 4 , 5 }. Primele patru permutări generate sunt: 54321 , 54312 , 54231 , 54213. A cincea permutare este:
a. 53421
b. 54321
c. 54132
d. 54123
Raspuns: c)

24. 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 8 . Câte soluţii vor fi generate?
a. 3
b. 4
c. 6
d. 5
Raspuns: d)

25. Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a scrie numărul 6 ca sumă a cel puţin două numere naturale nenule. Termenii descompunerii sunt în ordine crescătoare. Soluţiile se generează în ordinea: 1+1+1+1+1+1, 1+1+1+1+2, 1+1+1+3, 1+1+4, 1+5, 2+2+2, 2+4 şi 3+3. Se aplică exact aceeaşi metodă pentru scrierea lui 9 . Care este penultima soluţie?
a. 3+3+3
b. 3+6 c. 4+5
d. 2+7

Raspuns:b)

26. Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a scrie numărul 6 ca sumă a cel puţin două numere naturale nenule. Termenii descompunerii sunt în ordine crescătoare. Soluţiile se generează în ordinea: 1+1+1+1+1+1, 1+1+1+1+2, 1+1+1+3, 1+1+4, 1+5, 2+2+2, 2+4 şi 3+3. Se aplică exact aceeaşi metodă pentru scrierea lui 9 . Câte soluţii de forma 2+... vor fi generate?
a. 2
b. 3
c. 4 d. 5

Raspuns: c)

27. Utilizând metoda backtracking se generează numerele naturale formate din exact 3 cifre şi care au suma cifrelor egală cu 4, în această ordine: 103, 112, 121, 130, 202, 211, 220, 301, 310, 400 . Dacă utilizăm acelaşi algoritm pentru a genera toate numerele de 4 cifre ce au suma cifrelor egala cu 7 precizaţi care este numarul generat imediat dupa 1222.
a. 1231
b. 1223
c. 1213
d. 1321
Raspuns: a)

28. Utilizând metoda backtracking se generează toate permutările mulţimii {1,2,3,4} . Dacă primele trei permutări generate sunt, în acestă ordine: 1234, 1243, 1324 precizaţi care este permutarea generată imediat după 3412 .
a. 3421
b. 3413
c. 4123
d. 3214
Raspuns: a)

29. Utilizând metoda backtracking se generează numerele formate din câte 3 cifre distincte din mulţimea {1,3,5,7} . Dacă primele trei numere generate sunt, în acestă ordine: 135, 137,153 care este cel de-al patrulea număr generat?
a. 157
b. 173
c. 315
d. 357
Raspuns: a)

30. Utilizând metoda backtracking se generează permutările cuvântului info . Dacă primele trei soluţii generate sunt: fino, fion, fnio care este cea de-a cincea soluţie?
a. foin
b. fnoi
c. foni
d. ifon

Raspuns: a)

31. Utilizând metoda backtracking se generează toate cuvintele de câte 3 litere din mulţimea {a,b,c} . Dacă primele patru cuvinte generate sunt, în acestă ordine: aaa, aab, aac, aba, care este cel de-al optulea cuvânt generat?
a. acb
b. acc
c. aca
d. bca<
Raspuns: a)

32. Un program generează, în ordine crescătoare, numerele naturale, de exact 5 cifre din mulţimea { 1 , 2 , 3 , 4 , 5} . Fiecare dintre numerele generate are cifrele distincte două câte două. Primele 3 numere astfel generate sunt: 12345 , 12354 , 12435 . Care este numărul generat imediat după 12543 ?
a. 15342
b. 12534
c. 13245
d. 13452
Raspuns: c)

33. Într-un penar sunt unsprezece creioane, dintre care trei sunt roşii iar celelalte sunt negre. Dacă scoatem din penar cinci creioane, câte posibilităţi există ca două dintre ele să fie roşii?
Raspuns: 168

34.  Se generează în ordine strict crescătoare numerele de câte şase cifre care conţin: cifra 1 o singură dată, cifra 2 de două ori şi cifra 3 de trei ori. Se obţin, în această ordine, numerele: 122333 , 123233 , 123323 , …, 333221 . Câte numere generate prin această metodă au prima cifră 1 şi ultima cifră 2 ?
Raspuns: 122333, 123233, 123323, 123332 , 132332 ,132323, 132233, 133223, 133232 , 133322=> 4 numere

35.  Se generează în ordine strict crescătoare toate numerele de câte şase cifre care conţin: cifra 1 o singură dată, cifra 2 de două ori şi cifra 3 de trei ori. Se obţin, în această ordine, numerele: 122333 , 123233 , 123323 , …, 333221 . Ce număr se generează imediat după 332312 ?
Raspuns: 332321

36.  Se consideră un număr natural nenul x având exact 8 cifre, cifrele lui fiind distincte 2 câte 2 , iar printre cifrele sale se găseşte şi cifra 0 . Permutând cifrele lui x se obţin alte numere naturale. Câte dintre numerele obţinute, inclusiv x , au exact 8 cifre?
Raspuns: Numarul de permutari pentru un numar de 8 cifre este 8!. Din acestea se scad cele cu cifra 0 pe prima pozitie,adica7!.
8!-7!=35280.

37.   Utilizând metoda backtracking se generează în ordine lexicografică toate anagramele cuvântului caiet ( cuvinte formate din aceleaşi litere, eventual în altă ordine). Câte cuvinte vor fi generate?
Rezolvare: Permutari de n litere. Cuvantul are 5 litere. P5=5!=1*2*3*4*5=120.

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

Rezolvare: caiet, caite, caeti, caeit, catei, catie

39. Utilizând metoda backtracking se generează toate matricele pătratice de ordinul 4 ale căror elemente aparţin mulţimii {0,1} cu proprietatea că pe fiecare linie şi pe fiecare coloană există o singură valoare 1 . Primele 3 soluţii generate sunt, în această ordine:
1 0 0 0
1 0 0 0
1 0 0 0
0 1 0 0

0 1 0 0
0 0 1 0
0 0 1 0
0 0 1 0

0 1 0 0
0 0 0 1
0 0 0 1
0 0 0 1.
Care este penultima soluţie?

a. 0 0 0 1
    0 0 1 0
    1 0 0 0
    0 1 0 0

b. 0 1 0 0
    1 0 0 0
    0 0 1 0
    0 0 0 1

c. 0 0 0 1
    0 1 0 0
    0 0 1 0
    1 0 0 0

d. 0 0 1 0
    1 0 0 0
    0 1 0 0
    0 0 0 1

Raspuns: a

40. 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

Raspuns: b

41. Se utilizează metoda backtracking pentru a genera toate cuvintele de câte patru litere distincte din mulţimea {d,a,n,s} . Ştiind că al doilea cuvânt generat este dans , iar al treilea este dsan , care va fi ultimul cuvânt obţinut?
a. nsad
b. snad
c. snda
d. dans
dasn, dans, dsan, dnsa, dnas,…., nsad
Raspuns: a

42. Se utilizează metoda backtracking pentru a genera toate cuvintele de câte trei litere distincte din mulţimea {i,n,f,o} . Ştiind că ultimele trei cuvinte generate sunt, în ordine, ion , inf şi ino , care este cel de-al doilea cuvânt obţinut?
a. ofn
b. ifo
c. foi
d. nif
Raspuns: c.

43. Se utilizează metoda backtracking pentru a genera toate cuvintele care conţin toate literele din mulţimea {i,n,f,o} , astfel încât fiecare literă să apară exact o dat într-un cuvânt. Ştiind că al doilea cuvânt generat este info iar al treilea este ionf , care este ultimul cuvânt obţinut?
a. nifo
b. ofni
c. ofin
d. foni
Raspuns: d.

44. Se utilizează metoda backtracking pentru a genera toate cuvintele care conţin toate literele din mulţimea {i,n,f,o} , astfel încât fiecare literă să apară exact o data într-un cuvânt şi literele n şi o să nu se afle pe poziţii vecine. Ştiind că primul cuvânt generat este info , iar al treilea este nifo care este cel de-al doilea cuvânt obţinut?
a. iofn
b. inof
c. ionf
d. niof
Raspuns: d.

45. Generarea matricelor pătratice de ordinul n , cu elemente 0 şi 1 , cu proprietatea că pe fiecare linie şi pe fiecare coloană există un singur element egal cu 1 , se poate realiza utilizând metoda backtracking. Algoritmul utilizat este echivalent cu algoritmul de generare a:
a. combinărilor
b. permutărilor
c. aranjamentelor
d. produsului cartezian

Raspuns: d.

46. Se utilizează metoda backtracking pentru a genera toate cuvintele care conţin toate literele din mulţimea {i,n,f,o}, astfel încât fiecare literă să apară exact o data într-un cuvânt. Ştiind că al doilea cuvânt generat este info iar al treilea este ionf, care este ultimul cuvânt obţinut? a. nifo
b. ofni
c. ofin
d. foni
Daca al 2-lea cuvant generat din multimea {info} este info si al treilea cuvant generat este ionf=> ca primul cuvant generat este inof iar al 4-lea este iofn. De la primul cuvant observam ca ultimele 4 cuvinte generate vor incepe cu f ,prin eliminare ,ultimul cuvant va fi foni.
Raspuns: d.

47. Generarea matricelor p ătratice de ordinul n, cu elemente 0 şi 1, cu proprietatea că pe fiecare linie şi pe fiecare coloană există un singur element egal cu 1, se poate realiza utilizând metoda backtracking. Algoritmul utilizat este echivalent cu algoritmul de generare a:
a. combinărilor
b. permutărilor
c. aranjamentelor
d. produsului cartezian
Raspuns: b.
Prin definitie, metoda backtracking poate fi asociata cu permutarile.

48.Se generează, prin metoda backtracking toate partiţiile mulţimii A={1,2,3} obţinându-se următoarele soluţii: {1}{2}{3}; {1}{2,3}; {1,3}{2}; {1,2}{3}; {1,2,3}. Se observă că dintre acestea, prima soluţie e alcătuită din exact trei submulţimi. Dacă se foloseşte aceeaşi metodă pentru a genera partiţiile mulţimii {1,2,3,4} stabiliţi câte dintre soluţiile generate vor fi alcătuite din exact trei submulţimi.
a. 3
b. 12
c. 6
d. 5
Raspuns: c.
Generand fiecare solutie din submultimea A, vom obtine exact 6 solutii a cate 3 submultimi.

49. Se generează, prin metoda backtracking, toate modalităţile de aşezare a numerelor naturale de la 1 la 5, astfel încât oricare 2 numere consecutive s ă nu se afle pe poziţii alăturate. Dacă primele 2 soluţii sunt: (1,3,5,2,4) şi (1,4,2,5,3), care este prima soluţie generată în care primul număr este 4?
a. (4, 1, 3, 2, 5)
b. (4, 2, 5, 1, 3)
c. (4, 3, 5, 3, 1)
d.(4, 1, 3, 5, 2)
Raspuns: d.
Dupa 4 trebuie sa fie neaparat 1 ,ramane A si D. La A ai pe pozitia 2 si 3 numere consecutive deci sare..inseamna ca a mai ramas D.