Backtracking Variante 2009

BAC 2009 – Backtracking

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?
a. 9
b. 15
c. 12
d. 20

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?
a. edcb
b. eeee
c. edde
d. eded

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?
a. edec
b. eded
c. edde
d. edcb

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?
a. edde
b. eddb
c. edeb
d. edcb

1
Backtracking Variante 2009

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?
a. 8
b. 3
c. 4
d. 6

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ă?
a. 145
b. 147
c. 230
d. 149

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

8. Utilizând metoda backtracking sunt generate numerele de 3 cifre care au

cifrele în ordine crescătoare, iar cifrele aflate pe poziţii consecutive sunt de
paritate diferită. Ştiind că primele cinci soluţii generate sunt, în această ordine,
123, 125, 127, 129, 145, care este cel de al 8-lea număr generat?
a. 169
b. 149
c. 167
d. 147

9. Utilizând metoda backtracking, sunt generate n ordine crescătoare toate

numerele de 3 cifre, astfel încât cifrele sunt în ordine crescătoare, iar cifrele
aflate pe poziţii consecutive sunt de paritate diferită. Ştiind că primele trei soluţii
generate sunt, în această ordine, 123, 125, 127, scrieţi toate numerele generate
care au suma cifrelor egală cu 12.

2
Backtracking Variante 2009

10. Un elev a scris un program care, folosind metoda backtracking, generează

toate numerele de câte 5 cifre, cifrele fiind în ordine strict crescătoare. Scrieţi
toate numerele generate de program care au prima cifră 5.

11. Un algoritm de tip backtracking generează, în ordine lexicografică, toate

şirurile de 5 cifre 0 şi 1 cu proprietatea că nu există mai mult de două cifre 0 pe
poziţii consecutive. Primele 7 soluţii generate sunt: 00100, 00101, 00110, 00111,
01001, 01010, 01011. Care este a 8-a soluţie generată de acest algoritm?
a. 01110
b. 01100
c. 01011
d. 01101

12. Pentru a scrie valoarea 10 ca sumă de numere prime se foloseşte metoda

backtracking şi se generează, în această ordine, sumele distincte: 2+2+2+2+2,
2+2+3+3, 2+3+5, 3+7, 5+5. Folosind exact aceeaşi metodă, se scrie valoarea 9
ca sumă de numere prime. Care sunt primele trei soluţii, în ordinea generării lor?

13. Trei băieţi, Alin, Bogdan şi Ciprian, şi trei fete, Delia, Elena şi Felicia,
trebuie să formeze o echipă de 3 copii, care să participe la un concurs. Echipa
trebuie să fie mixtă (adică să conţină cel puţin o fată şi cel puţin un băiat).
Ordinea copiilor în echipă este importantă deoarece aceasta va fi ordinea de
intrare a copiilor în concurs (de exemplu echipa Alin, Bogdan, Delia este diferită
de echipa Bogdan, Alin, Delia). Câte echipe se pot forma, astfel încât din ele să
facă parte simultan Alin şi Bogdan? Daţi exemplu de o echipă corect formată
din care să nu facă parte nici Alin şi nici Bogdan.

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

15. Câte numere cu exact două cifre pot fi construite folosind doar cifre pare
distincte?
a. 12
b. 16
c. 20

3
Backtracking Variante 2009

d. 25

15. Un algoritm generează în ordine crescătoare toate numerele de n cifre,

folosind doar cifrele 3, 5 şi 7. Dacă pentru n=5, primele cinci soluţii generate sunt
33333, 33335, 33337, 33353, 33355, precizaţi care sunt ultimele trei soluţii
generate, în ordinea generării.

16. 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 cinci
soluţii generate sunt 56789, 46789, 45789, 45689, 45679, precizaţi care sunt
ultimele trei soluţii generate, în ordinea generării.

17. 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 patru soluţii generate
sunt 00000, 00001, 00010, 00011, precizaţi care sunt ultimele trei soluţii
generate, în ordinea obţinerii lor.

18. 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 cinci soluţii generate sunt 10325, 10327, 10329, 10345, 10347, precizaţi
care sunt următoarele trei soluţii generate, în ordinea obţinerii lor.

19. 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 cinci soluţii generate sunt 56789, 45789, 45679,
45678, 36789, precizaţi care sunt următoarele trei soluţii generate, în ordinea
obţinerii lor.

