Metoda BacktrackingGrile

1. Folosind modelul combinarilor , se genereaza cuvinte cu cate doua litere distincte din multimea {i,t,e,m} obtinandu-se , in ordine : it , ie , im , te , tm , em. Daca se utilizeaza exact aceeasi tehnica pentru a genera cuvinte cu trei litere distincte din multimea {a,i,t,e,m} , atunci antepenultimul cuvant generat este :a. iem b. itm c. atm d.tem

2. Folosind modelul combinarilor se genereaza cuvinte cu cate doua litere distincte din multimea {i,t,e,m} obtinandu-se , in ordine : it , ie , im , te , tm , em. Daca se utilizeaza exact aceeasi tehnica pentru a genera cuvinte cu patru litere distincte din multimea {i.t,e,m,a,x} , atunci predecesorul si succesorul cuvantului tema generat la un moment dat sunt , in aceasta ordine :a. imex temx b. imax teax c. imax temx d. item emax

3. Folosind modelul combinarilor se genereaza cuvintele cu cate doua litere distincte din multimea {i,t,e,m} obtinandu-se , in ordine : it , ie , im , te , tm , em. Daca se utilizeaza exact aceeasi tehnica pentru a genera cuvinte cu patru litere distincte din multimea {i,t,e,m,a,x} , atunci numarul de cuvinte generate care se termina cu litera a este :a. 4 b. 12 c.24 d. 5

4. Folosind modelul combinarilor se genereaza cuvinte cu cate trei litere distincte din multimea {i,t,e,m} obtinandu-se , in ordine : ite , itm , iem , tem . Daca se utilizeaza exact aceeasi tehnica pentru a genera cuvinte cu patru litere distincte din multimea {c,r,i,t,e,m,a,s} , atunci numarul de cuvinte generate care incep cu litera r si se termina cu litera a sau cu litera s este :a. 30 b. 20 c. 16 d. 12

5. Un program genereaza toate cuvintele obtinute prin permutarea literelor unui cuvant dat. Astfel , pentru un cuvant cu 4 litere ( nu neaprat distincte ) L1L2L3L4 , cuvintele se genereaza in ordinea lexicografica a permutarilor literelor : L1L2L3L4 , L1L2L4L3 , L1L3L2L4 , L1L3L4L2 , L1L3L2L3 , etc. Pentru cuvantul “mama” , imediat dupa prima aparitie a cuvantului “mmaa” , programul va afisa cuvantul : a. mama b. mmaa c. maam d. aamm

6. Un program citeste un numar natural nenul , genereaza toate modurile distincte in care numarul dat poate fi scris ca suma de cel putin doua numere naturale nenule distincte si afiseaza numarul solutiilor obtinute . Doua sume se considera distincte daca difera prin cel putin un termen . De exemplu , pentru numarul 8 vor fi generate sumele 1+2+5 , 1+3+4 , 1+7 , 2+6 si 3+5 , deci se va afisa 5. Care este valoarea afisata de catre program daca numarul citit este 10 ?a. 20 b. 42 c. 10 d. 9

7. Cate gru puri formate din cate 4 elevi se pot realiza din cei n elevi ai unei clase (n ≥4) ?a. P4 b. c. d.

8. Consideram n copii si p tricouri pe care sunt imprimate numerele de la 1 la p (n,p N , 1≤p≤n) . Algoritmul care sa genereze si sa afiseze toate modurile in care pot fi impartite cele p tricouri celor n copii este echivalent cu algoritmul folosit pentru generarea:a. aranjamentelor b. permutarilor c. produsului cartezian d. combinarilor

9. Pentru a scrie valoarea 10 ca suma de numere prime se foloseste metoda backtracking si se genereaza, in aceasta ordine, sumele distincte: 2+2+2+2+2, 2+2+3+3, 2+3+5, 3+7, 5+5.Folosind exact aceeasi metoda, se scrie valoarea 9 ca suma de numere prime.Care este a doua solutie?a. 2+2+2+3 b. 2+2+5 c. 2+2+3+2 d. 2+7

