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 . Care este ultimul cuvânt generat?
a.edec b.eded c.edeb d.edde
2. 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
3. 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
4. Utilizând metoda backtracking sunt g enerate 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.143 b.145 c.129 d.154
5. 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
6. 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.dans b.snad c.snda d.nsad
7. 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.actei b.catie c.catei d.actie
8. 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.1223 b.1231 c.1213 d.1321
9. 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
10. 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.1022 b.2201 c.1031 d.1301
11. 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
12. 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?
13. 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
a.fnoi b.foni c.foin d.ifon
14. 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.3 b.2 c.5 d.4
15. 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
16. 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:
17. 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
18. 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
19. 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
20. Utilizând metoda backtracking se generează permutările cuvantului INFO. Daca primele 3 solutii generate sunt : FINO, FION, FNIO care este a 5-a solutie ?
a.FION b.FNOI c.FINO d.FNIO