20. Următoarele probleme se referă la mulţimea de numere reale M={x1, x2, …,

xn}
(1000<n≤10000). Care dintre acestea, comparativ cu celelalte, admite un
algoritm care se încheie după un număr minim de paşi?
a. sortarea elementelor mulţimii M
b. generarea elementelor produsului cartezian M x M
c. determinarea elementului minim al mulţimii M
d. generarea tuturor permutărilor mulţimii M

4
Backtracking Variante 2009

21. In timpul procesului de generare a permutărilor mulţimii {1,2,…,n} prin

metoda backtracking, în tabloul unidimensional x este plasat un element xk
(1≤k≤n). Acesta este considerat valid dacă este îndeplinită condiţia:
a. xk{x1, x2, …, xk-1}
b. xk≠xk-1
c. xk{x1, x2, …, xn}
d. xk≠xk-1 şi xk≠xk+1

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

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

24. Un program citeşte o valoare naturală nenulă impară pentru n şi apoi

generează şi afişează în ordine crescătoare lexicografic toate combinaţiile
formate din n cifre care îndeplinesc următoarele proprietăţi:
- încep şi se termină cu 0;
- modulul diferenţei între oricare două cifre alăturate dintr-o combinaţie este 1.
Astfel, pentru n=5, combinaţiile afişate sunt, în ordine, următoarele: 01010,
01210. Dacă se rulează acest program şi se citeşte pentru n valoarea 7, imediat
după combinaţia 0101210 va fi afişată combinaţia:
a. 0121210
b. 0123210
c. 0111210
d. 0121010

25. Pentru generarea numerelor cu n cifre formate cu elementele mulţimii

{0,2,9} se
utilizează un algoritm backtracking care, pentru n=2, generează, în ordine,
numerele 20,22,29,90,92,99. Dacă n=4 şi se utilizează acelaşi algoritm, care
este numărul generat imediat după numărul 2009?
a. 2002

5
Backtracking Variante 2009

b. 2020
c. 2090
d. 2010

26. Pentru generarea în ordine crescătoare a numerelor cu n cifre formate cu

elementele mulţimii {0,2,8} se utilizează un algoritm backtracking care, pentru
n=2, generează, în ordine, numerele 20,22,28,80,82,88. Dacă n=4 şi se
utilizează acelaşi algoritm, precizaţi câte numere generate sunt divizibile
cu 100?
a. 8
b. 90
c. 6
d. 10

27. Generarea tuturor cuvintelor de trei litere mici, nu neapărat distincte, ale
alfabetului englez, se poate realiza cu ajutorul unui algoritm echivalent cu cel de
generare a:
a. produsului cartezian
b. combinărilor
c. aranjamentelor
d. permutărilor

28. În câte dintre permutările elementelor mulţimii {‘I’,’N’,’F’,’O’} vocalele apar

pe
poziţii consecutive?
a. 24
b. 6
c. 12
d. 4

29. Pentru generarea numerelor cu n cifre formate cu elementele mulţimii

{0,4,8} se utilizează un algoritm backtracking care, pentru n=2, generează, în
ordine, numerele 40,44,48,80,84,88.
Dacă n=4 şi se utilizează acelaşi algoritm, care este numărul generat imediat
după numărul 4008 ?
a. 4040
b. 4004
c. 4080
d. 8004

6
Backtracking Variante 2009

30. Având la dispoziţie cifrele 0, 1 şi 2 putem genera, în ordine crescătoare,

numere care au suma cifrelor egală cu 2 astfel încât primele 6 numere generate
sunt, în această ordine: 2, 11, 20, 101, 110, 200. Folosind acelaşi algoritm se
generează numere cu cifrele 0, 1, 2 şi 3 care au suma cifrelor egală cu 4. Care
va fi al 7-lea număr din această generare ?
a. 103
b. 301
c. 220
d. 130

31. În vederea participării la un concurs, elevii de la liceul sportiv au dat o probă

de selecţie, în urma căreia primii 6 au obţinut punctaje egale. În câte moduri
poate fi formată echipa selecţionată ştiind că poate avea doar 4 membri, aleşi
dintre cei 6, şi că ordinea acestora în cadrul echipei nu contează?
a. 24
b. 30
c. 15
d. 4

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