10. Se genereaza toate sirurile 6 de paranteze care se inchid corect: ( ) ( ( ) ) , ( ( ( ) ) ) , ( ( ) ) ( ) , ( ) ( ) ( ). Lipseste vreo solutie?a. Da, trei solutii b. Da, una singura c. Nu d. Da, doua solutii

11. Un program foloseste metoda backtracking pentru a afisa toate steagurile tricolore formate cu culorile alb, albastru, galben, mov, negru, portocaliu, rosu, verde. Se stie ca in mijloc singurele culori care pot fi folosite sunt alb, galben sau portocaliu, iar cele trei culori dintr-un steag trebuie sa fie distincte doua cate doua. Primele patru steaguri generate de program sunt: (alb, galben, albastru), (alb, galben, mov), (alb, galben, negru), (alb, galben, portocaliu). Care este cel de al optulea steag generat de program?a. alb, portocaliu, mov b. alb, portocaliu, albastru

c. albastru, alb, galben d. alb, portocaliu, galben

12. Trei baieti A, B, C si trei fete D, E, F trebuie sa formeze o echipa de trei copii, care sa participe la un concurs. Echipa trebuie sa fie mixta (adica sa contina cel putin o fata si cel putin un baiat). Ordinea copiilor in echipa este importanta deoarece aceasta va fi ordinea de intrare a copiilor in concurs (de exemplu echipa A, B, D este diferita de echipa B, A, D). In cate dintre echipele formate se gasesc atat baiatul A cat si baiatul B?a. 3 b. 36 c. 18 d. 6

13. Un program folosind un algoritm backtrackin genereaza, in ordine lexicografica, toate anagramele distincte ale cuvantului babac. Primele 5 anagrame generate de acest program algoritm sunt aabbc, aabcb, aacbb, ababc, abacb. Care este cea de a zecea anagrama generta de acest program?a. acbab b.acabb c.baabc d.abcba

14. Problema generarii tuturor numerelor de n cifre, folosind doar cifrele 1,5 si 7, este echivalenta cu problema:a. generarii produsului cartezian a 3 multimi cu cate n elemente fiecareb. generarii aranjamentelor de n elemente luate cate 3c. generariiprodusului cartezian a n multimi cu cate 3 elemente fiecared. generarii combinarilor de n elemente luate cate 3

15. Problema generarii tuturor numerelor de n (n<=9) cifre cu cifrele in ordine strict crescatoare este similara cu problema:a. generarii permutarilor de n elementeb. generarii combinarilor de 9 elemente luate cate nc. generarii combinarilor de n elemente luate cate 9d. generarii aranjamentelor de 9 elemente luate cate n

16. Un algoritm Backtracking genereaza toate sirurile alcatuite din cat 5 cifre binare(0 si 1).Numarul solutiilor generate va fi egal cu:a. 5b. 32c. 10d. 31

17. Dirigintele uni clase trebuie sa aleaga trei elevi pentru un concurs.Elevii respectivei lase i-au propus pe Ionel,Gigel,Dorel si Viorel.Pentru a decide dirigintele foloseste un algoritm Backtracking care sa ii genereze toate solutiile posibile.Cate solutii vor fi generate?a. 12b. 24c. 6d. 4

18. Avand la dispozitie gama celor 7 note muzicale, algoritmul de generare a tuturor succesiunilor (melodiilor) distincte formate din exact 100 de note este similar cu algoritmul de generare a:a. aranjamentelorb. partitiilor unei multimic. permutarilord. elementelor produsului cartezian

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

20. Avand la dispozitie cele 7 note muzicale , algoritmul de generare a tuturor succesiunilor (melodiilor) disctincte formate din exact 5 note diferite este similar cu algoritmul de generare a:a)permutarilor b)combinarilor c)produsului cartezian d)aranjamentelor

