1) Complexitatea minimă a unui algoritm care calculează numărul tuturor submulŃimilor

unei mulŃimi cu n elemente este:

a) O(n2)

b) O(2n)

c) O(n)

d) O(1)

2) Complexitatea minimă a unui algoritm care să afişeze toate submulŃimile unei mulŃimi

cu n elemente este:

a) O(n2)

b) O(2n)

c) O(n)

d) O(log2n)

3) Complexitatea minimă a unui algoritm care să calculeze numărul modurilor în care pot

fi aşezate n cărŃi pe un raft suficient de lung este:

a) O(n)

b) O(n2)

c) O(2n)

d) O(1)

4) Complexitatea minimă a unui algoritm care să afişeze toate modurile în care pot fi

aşezate n cărŃi pe un raft suficient de lung este:

a) O(n)

b) O(1)

c) O(2n)

d) O(n!)

5) Dacă ultima soluŃie afişată de către algoritmul backtracking pentru generarea tuturor

permutărilor mulŃimii {1,2,…,n} este 7,6,3,5,4,2,1, atunci următoarea soluŃie care va fi

afişată este:

a) 7,6,4,1,2,5,3

b) 7,1,2,3,4,5,6

c) 7,6,4,1,2,3,5

d) 7,6,5,3,4,2,1

6) Dacă ultima soluŃie afişată de către algoritmul backtracking pentru generarea tuturor

permutărilor mulŃimii {1,2,…,7} este 6,5,7,4,3,2,1, atunci următoarea soluŃie care va fi

afişată este:

a) 7,1,2,3,4,5,6

b) 6,7,1,2,3,4,5

c) 7,6,1,2,3,4,5

d) 6,7,5,4,3,2,1

7) Considerăm un rucsac cu ajutorul căruia putem transporta 66 kg şi 7 obiecte având

greutăŃile 23, 10, 10, 25, 38, 7 şi 5 kg, iar câştigurile obŃinute prin transportul integral al

fiecărui obiect la destinaŃie sunt 69, 10, 30, 100, 19, 14 şi 50 RON. Ştiind că din orice

obiect putem încărca şi doar o parte a sa, câştigul maxim pe care îl putem obŃine este:

a) 250.5 RON

b) 217 RON

c) 265 RON

d) 255 RON

8) Considerăm un rucsac cu ajutorul căruia putem transporta 67 kg şi 7 obiecte având

greutăŃile 10, 5, 20, 10, 20, 25 şi 21 kg, iar câştigurile obŃinute prin transportul integral

al fiecărui obiect la destinaŃie sunt 30, 40, 40, 10, 4, 50 şi 30 RON. Ştiind că din oricare

obiect putem încărca şi doar o parte a sa, câştigul maxim pe care îl putem obŃine este:

a) 114 RON

b) 170 RON

c) 280 RON

d) 163.7 RON

9) Considerăm un rucsac cu ajutorul căruia putem transporta 53 kg şi 7 obiecte având

greutăŃile 10, 5, 18, 10, 8, 20 şi 40 kg, iar câştigurile obŃinute prin transportul integral al

fiecărui obiect la destinaŃie sunt 30, 40, 36, 10, 16, 10 şi 30 RON. Ştiind că din oricare

obiect putem încărca şi doar o parte a sa, câştigul maxim pe care îl putem obŃine este:

a) 133 RON

b) 121 RON

c) 133.5 RON

d) 136.5 RON

10) Considerăm următorul algoritm, în care a este un tablou format din n numere întregi:

i � 1 j � n ┌cât timp (i≤n) şi (ai<0) execută │ i � i+1 └■ ┌cât timp (j≥1) şi (aj≥0) execută │ j � j-1 └■ ┌dacă(i>=j) │ atunci │ scrie 1 │ altfel │ scrie 0 └■

Complexitatea algoritmului dat este:

a) O(n2)

b) O(log2n)

c) O(n3)

d) O(n)

11) Un algoritm optim care să afişeze toate subşirurile crescătoare de lungime maximă ale

unui şir format din n numere foloseşte:

a) doar metoda programării dinamice;

b) doar metoda backtracking (se generează toate subşirurile şirului respectiv, iar pentru

fiecare subşir se verifică dacă este crescător şi, respectiv, maximal);

c) mai întâi metoda programării dinamice pentru a determina lungimea maximă lmax a

unui subşir crescător al şirului dat şi apoi metoda backtracking pentru a genera toate

subşirurile crescătoare de lungime lmax ale şirului considerat;

d) doar metoda Greedy.

12) StabiliŃi care dintre următoarele propoziŃii referitoare la tehnica de programare Greedy

este adevărată:

a) conduce întotdeauna la o soluŃie optimă;

b) construieşte o soluŃie element cu element şi în cazul în care valoarea elementului

curent nu verifică anumite condiŃii se renunŃă la acesta şi se revine la elementul