33. Completarea unui bilet de LOTO presupune colorarea a 6 numere dintre

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

34. 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}

7
Backtracking Variante 2009

c. combinărilor de 9 elemente luate câte 5

d. aranjamentelor de 9 elemente luate câte 5

35. 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 fiecărei sume 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 ordinea generării, toate soluţiile de
forma 2+...

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

37. 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 fiecărei sume 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

38. 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
fiecărei sume 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+2+2, 1+1+4, 1+2+3, 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

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

8
Backtracking Variante 2009

fiecărei sume 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+2+2, 1+1+4, 1+2+3, 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

40. 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. 3214
b. 3413
c. 4123
d. 3421

41. 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. 315
b. 173
c. 157
d. 357

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

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

9
Backtracking Variante 2009

44. Se consideră opt bancnote: trei cu valoarea de 1 leu, două cu valoarea de

10 lei şi trei cu valoarea de 100 de lei. Câte rezultate distincte se pot obţine
însumând valorile a exact cinci dintre cele opt bancnote, astfel încât suma să fie
de cel puţin 200 de lei?
a. 6
b. 12
c. 15
d. 3

45. Se generează prin metoda backtracking mulţimile distincte ale căror

elemente sunt numere naturale nenule şi care au proprietatea că suma
elementelor fiecărei mulţimi este egală cu 7. Astfel, sunt generate, în această
ordine, mulţimile: {1,2,4}, {1,6}, {2,5}, {3,4}, {7}. Folosind aceeaşi metodă pentru
a genera mulţimile distincte ale căror elemente sunt numere naturale nenule şi
care au proprietatea că suma elementelor fiecărei mulţimi este egală cu 9,
stabiliţi în ce ordine sunt generate următoarele mulţimi: M1={2,3,4}; M2={3,6};
M3={2,7}; M4={4,5}.

46. 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?
a. 1
b. 3
c. 4
d. 8

47. 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 află imediat înaintea şi ce număr se află imediat după numărul 332312
în şirul numerelor generate?

48. 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 care încep cu litera t vor fi generate?
a. 1
b. 6
c. 12
d. 24

10
Backtracking Variante 2009

49. 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. catei
b. actie
c. actei
d. catie

50. 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 4 soluţii generate
sunt, în această ordine:
1000
0100
0010
0001

1000
0100
0001
0010

1000
0010
0100
0001

1000
0010
0001
0100
Care este a opta soluţie? (4p.)
a. 0 1 0 0
1000
0001
0010
b. 0 1 0 0
1000
0010
0001
c. 0 1 0 0
0010
1000
0001

11
Backtracking Variante 2009

d. 0 0 1 0
1000
0100
0001

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

52. Se utilizează metoda backtracking pentru a genera în ordine lexicografică

toate cuvintele de câte patru litere din mulţimea {d,a,n,s}, astfel încât în niciun
cuvânt să nu existe două litere alăturate identice. Ştiind că primele trei cuvinte
generate sunt, în ordine, adad, adan şi adas, care va fi ultimul cuvânt obţinut?
a. snns
b. nsns
c. snsn
d. dans

53. Se utilizează metoda backtracking pentru a genera în ordine lexicografică

toate cuvintele de câte trei litere distincte din mulţimea {d,a,n,s}. Care este cel
de-al treilea cuvânt obţinut?
a. ads
b. ans
c. dan
d. and

54. Se utilizează metoda backtracking pentru a genera în ordine lexicografică

toate cuvintele care conţin toate literele din mulţimea {a,m,i,c}, astfel încât
fiecare literă să apară exact o dată într-un cuvânt. Câte soluţii sunt generate
după cuvântul amic şi înainte de cuvântul cami?
a. 6
b. 4
c. 1
d. 3

55. 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ă

12
Backtracking Variante 2009

exact o dată î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, al patrulea şi al cincilea sunt
nifo, niof, nfio care este cel de-al doilea cuvânt obţinut?
a. iofn
b. inof
c. ionf
d. niof

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

57. Utilizând metoda backtracking pentru afişarea tuturor modalităţilor de

