[canonical]: https://grile.online/informatica/subiecte/model-admitere-mateinfo-ub-081

> Pagina completă: https://grile.online/informatica/subiecte/model-admitere-mateinfo-ub-081
> 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 MateInfo UB · Informatică #081

10 grile din Complexitate, Căutare, Arbori binari, cu explicații. Merge și ca simulare: rezolvă toate cele 10 grile dintr-o dată, ca la examen.

Original, în stilul admitere MateInfo UB

## Teaser gratuit, fără cont

1. Câte frunze are un arbore binar plin (toate nivelurile complete) cu $15$ noduri?

a) $16$
b) $6$
c) $4$
d) $8$
e) $15$
f) $7$

Răspuns corect: d) $8$

Un arbore binar plin cu $15=2^4-1$ noduri are $4$ niveluri, iar ultimul are $2^3=8$ noduri.

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

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

Răspuns corect: e) `4`

Bucla avansează până întâlnește valoarea $5$, aflată pe poziția $4$ (indexare de la $0$).

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

`while(n>0) { s=s+n%10; n=n/10; }`

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

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

Bucla face câte un pas pentru fiecare cifră, iar $n$ are aproximativ $\log_{10} n$ cifre.

4. Un arbore binar cu nodurile $1..7$ este memorat prin vectorii `st` și `dr` (fiul stâng și fiul drept, $0$ = lipsă). Ce afișează programul?

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

Răspuns corect: a) `4 2 5 1 6 3 7`

Funcția afișează în inordine (stânga, rădăcină, dreapta): subarborele lui $2$ dă $4\ 2\ 5$, apoi $1$, apoi $6\ 3\ 7$.

5. Vectorul `v` este ordonat descrescător, dar i se aplică o căutare binară scrisă pentru vectori crescători. Ce afișează secvența alăturată?

a) `3`
b) `2`
c) `-1`
d) `4`
e) `0`
f) `1`

Răspuns corect: c) `-1`

Primul mijloc este poziția $2$ ($12$); cum $12>9$, se păstrează stânga (`dr`$=1$). Apoi mijlocul $0$ ($20>9$) dă `dr`$=-1$ și bucla se oprește: $9$ există pe poziția $3$, dar nu e găsit.