[canonical]: https://grile.online/informatica/complexitate

> Pagina completă: https://grile.online/informatica/complexitate
> 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 Complexitate · Informatică

1 grilă, în 1 set, cu explicații.

## Teaser gratuit, fără cont

1. Fie $a$ și $b$ două valori întregi, cu $a \le b$, și $v$ un vector sortat descrescător cu $n$ elemente (numere întregi). Dorim să determinăm numărul de elemente din $v$ care sunt în intervalul $[a,b]$. Care este complexitatea temporală a algoritmului optim?

a) $O(\log^2 n)$
b) $O(n \log n)$
c) $O(1)$
d) $O(\log n)$
e) $O(n)$
f) $O(n^2)$

Răspuns corect: d) $O(\log n)$

Vectorul fiind sortat, marginile intervalului $[a,b]$ se pot localiza prin două căutări binare (una pentru fiecare capăt), iar numărul de elemente din interval rezultă direct din diferența pozițiilor găsite — complexitate $O(\log n)$.

2. O matrice rară (cu multe elemente nule) este reprezentată prin dimensiunile ei: numărul de linii și numărul de coloane (`nl` și `nc`), numărul de elemente nenule (`nn`) și un vector `term` care conține maxim $100$ de termeni nenuli caracterizați prin poziție (`lin`, `col`) și valoare (`val`).

Matricea: $$A = \begin{pmatrix} 0 & 0 & 0 & 0 & 7 \\ 2 & 0 & 0 & 1 & 0 \\ 0 & 3 & 0 & 0 & 1 \\ 0 & 4 & 0 & 0 & 9 \end{pmatrix}$$ se va reprezenta (în ordinea parcurgerii pe linii, de la stânga la dreapta) folosind variabila `mr`.

Ce va afișa secvența `printf("%d", mr.term[1].val);` (Pascal: `Write(mr.term[2].val);`)?

a) $4$
b) $3$
c) $1$
d) $2$
e) $5$
f) $7$

Răspuns corect: d) $2$

Parcurgând matricea pe linii, primii doi termeni nenuli sunt $7$ (linia $0$, coloana $4$) și $2$ (linia $1$, coloana $0$); `mr.term[1]` este al doilea termen din vector (indexare de la $0$ în C), deci `mr.term[1].val` $=2$ — aceeași valoare pe care Pascal o accesează prin `mr.term[2]` (indexare de la $1$).

(din capitolul Structuri de date)

3. Se definește $\mathrm{ARB}(n)$ un arbore binar în care: toate nodurile au $0$ sau $2$ copii; toate frunzele sunt pe același nivel; numărul de niveluri este $n$. Rădăcina este pe nivelul $1$ și are valoarea $1$. Un nod cu valoarea $x$ (care nu este frunză) are: copilul stâng $2x$; copilul drept $2x+1$.

Exemplu: $\mathrm{ARB}(3)$ conține $7$ noduri, iar $\mathrm{sum}(\mathrm{ARB}(3)) = 103$. Cât este $\mathrm{sum}(\mathrm{ARB}(5)) - \mathrm{sum}(\mathrm{ARB}(4))$?

a) $3072$
b) $2987$
c) $2869$
d) $3061$
e) $2976$
f) $3125$

Răspuns corect: b) $2987$

Construind $\mathrm{ARB}(n)$ conform regulii date, suma valorilor tuturor nodurilor de pe un nivel nou adăugat este determinată exact de acea regulă; enunțul indică $\mathrm{sum}(\mathrm{ARB}(3))=103$, iar $2987 = 29 \times 103$ este singura variantă divizibilă cu acest număr.

(din capitolul Arbori binari)

4. Care dintre următoarele expresii verifică proprietatea $|x-a| < b$ pentru $a, b, x$ întregi?

a) `I3`
b) `I2` și `I5`
c) `I4`
d) `I1`
e) `I2` și `I5`
f) `I5`

Răspuns corect: d) `I1`

`I1` (`a-b < x && x < a+b`) implementează corect conjuncția $a-b < x$ și $x < a+b$, echivalentă cu $|x-a| < b$. Celelalte fie folosesc `||` în loc de `&&` (`I2`), inversează inegalitățile (`I3`), înlănțuie incorect operatorii de comparație (`I4`), fie testează o singură margine (`I5`).

(din capitolul Expresii)

5. Un graf orientat are nodurile $1,2,3,4,5$ și arcele: $$\begin{gathered} (1,2),\quad (1,3),\quad (2,3) \\ (2,4),\quad (2,5),\quad (3,4) \\ (5,3),\quad (4,5) \end{gathered}$$

Numărul de drumuri elementare de la $1$ la $5$ este:

a) $6$
b) $3$
c) $2$
d) $5$
e) $4$
f) $1$

Răspuns corect: e) $4$

Drumurile elementare de la $1$ la $5$ sunt $1,2,5$; $1,2,4,5$; $1,3,4,5$; $1,2,3,4,5$ — în total $4$.

(din capitolul Grafuri)

## Seturi care conțin acest capitol

- [Informatică #003](https://grile.online/informatica/rezolva?set=informatica-poli-2025)