descompunere a unui
număr natural ca o sumă de numere naturale nenule, pentru n=3 se obţin, în
ordine, soluţiile: 1+1+1; 1+2; 2+1; 3. Ordinea de scriere a termenilor dintr-o
descompunere este semnificativă. Folosind aceeaşi metodă pentru n=10, care
este soluţia generată imediat după 1+1+3+5?
a. 1+1+4+1+1+1+1
b. 1+1+7+1
c. 1+2+7
d. 1+1+4+4

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

59. 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 două 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?

13
Backtracking Variante 2009

a. (4, 1, 3, 2, 5)
b. (4,2,5,1, 3)
c. (4, 3, 5, 3, 1)
d. (4, 1, 3, 5, 2)

60. Se generează, prin metoda backtracking, toate modalităţile de aşezare a

numerelor naturale de la 1 la 5 astfel încât oricare două numere consecutive să
nu se afle pe poziţii alăturate. Dacă primele două soluţii sunt: (1,3,5,2,4) şi
(1,4,2,5,3), care este prima soluţie generată care începe cu 2?
a. (2, 4, 1, 3, 5)
b. (2, 5, 4, 3, 1)
c. (2, 4, 1, 3, 1)
d. (2, 3, 5, 4, 1)

61. Se generează în ordine crescătoare, toate numerele naturale de 5 cifre

distincte, care se pot forma cu cifrele 2,3,4,5 şi 6. Să se precizeze numărul
generat imediat înaintea şi numărul generat imediat după secvenţa următoare :
34256, 34265, 34526, 34562
a. 32645 şi 34625
b. 32654 şi 34655
c. 32654 şi 34625
d. 32645 şi 34655

62. Se generează în ordine crescătoare, toate numerele naturale de 5 cifre

distincte, care se pot forma cu cifrele 5,6,7,8 şi 9. Să se precizeze numărul
generat imediat înaintea şi numărul generat imediat după secvenţa următoare :
67589,67598,67859,67895.
a. 65987 şi 67958
b. 65978 şi 67988
c. 65978 şi 67958
d. 65987 şi 67988

63. Se utilizează metoda backtracking pentru a genera toate submulţimile cu 4

elemente ale mulţimii {1,2,3,4,5,6}. Numărul de submulţimi generate este:
a. 30
b. 35
c. 5
d. 15

64. Construim anagramele unui cuvânt c1c2c3c4 prin generarea în ordine

lexicografică a permutărilor indicilor literelor cuvântului şi obţinem c1c2c3c4

14
Backtracking Variante 2009

c1c2c4c3 c1c3c2c4 … c4c3c1c2 c4c3c2c1. Pentru anagramele cuvântului

pateu, după şirul paetu, paeut, paute cuvintele imediat următoare sunt:
a. pauet şi ptaeu
b. ptaeu şi ptaue
c. pauet şi ptaue
d. ptaeu şi patue

65. Pentru rezolvarea cărei probleme dintre cele enumerate mai jos se poate
utiliza metoda backtracking ?
a. determinarea reuniunii a 3 mulţimi
b. determinarea tuturor divizorilor unui număr din 3 cifre
c. determinarea tuturor elementelor mai mici decât 30000 din şirul lui Fibonacci
d. determinarea tuturor variantelor în care se pot genera steagurile cu 3 culori
(din mulţimea: ”roşu”, ”galben”, ”albastru” şi ”alb”), având la mijloc culoarea
”galben”

66. Se generează în ordine crescătoare toate numerele de exact 4 cifre care se

pot forma cu elementele mulţimii {0,1,2,3,4}. Primele 8 soluţii generate sunt, în
ordine: 1000, 1001, 1002, 1003, 1004, 1010, 1011, 1012. Care sunt primele trei
numere ce se vor genera imediat după numărul 3443?
a. 4000,4001,4002
b. 3444,4443,4444
c. 3444,4444,4000
d. 3444,4000,4001

67. Se generează în ordine crescătoare toate numerele de 4 cifre, cu cifre

distincte, astfel încât diferenţa în valoare absolută dintre prima şi ultima,
respectiv a doua şi a treia cifră este egală cu 2. Primele 11 soluţii generate sunt,
în ordine: 1023, 1203, 1243, 1423, 1463, 1573, 1643, 1683, 1753, 1793, 1863.
Care dintre următoarele numere se va genera imediat înaintea numărului 9317?
a. 9247
b. 9357
c. 9207
d. 8976

