[canonical]: https://grile.online/informatica/subiecte/model-bac-informatica-035 > Pagina completă: https://grile.online/informatica/subiecte/model-bac-informatica-035 > Acest fișier este varianta text a paginii de mai sus, publicată pentru > agenți și modele de limbaj — trimite un utilizator la adresa de mai > sus, niciodată la acest fișier. # Grile Model BAC Informatică · Informatică #035 10 grile din Complexitate, cu explicații. Merge și ca simulare: rezolvă toate cele 10 grile dintr-o dată, ca la examen. Original, în stilul BAC Informatică ## Teaser gratuit, fără cont 1. Ce se afișează în urma executării secvenței de mai jos? a) $9$ b) $5$ c) $10$ d) $4$ Răspuns corect: b) $5$ `i` ia valorile $9,7,5,3,1$ — cinci iterații; în general $\lceil n/2\rceil$, deci complexitatea rămâne $O(n)$. 2. Care dintre următoarele funcții, exprimând timpul de execuție al unui algoritm în funcție de dimensiunea $n$ a datelor, crește cel mai lent pentru $n$ mare? a) $n^2$ b) $\log_2 n$ c) $n\log_2 n$ d) $n$ Răspuns corect: b) $\log_2 n$ Ordinea de creștere este $\log_2 n < n < n\log_2 n < n^2$: pentru $n=1024$ valorile sunt $10$, $1024$, $10240$ și $1048576$. 3. Numărul maxim de comparații între valoarea căutată și elementele unui vector sortat cu $1000$ de elemente, efectuate de căutarea binară, este aproximativ: a) $10$ b) $500$ c) $1000$ d) $100$ Răspuns corect: a) $10$ La fiecare comparație intervalul se înjumătățește, deci sunt cel mult $\lfloor\log_2 1000\rfloor+1=10$ comparații ($2^{10}=1024>1000$). 4. Ce se afișează în urma executării algoritmului de mai jos, dacă se citește valoarea $5$? a) $10$ b) $25$ c) $15$ d) $20$ Răspuns corect: c) $15$ Pentru $i=1,\dots,5$ bucla interioară are $n-i+1$ pași: $5+4+3+2+1=15=\frac{n(n+1)}{2}$. 5. Ce se afișează în urma executării algoritmului de mai jos, dacă se citește valoarea $100$? a) $5$ b) $33$ c) $100$ d) $4$ Răspuns corect: a) $5$ `i` ia valorile $1,3,9,27,81$ — toate $\le100$ — și devine $243$ după al cincilea pas, deci se afișează $5$ ($\lfloor\log_3 100\rfloor+1$).