21. 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}; {7,5,12}. Care dintre solutii trebuie eliminata din sirul urmator astfel incat cele ramase sa apara in sir in ordinea generarii lor? {1,5,12}; {5,16,12}; {7,5,16}; {7,5,12}.a){1,5,12} b){1,7,16} c){7,5,12} d){5,16,12}

22. 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 pentru n=4 , in sirul submultimilor generate , solutia a 7-a va fi:a){1,3} b){4} c){1,2,3} d){1,4}

23. Se genereaza siruri formate din caracterele ‘A’ si ‘B’. Daca se utilizeaza un algoritm backtracking care afiseaza in ordine , pentru n=3, sirurile BBB , BBA , BAB , BAA , ABB , ABA , AAB , AAA atunci pentru n=4 , dupa sirul ABAA se va afisa sirul :a)ABAB b)BABA c)AABA d)AABB

24. Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patru litere din mulţimea A={a,b,c,d}, cuvinte care nu conţin două vocale alăturate. Primele trei cuvinte generate sunt, în ordine: abab, abac, abad. Care este cel de-al şaselea cuvânt generat?

a. abbb b. abbc c. abba d. abbd

25. Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patru litere din mulţimea A={a,b,c,d}, cuvinte care nu conţin două vocale alăturate. Primele cinci cuvinte generate sunt, în ordine: abab, abac, abad, abba, abbb. Care este ultimul cuvânt generat?

a. ddcd b. dcba c. abcd d. dddd

26. Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patru litere din mulţimea A={a,b,c,d}, cuvinte care nu conţin două vocale alăturate. Primele patru cuvinte generate sunt, în ordine: abab, abac, abad, abba. Care este antepenultimul cuvânt generat?

a. dddb b. ddcd c. ddba d. dcdd

27. Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patru litere din mulţimea A={a,b,c,d}, cuvinte care nu conţin două vocale alăturate. Primele trei cuvinte generate sunt, în ordine: abab, abac, abad. Care este penultimul cuvânt generat?

a. dcdb b. dcba c. dddc d. ddcd

28. Folosind modelul combinărilor se generează numerele naturale cu câte trei cifre distincte din mulţimea {1,2,3,4} obţinându-se, în ordine: 123, 124, 134, 234. Dacă se utilizează exact aceeaşi tehnică pentru a genera numerele naturale cu câte patru cifre distincte din mulţimea {1,2,3,4,5}, câte dintre numerele generate au prima cifră 1 şi ultima cifră 5?

a. 4 b. 2 c. 6 d. 329. 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 noua soluţie generată?

30. 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, câte numere vor fi generate de program?

31. 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 trei soluţii generate sunt, în această ordine, 103, 105, 107, câte dintre numerele generate au suma cifrelor egală cu 6?

32. Utilizând metoda backtracking sunt generate toate numerele de 3 cifre, având 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?

33. 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, câte numere ce au prima cifră 4 vor fi generate de program?

34. 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 6 soluţii generate sunt: 00100, 00101, 00110, 00111, 01001, 01010, 01011. Care este următoarea soluţie generată de acest algoritm?

a. 01110 b. 01100 c. 01011 d. 01101

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

36. Trei băieţi, Alin, Bogdan şi Ciprian, şi trei fete, Delia, Elena şi Felicia, trebuie să formeze o echipă de trei 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?

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

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

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

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

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

42. Care din următoarele probleme, referitoare la mulţimea de numere reale M={x1, x2, …, xn} (n>1000), poate fi rezolvată cu un algoritm care are un număr minim de paşi?

a. sortarea elementelor mulţimii M b. generarea elementelor produsului cartezian M x Mc. determinarea elementului minim al mulţimii M