68. Se generează în ordine crescătoare toate numerele de 4 cifre, cu cifre

distincte, astfel încât diferenţa în valoare absolută dintre ultimele două cifre ale
fiecărui număr generat este egală cu 2. Primele opt soluţii generate sunt, în
ordine: 1024, 1035, 1042, 1046, 1053, 1057, 1064, 1068. Care dintre
următoarele numere se va genera imediat după numărul 8975?
a. 8979
b. 9013

15
Backtracking Variante 2009

c. 8957
d. 9024

69. Prin metoda backtracking se generează toate anagramele (cuvintele

obţinute prin permutarea literelor) unui cuvânt dat. Ştiind că se aplică această
metodă pentru cuvântul solar, precizaţi câte cuvinte se vor genera astfel încât
prima şi ultima literă din fiecare cuvânt generat să fie vocală (sunt considerate
vocale caracterele a, e, i , o, u)?
a. 24
b. 6
c. 10
d. 12

70. Dacă se utilizează metoda backtracking pentru a genera toate permutările

de 4 obiecte şi primele 5 permutări generate sunt, în această ordine, 4 3 2 1, 4 3
1 2, 4 2 3 1, 4 2 1 3, 4 1 3 2, atunci a 6-a permutare este:
a. 3 2 1 4
b. 3 4 2 1
c. 1 4 3 2
d. 4 1 2 3

71. La un concurs participă 50 de sportivi împărţiţi în 5 echipe, astfel încât în

fiecare echipă să fie câte 10 sportivi. Problema determinării tuturor grupelor de
câte 5 sportivi, câte unul din fiecare echipă, este similară cu generarea tuturor:
a. elementelor produsului cartezian AxAxAxAxA, unde A={1,2,…,10}
b. submulţimilor cu 5 elemente ale mulţimii {1,2,…,10}
c. permutărilor mulţimii {1,2,3,4,5}
d. partiţiilor mulţimii {1,2,…,10}

72. Un program construieşte şi afişează elementele produsului cartezian AxBxC

pentru mulţimile A={1,2,3,4}, B={1,2,3}, C={1,2}. Care dintre următoarele triplete
NU va fi afişat?
a. (3,2,1)
b. (1,3,2)
c. (1,2,3)
d. (2,2,2)

73. Problema generării tuturor codurilor formate din exact 4 cifre nenule, cu
toate cifrele distincte două câte două, este similară cu generarea tuturor:
a. aranjamentelor de 9 elemente luate câte 4
b. permutărilor elementelor unei mulţimi cu 4 elemente

16
Backtracking Variante 2009

c. elementelor produsului cartezian AxAxAxA unde A este o mulţime cu 9

elemente
d. submulţimilor cu 4 elemente ale mulţimii {1,2,3,4,5,6,7,8,9}

74. Folosind cifrele {1,2,3} se generează, în ordinea crescătoare a valorii, toate

numerele pare formate din trei cifre distincte. Astfel, se obţin în ordine, numerele:
132, 312. Folosind aceeaşi metodă, se generează numerele pare formate din
patru cifre distincte din mulţimea {1,2,3,4}. Care va fi al 4-lea număr generat ?
a. 2134
b. 1432
c. 2314
d. 1423

75. O clasă de 28 de elevi este la ora de educaţie fizică şi profesorul doreşte să

formeze o echipă de 4 elevi. Ordinea elevilor în cadrul echipei nu are importanţă.
Algoritmul de generare a tuturor posibilităţilor de a forma o asfel de echipă este
similar cu algoritmul de generare a tuturor:
a. aranjamentelor de 28 de elemente luate câte 4
b. combinărilor de 28 de elemente luate câte 4
c. partiţiilor unei mulţimi cu28 de elemente
d. elementelor produsului cartezian AxAxAxA, A fiind o mulţime cu 28 de
elemente

76. Folosind cifrele {2,3,4} se generează, în ordinea crescătoare a valorii, toate

numerele impare formate din trei cifre distincte. Astfel se obţin, în ordine,
numerele: 243, 423. Folosind aceeaşi metodă, se generează numerele pare
formate din patru cifre distincte din mulţimea {2,3,4,5}. Care va fi al 5-lea număr
generat?
a. 3452
b. 3524
c. 2534
d. 3542

