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

> Pagina completă: https://grile.online/informatica/subiecte/model-admitere-ubb-cluj-mate-info-103
> 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ă #103

10 grile din Expresii, Algoritmi elementari, Arbori binari, 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ă secvența de mai jos, aplicată unui șir $x[1], x[2], \ldots, x[n]$ de numere întregi ($1 \le n \le 100$). Ce se afișează pentru $x = (4, 9, 1, 4, 7, 2)$ și $n = 6$?

a) $2$
b) $3$
c) $4$
d) $1$

Răspunsuri corecte: a)

Se numără elementele strict mai mari decât primul, $4$: doar $9$ și $7$. Al doilea $4$ nu este strict mai mare, deci se afișează $2$.

2. Se consideră algoritmul $f(a, b)$, unde $a$ și $b$ sunt numere naturale ($1 \le a, b \le 10^4$). Care dintre următoarele afirmații sunt adevărate?

a) $f(12, 18)$ returnează $4$.
b) $f(7, 14)$ returnează $1$, singurul divizor comun fiind $1$.
c) $f(a, b) = 1$ dacă și numai dacă $(a, b) = 1$.
d) $f(a, a) = a$ pentru orice $a$; de exemplu, $f(10, 10) = 10$.

Răspunsuri corecte: a), c)

Algoritmul numără divizorii comuni ai lui $a$ și $b$, adică divizorii lui $(a, b)$. $(12, 18) = 6$ are divizorii $1, 2, 3, 6$; $(7, 14) = 7$ are $2$ divizori; $10$ are $4$ divizori, deci $f(10, 10)=4$, nu $10$. Singurul divizor comun este $1$ exact când $a$ și $b$ sunt prime între ele.

3. Se consideră algoritmul de căutare binară de mai jos, apelat pentru șirul ordonat $x = (4, 10, 15, 21, 30, 42, 57, 63)$, cu $n = 8$. Care dintre următoarele afirmații sunt adevărate?

a) $f(x, 8, 42)$ returnează $6$ după $2$ execuții ale corpului buclei.
b) $f(x, 8, 5)$ returnează $1$.
c) Apelul $f(x, 8, 63)$ execută corpul buclei While de $4$ ori.
d) $f(x, 8, 4)$ returnează $1$ după o singură execuție a corpului buclei.

Răspunsuri corecte: a), c)

Pentru $42$: $m = 4$ ($21 < 42$), $m = 6$ — găsit. Pentru $63$: $m = 4$, $6$, $7$, $8$ — patru pași. Pentru $5$: $m = 4$, $2$, $1$, apoi $st > dr$ și se returnează $0$. Pentru $4$: $m = 4$, $2$, $1$ — trei pași.

4. Operatorii $\&$, $|$, $\oplus$, $\ll$ și $\gg$ sunt, respectiv, ȘI, SAU, SAU-exclusiv pe biți, deplasarea la stânga și deplasarea la dreapta pe biți, aplicați numerelor naturale. Care dintre următoarele afirmații sunt adevărate?

a) $(1 \ll 10) - 1 = 1024$
b) $5 \ll 3 = 40$
c) $100 \gg 2 = 25$
d) $(7 \oplus 2) \ll 1 = 12$

Răspunsuri corecte: b), c)

$x \ll k = x\cdot 2^k$, deci $5 \ll 3=40$; $x \gg k = x \operatorname{DIV} 2^k$, deci $100 \gg 2=25$. $7 \oplus 2 = 111_{(2)} \oplus 010_{(2)} = 101_{(2)} = 5$, iar $5 \ll 1=10$. $(1 \ll 10)-1=1023$.

5. Un arbore cu rădăcină are $8$ noduri și este memorat prin vectorul de tați $t = (4, 4, 0, 3, 3, 5, 5, 1)$ ($t[i]$ este tatăl nodului $i$, iar $t[i] = 0$ pentru rădăcină). Înălțimea este numărul de muchii de pe cel mai lung lanț de la rădăcină la o frunză, iar rădăcina se află pe nivelul $0$.

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

a) Arborele are $4$ frunze.
b) Nodul $5$ are $2$ fii.
c) Înălțimea arborelui este $4$.
d) Nodul $1$ se află pe nivelul $1$.

Răspunsuri corecte: a), b)

Rădăcina este $3$, cu fiii $4$ și $5$; $4$ are fiii $1$ și $2$, $5$ are fiii $6$ și $7$, iar $1$ are fiul $8$. Frunzele sunt $2, 6, 7, 8$. Cel mai lung lanț este $3 - 4 - 1 - 8$, deci înălțimea este $3$, iar nodul $1$ este pe nivelul $2$.