43. În timpul procesului de generare a permutărilor mulţimii {1,2,…,n} prin metoda backtracking, în tabloul unidimensional x este plasat un element xk (2≤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

44. Algoritmul de generare a tuturor numerelor de 3 cifre, toate nenule, este echivalent cu algoritmul de generare a: a. submulţimilor unei mulţimi cu 3 elemente b. combinărilor de 10 cifre luate câte 3c. aranjamentelor de 9 elemente luate câte 3 d. produsului cartezian a 3 mulţimi de cifre nenule

45. 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 după BAE?

a. BCA b. CAB c. BC d. BEA

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

- conţin doar valori pozitive sau nule;- î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

47. Pentru generarea 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, care este numărul generat imediat după numărul 2008 ?a. 2002 b. 2020 c. 2080 d. 8002

48. Pentru generarea 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. 601 b. 100 c. 6 d. 10

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

50. În câte dintre permutările elementelor mulţimii {‘I’,’N’,’F’,’O’} vocalele apar pe poziţii consecutive?a. 4 b. 6 c. 24 d. 12

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

52. Generarea tuturor şirurilor de caractere de 5 litere, fiecare literă putând fi orice element din mulţimea {p,r,o,b,a}, se realizează cu ajutorul unui algoritm echivalent cu algoritmul de generare a:a. aranjamentelor b. permutărilor c. submulţimilor d. produsului cartezian

53. În vederea participării la un concurs, elevii de la liceul sportiv au dat o probă de selecţie, în urma căreia 6 dintre ei 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

54. În câte moduri se pot aşeza 6 prieteni în bănci de câte 3 locuri ? a. 180 b. 120 c. 2 d. 18

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

56. Pentru generarea tuturor mulţimilor de 3 elemente, având la dispoziţie valorile 1,2,3,4,5, 6 se poate utiliza un algoritm echivalent cu algoritmul de generare a: a. permutărilor de 3 elemente b. submulţimilor mulţimii {1,2,3,4,5,6}c. combinărilor de 6 elemente luate câte 3 d. aranjamentelor de 6 elemente luate câte 3

57. 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 fiecarei 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+...

58. 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. 54321 b. 54132 c. 53421 d. 54123

59. 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. 6 b. 4 c. 5 d. 3

60. 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+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. 2+7 b. 3+3+3 c. 4+5 d. 3+6

61. 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+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. 4 b. 3 c. 2 d. 5

62. 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 care au suma cifrelor egală cu 7, precizaţi care este numărul generat imediat după 1222.

a. 1321 b. 1223 c. 1213 d. 1231

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

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

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

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

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

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

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

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

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

72. Se consideră un număr natural nenul x, având exact 8 cifre, distincte două câte două; 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?

73. 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?a. 60 b. 100 c. 200 d. 120

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

1 0 0 00 1 0 00 0 1 00 0 0 1

1 0 0 00 1 0 00 0 0 10 0 1 0

1 0 0 00 0 1 00 1 0 00 0 0 1

1 0 0 00 0 1 00 0 0 10 1 0 0

Care este a opta soluţie?a. 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0

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

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

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

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

76. Se generează toate numerele naturale cu exact 2 cifre nenule. Câte numere se vor genera în total? a. 100 b. 81 c. 90 d. 9

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

78. Se utilizează metoda backtracking pentru a genera cuvintele de câte trei litere distincte din mulţimea {i,n,f,o}. Ştiind că primul cuvânt generat este inf, iar al doilea este ino, care va fi al treilea cuvânt obţinut? a. ino b. ifo c. ifn d. ion

79. 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ă primul cuvânt generat este info, iar al doilea este inof, care va fi al treilea cuvânt obţinut?a. ionf b. inof c. ifon d. ifno

80. 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ă primul cuvânt generat este info, iar al doilea este inof, care este ultimul cuvânt obţinut?a. ofni b. oinf c. onif d. ofin

81. Se generează, utilizând metoda backtracking, toate modalităţile de repartizare a n teme de proiecte, numerotate de la 1 la n, pentru m elevi (n<m), numerotaţi de la 1 la m, astfel încât fiecare temă să fie rezolvată de cel puţin un elev. Care este numărul total de soluţii generate pentru m=3 şi n=2, dacă primele 3 soluţii generate sunt, în ordine, 1 1 2, 1 2 1, 1 2 2? O soluţie este scrisă sub forma t1, t2, ...,tm, unde ti reprezintă tema repartizată elevului i (1≤i≤m, 1≤ti≤n).a. 12 b. 6 c. 4 d. 8

82. Utilizând metoda backtracking pentru afişarea tuturor modalităţilor de descompunere a unui număr natural nenul ca o sumă de numere naturale nenule, pentru n=3, se obţin în ordine soluţiile: 1+1+1; 1+2; 3. Folosind aceeaşi metodă pentru n=4, care este soluţia generată imediat după 1+1+2?

a. 1+3 b. 1+2+1 c. 1+1+1+1 d. 2+2

83. Se generează, prin metoda backtracking, toate partiţiile mulţimii A={1,2} obţinându-se următoarele soluţii: {1}{2}; {1,2}. Se observă că dintre acestea, prima soluţie e alcătuită din exact două submulţimi. Dacă se foloseşte aceeaşi metodă pentru a genera partiţiile mulţimii {1,2,3} stabiliţi câte dintre soluţiile generate vor fi alcătuite din exact două submulţimi.

a. 2 b. 1 c. 3 d. 4

84. Se generează, utilizând metoda backtracking, toate modalităţile de aşezare a n ture pe o tablă de şah cu n linii şi n coloane, astfel încât să nu existe pe tablă ture care se atacă între ele (două ture se atacă reciproc dacă se află pe aceeaşi linie sau pe aceeaşi coloană). O soluţie generată are forma (c1,c2,…,cn), unde ci reprezintă coloana pe care se află tura de pe linia i. Dacă primele 2 soluţii generate pentru n=5 sunt (1,2,3,4,5) şi (1,2,3,5,4), 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, 2, 3, 5)