77. Folosind cifrele {1,2,3} se generează, în ordinea crescătoare a valorii, toate

numerele formate din exact trei cifre, în care cifrele alăturate au valori
consecutive. Astfel se obţin în ordine, numerele: 121, 123, 212, 232, 321 şi 323.
Folosind aceeaşi metodă se generează numere de patru cifre din mulţimea
{1,2,3,4} care îndeplinesc aceeaşi condiţie. Care va fi al 5-lea număr generat ?
a. 2121
b. 2123
c. 3121
d. 2323

17
Backtracking Variante 2009

78. Folosind cifrele {3,4,5} se generează, în ordinea crescătoare a valorii, toate

numerele impare formate din trei cifre distincte. Astfel se obţin, în ordine,
numerele: 345, 435, 453, 543. Folosind aceeaşi metodă, se generează numerele
impare formate din patru cifre distincte din mulţimea {2,3,4,5}. Care va fi al 5-lea
număr generat?
a. 3425
b. 2534
c. 4235
d. 3245

79. Folosind cifrele {1,2,3} se generează, în ordinea crescătoare a valorii, toate

numerele impare formate din trei cifre distincte. Astfel se obţin, în ordine,
numerele: 123, 213, 231, 321. Folosind aceeaşi metodă, se generează numerele
impare formate din patru cifre distincte din mulţimea {1,2,3,4}. Care va fi al 5-lea
număr generat ?
a. 2413
b. 1423
c. 2431
d. 3241

80. La examenul de bacalaureat, un elev primeşte un test format dintr-un subiect

de tip I, unul de tip II şi unul de tip III. Stiind că pentru fiecare tip de subiect sunt
elaborate exact 100 de variante, algoritmul de generare a tuturor posibilităţilor de
a forma un test este similar cu algoritmul de generare a:
a. elementelor produsului cartezian
b. aranjamentelor
c. permutărilor
d. submulţimilor

81. Trei elevi vor să înfiinţeze o trupă de rock formată dintr-un chitarist solo, un
basist şi un baterist. Toţi trei ştiu să cânte atât la chitară solo, cât şi la chitară
bas, şi se pricep cu toţii şi la baterie. Algoritmul de generare a tuturor
posibilităţilor de a forma trupa este similar cu algoritmul de generare a:
a. aranjamentelor
b. permutărilor
c. elementelor produsului cartezian
d. submulţimilor

82. Ionel doreşte să ofere cadouri membrilor familiei sale, formată din cei doi
părinţi şi o soră. Decide să le ofere stilouri de diferite culori. La magazin există

18
Backtracking Variante 2009

stilouri de 5 culori diferite. Algoritmul de generare a tuturor posibilităţilor de a

atribui câte un stilou fiecăruia dintre cei trei membri ai familiei, fără să se repete
vreo culoare, este similar cu algoritmul de generare a
a. aranjamentelor
b. elementelor produsului cartezian
c. permutărilor
d. submulţimilor

83. O clasă formată din 28 de elevi doreşte să trimită la consfătuirea

reprezentanţilor claselor şcolii o delegaţie formată din 3 elevi. Algoritmul de
generare a tuturor posibilităţilor de a forma o delegaţie este similar cu algoritmul
de generare a:
a. permutărilor
b. aranjamentelor
c. combinărilor
d. submulţimilor

84. La un bal mascat, magazia şcolii pune la dispoziţia elevilor 10 pelerine, 10

măşti şi 10 pălării divers colorate. Algoritmul de generare a tuturor posibilităţilor
de a obţine un costum format dintr-o pălărie, o mască şi o pelerină este similar
cu algoritmul de generare a :
a. elementelor produsului cartezian
b. aranjamentelor
c. permutărilor
d. submulţimilor

85. Pentru a planifica în orarul unei şcoli, la clasa a XII-a, 4 ore de informatică în
zile lucrătoare diferite din săptămână, câte o singură oră pe zi, se poate utiliza un
algoritm echivalent cu algoritmul de generare a:
a. permutărilor de 4 elemente
b. aranjamentelor de 4 elemente luate câte 5
c. aranjamentelor de 5 elemente luate câte 4
d. combinărilor de 5 elemente luate câte 4

86. Având la dispoziţie cifrele 0, 1 şi 2 se pot genera, în ordine crescătoare,

