[canonical]: https://grile.online/informatica/subiecte/model-preadmitere-politehnica-bucuresti-055

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

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

Original, în stilul Preadmitere Politehnica București

## Teaser gratuit, fără cont

1. Un arbore cu $10$ noduri este memorat prin vectorul de „tați” `t` (`t[i] = 0` pentru rădăcină); `niv` este inițial nul. Ce se afișează?

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

Răspuns corect: d) `4 2`

`niv[i]` este nivelul nodului `i` (rădăcina $1$ pe nivelul $0$). Nivelurile sunt: $2,3\to1$; $4,5,6\to2$; $7,8\to3$; $9,10\to4$. Înălțimea este $4$, iar pe ultimul nivel sunt $2$ noduri.

2. Într-un arbore cu $22$ de noduri, fiecare nod care nu este frunză are exact $3$ fii. Câte frunze are arborele?

a) $15$
b) $21$
c) $8$
d) $14$
e) $7$

Răspuns corect: a) $15$

Dacă $i$ este numărul nodurilor interne, arborele are $3i$ noduri care sunt fii, plus rădăcina: $3i+1=22$, deci $i=7$ și rămân $22-7=15$ frunze.

3. Un arbore binar complet cu $100$ de noduri are toate nivelurile complet ocupate, cu excepția ultimului. Secvența de mai jos calculează numărul de niveluri ale arborelui. Ce se afișează?

a) `100`
b) `8`
c) `50`
d) `6`
e) `7`

Răspuns corect: e) `7`

Nivelurile complete au $1,2,4,8,16,32$ noduri (în total $63<100$); al șaptelea nivel adaugă până la $64$ noduri și acoperă cele $100$: $7$ niveluri ($0,\dots,6$).

4. Un arbore binar complet cu $n=20$ de noduri, numerotate pe niveluri de la $1$ la $n$, are pentru nodul $i$ fiii $2i$ și $2i+1$ (dacă există). Ce returnează apelul `h(1)`?

a) `4`
b) `6`
c) `5`
d) `20`
e) `10`

Răspuns corect: c) `5`

`h(i)` returnează numărul de noduri de pe cel mai lung drum de la `i` în jos. Nivelurile conțin nodurile $1$; $2\text{-}3$; $4\text{-}7$; $8\text{-}15$; $16\text{-}20$: $5$ niveluri.

5. Un arbore binar cu $8$ noduri este memorat prin vectorii `st` și `dr` (fiul stâng, respectiv drept, al fiecărui nod; $0$ dacă lipsește). Ce se afișează?

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

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

Coada produce parcurgerea pe niveluri: rădăcina $7$; fiii săi $3,5$; apoi fiii lor în ordine — $1$ (din $3$), $2,6$ (din $5$); apoi $8$ (din $1$) și $4$ (din $6$).