[canonical]: https://grile.online/informatica/subiecte/model-admitere-politehnica-bucuresti-078

> Pagina completă: https://grile.online/informatica/subiecte/model-admitere-politehnica-bucuresti-078
> 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 Admitere Politehnica București · Informatică #078

10 grile din Programare dinamică, Complexitate, Șiruri de caractere, cu explicații. Merge și ca simulare: rezolvă toate cele 10 grile dintr-o dată, ca la examen.

Original, în stilul Admitere Politehnica București

## Teaser gratuit, fără cont

1. Ce afișează secvența alăturată?

a) `8`
b) `3`
c) `10`
d) `11`
e) `7`
f) `9`

Răspuns corect: a) `8`

`strlen` numără caracterele fără terminatorul nul: $11$. Rezultatul este $11-3=8$.

2. Care este complexitatea timp a secvenței de mai jos, în funcție de $n$?

`for(i=1;i<=n;i=i*2) k++;`

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

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

`i` se dublează la fiecare pas, deci bucla face aproximativ $\log_2 n$ pași.

3. Ce afișează secvența alăturată?

a) `45`
b) `32`
c) `21`
d) `43`
e) `85`
f) `64`

Răspuns corect: d) `43`

$d_2=3$, $d_3=5$, $d_4=11$, $d_5=21$, $d_6=21+2\cdot11=43$.

4. Ce afișează secvența alăturată?

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

Răspuns corect: b) `3`

Litera `a` apare pe pozițiile $0,1,3,4,5,7$. Nu e urmată de `a` la pozițiile $1$, $5$ și $7$ (ultima e urmată de terminatorul nul), deci $3$.

5. Care este complexitatea timp a secvenței de mai jos, în funcție de $n$?

`for(i=1;i<=n;i++) for(j=1;j<=i;j=j*2) k++;`

a) $O(n)$
b) $O(\log^2 n)$
c) $O(n^2)$
d) $O(n\sqrt{n})$
e) $O(n^2\log n)$
f) $O(n\log n)$

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

Pentru `i` fixat, `j` se dublează, deci bucla interioară face aproximativ $\log_2 i$ pași. Suma acestora pentru $i=1..n$ este de ordinul $n\log n$.