numere care au suma cifrelor egală cu 2. Astfel, primele 6 soluţii sunt 2, 11, 20,
101, 110, 200. Folosind acelaşi algoritm, se generează numere cu cifrele 0, 1, 2
şi 3 care au suma cifrelor egală cu 4. Care va fi al 7-lea număr din această
generare?
a. 130
b. 301
c. 220

19
Backtracking Variante 2009

d. 103

87. În câte dintre permutările elementelor mulţimii {‘I’,’N’,’F’,’O’} vocala ‘I’ apare
pe prima poziţie?
a. 1
b. 24
c. 6
d. 12

88. Un elev realizează un program care citeşte o valoare naturală pentru o

variabilă n şi apoi afişează în fişierul [Link], pe prima linie, valoarea lui n,
apoi toate permutările mulţimii {1,2,...,n}, câte o permutare pe câte o linie a
fişierului. Rulând programul pentru n=3, fişierul va conţine cele 7 linii alăturate.
Dacă va rula din nou programul pentru n=4, ce va conţine a 8-a linie din fişier?

3
321
312
231
213
132
123

a. 2134
b. 2143
c. 3421
d. 3412

89. Un program citeşte o valoare naturală nenulă pentru n şi apoi generează şi

afişează, în ordine crescătoare lexicografic, toate combinaţiile formate din n cifre
care aparţin mulţimii {0,1}. Astfel, pentru n=2, combinaţiile sunt afişate în
următoarea ordine: 00, 01, 10, 11. Dacă se rulează acest program şi se citeşte
pentru n valoarea 9, imediat după combinaţia 011011011 va fi afişată
combinaţia:
a. 011100100
b. 011011100
c. 011011011
d. 011100000

90. Un program citeşte o valoare naturală nenulă pentru n şi apoi generează şi

afişează, în ordine descrescătoare lexicografic, toate combinaţiile de n cifre care
aparţin mulţimii {0,1}. Astfel, pentru n=2, combinaţiile sunt afişate în următoarea

20
Backtracking Variante 2009

ordine: 11, 10, 01, 00. Dacă se rulează acest program şi se citeşte pentru n
valoarea 8, imediat după combinaţia 10101000 va fi afişată combinaţia:
a. 01010111
b. 10100111
c. 10101001
d. 10100100

91. Se generează, utilizând metoda bactracking, cuvintele cu exact 3 litere din

mulţimea {a,x,c,f,g}. Dacă primele patru cuvinte generate sunt, în ordine, aaa,
aax, aac, aaf, scrieţi ultimele trei cuvinte care încep cu litera a, în ordinea în care
vor fi generate.

92. Utilizând metoda backtracking se generează toate submuţimile nevide ale

mulţimii {3,6,2,5}. Primele şase submulţimi generate sunt, în ordine: {3}, {3,6},
{3,6,2}, {3,6,2,5}, {3,6,5}, {3,2}. Care sunt, în ordinea obţinerii, ultimele trei
submulţimi, generate după această regulă?

93. Se utilizează metoda backtracking pentru a genera toate cuvintele formate

din două litere distincte din muţimea {w,x,z,y} astfel încât niciun cuvânt să nu
înceapă cu litera x şi niciun cuvânt să nu conţină litera w lângă litera z. Cuvintele
vor fi generate în ordinea wx, wy, zx, zy, yw, yx, yz. Folosind aceeaşi metodă
se generează toate cuvintele de două litere distincte din mulţimea {w,x,z,y,t}
astfel încât niciun cuvânt să nu înceapă cu litera x şi niciun cuvânt să nu conţină
litera w lângă litera z. Care sunt a treia şi a patra soluţie generată?

94. Aplicând metoda backtracking pentru a genera toate permutările celor n

elemente ale unei mulţimi, o soluţie se memorează sub forma unui tablou
unidimensional x1,x2,…,xn. Dacă sunt deja generate valori pentru componentele
x1,x2,…,xk-1, iar pentru componenta curentă, xk (1<k<n), a fost găsită o
valoare convenabilă, atunci se încearcă alegerea
a. unei noi valori pentru componenta xk-1
b. unei valori pentru componenta xk+1
c. unei noi valori pentru componenta xk
d. unei noi valori pentru componenta x1

21