anterior;

c) găseşte întotdeauna o singură soluŃie a unei probleme;

d) construieşte o soluŃie element cu element, fără a reveni asupra alegerii făcute pentru

elementul curent.

13) Considerăm că într-un an sunt înscrişi n studenŃi. Pentru a afişa toate grupele ce pot fi

formate din câte p studenŃi (p≤n) din anul respectiv putem folosi algoritmul de:

a) generarea a aranjamentelor formate din p elemente ale unei mulŃimi cu n elemente;

b) generarea a permutărilor unei mulŃimi cu p elemente;

c) generarea a combinărilor formate din p elemente ale unei mulŃimi cu n elemente;

d) generarea a aranjamentelor formate din n elemente ale unei mulŃimi cu p elemente.

14) StabiliŃi care dintre următoarele metode de sortare se bazează pe tehnica de

programare Divide et Impera:

a) sortarea rapidă;

b) sortarea prin interschimbare ;

c) sortarea prin interclasare;

d) sortarea prin numărare.

15) Considerând că a este un tablou format din n numere întregi nenule şi am definit

anterior un subprogram cmmdc(x,y) care returnează cel mai mare divizor comun a două

numere întregi nenule x şi y, construim următorul subprogram:

┌subprogram F(p,u) │ ┌dacă p=u │ │ atunci │ │ F � a[p] │ │ altfel │ │ k � [(p + u)]/2 │ │ F � cmmdc(F(p,k),F(k+1,u)) │ └■ └■

Ştiind că apelul subprogramului va fi F(1, n), precizaŃi tehnica de programare utilizată în

cadrul funcŃiei F:

a) Greedy;

b) backtracking;

c) programare dinamică;

d) Divide et Impera.

16) Folosind tehnica de programare backtracking pentru a genera toate permutările mulŃimii

{1,2,...,n}, o soluŃie se memorează sub forma unui tablou unidimensional x1, x2, ..., xn. Dacă

au fost deja generate valori pentru componentele x1, x2, ..., xk-1, iar pentru componenta xk (1

<k<n) au fost deja testate toate valorile posibile şi nu a fost gasită niciuna convenabilă,

atunci:

a) se încearcă alegerea unei noi valori pentru xk-1;

b) se încearcă alegerea unei noi valori pentru x1, oricare ar fi valoarea lui k;

c) se încheie algoritmul;

d) se încearcă alegerea unei valori pentru componenta xk+1.

17) Considerăm ecuaŃia a1x1+a2x2+…+anxn=y, în care y, a1, a2,…,an sunt numere naturale.

Pentru a determina toate soluŃiile ecuaŃiei date de forma (x1, x2,...,xn), cu x1, x2,...,xn numere

naturale, se poate folosi direct algoritmul backtracking pentru:

a) generarea permutărilor;

b) descompunerea unui număr natural ca sumă de numere naturale nenule;

c) plata unei sume folosind n tipuri de bancnote;

d) generarea combinărilor.

18) StabiliŃi care dintre următorii algoritmi din teoria grafurilor se bazează pe tehnica de

programare Greedy:

a) algoritmul lui Kruskal;

b) algoritmul pentru determinarea componentelor conexe ale unui graf neorientat;

c) algoritmul lui Prim;

d) algoritmul Roy-Floyd.

19) StabiliŃi care dintre următorii algoritmi din teoria grafurilor se bazează pe metoda

programării dinamice:

a) algoritmul lui Kruskal;

b) algoritmul de parcurgere în adâncime a unui graf neorientat;

c) algoritmul lui Prim;

d) algoritmul Roy-Floyd.

20) La un ghişeu stau la coadă n persoane, numerotate cu 1,2,...,n. Cunoscând timpii de

servire t1, t2,...,tn ai celor n persoane şi ştiind că pentru a servi o persoană k trebuie servite

persoanele 1,2,...,k-1 aflate înaintea sa, trebuie să determinăm un mod de rearanjare al

persoanelor la coadă, astfel încât timpul de aşteptare al fiecărei persoane să fie minim.

StabiliŃi care dintre următoarele variante de rezolvare a acestei probleme este corectă şi are o

complexitate minimă:

a) se genereză toate modurile în care pot fi rearanjate cele n persoane la coadă şi

pentru fiecare mod de rearanjare se calculează într-un tablou timpii de servire, iar

soluŃia este tabloul minim în sens lexicografic;

b) se rearanjează persoanele în ordinea descrescătoare a timpilor de servire;

c) se genereză toate modurile în care pot fi rearanjate cele n persoane la coadă şi

pentru fiecare mod de rearanjare se calculează timpul total T de servire al celor n

persoane, iar soluŃia este tabloul pentru care valoarea lui T este minimă;

d) se rearanjează persoanele în ordinea screscătoare a timpilor de servire.