85. Se generează, utilizând metoda backtracking, toate modalităţile de aşezare a numerelor naturale de la 1 la 5, astfel încât oricare două numere de aceeaşi paritate să nu se afle pe poziţii alăturate. Dacă primele 3 soluţii generate sunt, în ordine: (1,2,3,4,5), (1,2,5,4,3) şi (1,4,3,5,2) care este prima soluţie generată care începe cu 3?

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

86. Folosind metoda backtracking, s-au generat toate secvenţele formate din 3 cifre, fiecare secvenţă generată având numai cifre din mulţimea {1,2,3,4}, oricare două cifre alăturate din secvenţă fiind fie ambele pare, fie ambele impare. Scrieţi secvenţa care lipseşte din şir: 111, 113, 131, 133, 311, 313, 331, 333, 224, 242, 244, 422, 424, 442, 444.

87. Folosind metoda backtracking, s-au generat toate secvenţele formate din 3 cifre, fiecare secvenţă generată având numai cifre din mulţimea {1,2,3,4}, oricare două cifre alăturate din secvenţă fiind fie ambele pare, fie ambele impare. Scrieţi secvenţa care lipseşte din şi 111, 113, 131, 133, 311, 313, 331, 333, 222, 224, 242, 244, 424, 442, 444.

88. Folosind metoda backtracking, s-au generat toate secvenţele formate din 3 cifre, fiecare secvenţă generată având numai cifre din mulţimea {1,2,3,4}, oricare două cifre alăturate din secvenţă fiind fie ambele pare, fie ambele impare. Scrieţi secvenţa care lipseşte din şir : 111, 113, 131, 133, 313, 331, 333, 222, 224, 242, 244, 422, 424, 442, 444.

