[canonical]: https://grile.online/informatica/subiecte/model-admitere-ubb-cluj-mate-info-096

> Pagina completă: https://grile.online/informatica/subiecte/model-admitere-ubb-cluj-mate-info-096
> 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 UBB Cluj Mate-Info · Informatică #096

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

Original, în stilul admitere UBB Cluj Mate-Info

## Teaser gratuit, fără cont

1. Se consideră algoritmul $g(n)$, unde $n$ este număr natural ($1 \le n \le 10^9$). Ce returnează $g(12030)$?

a) $6$
b) $12030$
c) $321$
d) $3021$

Răspunsuri corecte: d)

$g$ construiește oglinditul lui $n$: cifrele se iau de la dreapta și se adaugă în coada lui $r$. Zeroul final al lui $n$ devine un zero nesemnificativ, iar zeroul din interior se păstrează, deci rezultatul este numărul $3021$ (nu $321$).

2. Un arbore binar are rădăcina $1$. Nodul $1$ are fiul stâng $2$ și fiul drept $3$; nodul $2$ are fiii $4$ (stâng) și $5$ (drept); nodul $3$ are doar fiul drept $6$; nodul $6$ are doar fiul stâng $7$.

Care dintre următoarele afirmații sunt adevărate?

a) Parcurgerea în inordine este $4\ 2\ 5\ 1\ 3\ 7\ 6$.
b) Înălțimea arborelui (numărul de muchii de pe cel mai lung drum rădăcină–frunză) este $4$.
c) Parcurgerea în preordine este $1\ 2\ 4\ 5\ 3\ 6\ 7$.
d) Parcurgerea în postordine este $4\ 5\ 2\ 6\ 7\ 3\ 1$.

Răspunsuri corecte: a), c)

Preordine: rădăcină, stânga, dreapta; inordine: stânga, rădăcină, dreapta; postordine: stânga, dreapta, rădăcină — $4\ 5\ 2\ 7\ 6\ 3\ 1$ ($7$ înaintea lui $6$). Cel mai lung drum este $1 \text{-} 3 \text{-} 6 \text{-} 7$, cu $3$ muchii.

3. Se consideră algoritmul $f(v, n)$, unde $v$ este un șir de $n$ numere întregi ($1 \le n \le 10^5$). Fie $v = (1, 1, 2, 3, 3, 3, 5)$. Care dintre următoarele afirmații sunt adevărate?

a) După apelul $f(v, 7)$, $v[4] = 3$.
b) Algoritmul are complexitatea timp $\Theta(n^2)$.
c) $f(v, 7)$ returnează $4$.
d) Pentru șirul $(1, 2, 1)$, $f$ returnează $2$.

Răspunsuri corecte: c)

Algoritmul compactează șirul păstrând un element doar dacă diferă de ultimul păstrat: pe un șir sortat elimină duplicatele, lăsând $v[1..4]=(1,2,3,5)$, deci $v[4]=5$. Pe $(1,2,1)$ vecinii diferă mereu, deci returnează $3$. Face o singură parcurgere: $\Theta(n)$.

4. Fie $K_n$ graful neorientat complet cu $n$ noduri; un ciclu nu depinde de nodul de start și de sensul de parcurgere. Care dintre următoarele afirmații sunt adevărate?

a) $K_4$ are $4$ cicluri hamiltoniene distincte.
b) Gradul fiecărui nod din $K_n$ este $n$.
c) $K_5$ are $12$ cicluri hamiltoniene distincte.
d) $K_7$ are $21$ de muchii.

Răspunsuri corecte: c), d)

$K_n$ are $\binom{n}{2}$ muchii ($21$ pentru $n=7$), fiecare nod are gradul $n-1$, iar numărul de cicluri hamiltoniene este $\frac{(n-1)!}{2}$: $12$ pentru $n=5$ și $3$ pentru $n=4$.

5. Un arbore binar are parcurgerea în preordine `A B D G C E F` și parcurgerea în inordine `D G B A E C F`. Care este parcurgerea sa în postordine?

a) `D G B E F C A`
b) `G D B E F C A`
c) `G D E B F C A`
d) `D G B F E C A`

Răspunsuri corecte: b)

Rădăcina este `A`; în inordine, `D G B` formează subarborele stâng și `E C F` pe cel drept. În stânga, preordinea `B D G` dă rădăcina `B`, cu `D G` în stânga ei; `D` are fiul drept `G`. În dreapta, `C` are fiii `E` și `F`. Postordinea: `G D B E F C A`.