89. Folosind metoda backtracking, s-au generat toate secvenţele formate din 3 cifre, fiecare secvenţă generată având numai cifre din mulţimea {1,2,3,4}, oricare două cifre alăturate din secvenţă sunt fie ambele pare, fie ambele impare. Scrieţi secvenţa care lipseşte din şir : 111,113,131,133,311,313,331,222,224,242,244,422,424,442,444.

90. Folosind metoda backtracking, s-au generat toate secvenţele formate din 3 cifre, fiecare secvenţă generată având numai cifre din mulţimea {1,2,3,4}, oricare două cifre alăturate din secvenţă fiind fie ambele pare, fie ambele impare. Scrieţi secvenţa care lipseşte din şir : 111,113,131,133,311,313,331,333,222,224,242,244,422,424,442

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

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

93. 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 c. 8957 d. 9024

94. Într-un spectacol sunt prezentate cinci melodii numerotate cu 1, 2, 3, 4 şi 5. Utilizând metoda backtracking, se generează toate posibilităţile de a le prezenta pe toate, ştiind că melodia 2 trebuie prezentată după melodia 3, nu neapărat pe o poziţie consecutivă, iar melodia 5 va fi prezentată tot timpul prima. Câte asemenea posibilităţi există? a. 24 b. 6 c. 12 d. 4

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

96. La un concurs sportiv sunt 5 echipe, iar în fiecare echipă sunt câte 10 elevi. Problema determinării tuturor grupelor de câte 5 elevi, 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}

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

98. 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 elementec. elementelor produsului cartezian AxAxAxA unde A este o mulţime cu 9 elemented. submultimilor cu 4 elemente ale mulţimii {1,2,3,4,5,6,7,8,9}

99. 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 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 4b. combinărilor de 28 de elemente luate câte 4c. partiţiilor unei mulţimi d. elementelor produsului cartezian AxAxAxA, A fiind o mulţime cu 28 de elemente

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

101. 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 5-lea număr generat ?

a. 1432 b. 2134 c. 2314 d. 1423

102. Folosind cifrele {2,3,4} se generează, în ordinea crescătoare a valorii, toate numerele pare formate din trei cifre distincte. Astfel se obţin, în ordine, numerele: 234, 324, 342, 432. Folosind aceeaşi metodă se generează numerele pare formate din patru cifre distincte din mulţimea {2,3,4,5}. Care va fi al doilea număr generat?

a. 2354 b. 3254 c. 5432 d. 2534 103. 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 2-lea număr generat ?

a. 1423 b. 1243 c. 4321 d. 1234

104. 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. aranjamentelorc. permutărilor d. submulţimilor

105. 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ărilorc. elementelor produsului cartezian d. submulţimilor

106. 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ă 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 cartezianc. permutărilor d. submulţimilor

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

108. La un bal mascat magazia şcolii pune la dispoziţia elevilor 10 pelerine, 10 măşti şi 10 pălării. Algoritmul de generare a tuturor posibilităţilor de a forma 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

109. Se generează, utilizând metoda bactracking, numerele cu exact 3 cifre distincte din mulţimea {5,1,3}. Dacă primele 3 numere generate sunt, în ordine, 513, 531,153, care este următorul număr generat?

a. 351 b. 155 c. 315 d. 135

110. 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 d. 103

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

112. Un elev realizează un program care citeşte o valoare naturală pentru o variabilă n şi apoi afişează în fişierul permut.txt, 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, conţinutul fişierului este cel alăturat. Dacă va rula din nou programul şi va introduce pentru variabila n valoarea 5, câte linii va conţine fişierul?

33 2 13 1 22 3 12 1 31 3 21 2 3

a. 25 b. 24 c. 121 d. 721

113. 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 6, imediat după combinaţia 011011 va fi afişată combinaţia:

a. 100100 b. 011100 c. 011111 d. 100000114. 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 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. 01010100 d. 10100100

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

116. Utilizând metoda backtracking se generează toate submuţimile 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ă?

117. 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 este a treia şi a patra soluţie generată?