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

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

10 grile din Complexitate, Sortare, Subprograme, 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, unde $n$ este număr natural ($1 \le n \le 10^9$). Care dintre următoarele afirmații sunt adevărate?

a) Pentru $n = 1024$, se afișează $11$.
b) Pentru $n = 1$, se afișează $0$, bucla While neexecutându-se.
c) Pentru $n = 1000$, se afișează $10$.
d) Numărul de iterații este de ordinul $\Theta(\log n)$.

Răspunsuri corecte: a), c), d)

Valoarea afișată este numărul de cifre ale lui $n$ în baza $2$, $\lfloor \log_2 n \rfloor + 1$: $10$ pentru $1000$, $11$ pentru $1024=2^{10}$ și $1$ (nu $0$) pentru $n=1$, bucla executându-se o dată.

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

a) $f(7, 0)$ returnează $0$, deoarece al doilea argument este nul.
b) Apelul $f(18, 12)$ generează exact $2$ autoapeluri.
c) $f(12, 18)$ returnează $6$.
d) $f(a, b) = f(b, a)$ pentru orice $a$, $b$ din domeniu.

Răspunsuri corecte: b), c), d)

Este algoritmul lui Euclid, deci $f(a,b)$ este cel mai mare divizor comun: $f(12,18)=6$ și cmmdc-ul este simetric (dacă $a<b$, primul pas doar inversează argumentele). $f(18,12)$ apelează $f(12,6)$, apoi $f(6,0)$: două autoapeluri. $f(7,0)$ returnează $a=7$.

3. Câte șiruri binare de lungime $6$ conțin exact două cifre de $1$, care nu sunt vecine?

a) $5$
b) $12$
c) $15$
d) $10$

Răspunsuri corecte: d)

Sunt $\binom{6}{2}=15$ alegeri pentru pozițiile celor doi de $1$, dintre care $5$ sunt poziții vecine: $15-5=10$. Echivalent, $\binom{6-2+1}{2}=\binom{5}{2}=10$.

4. Se consideră algoritmul $b(x)$, unde $x$ este număr natural ($0 \le x \le 10^9$), iar $\&$ este operatorul ȘI pe biți. Ce returnează $b(200)$?

a) $8$
b) $4$
c) $5$
d) $3$

Răspunsuri corecte: d)

$x\ \&\ (x-1)$ șterge cel mai din dreapta bit $1$ al lui $x$, deci $b$ numără biții egali cu $1$. $200=11001000_{(2)}$ are $3$ biți de $1$.

5. Se interclasează două șiruri sortate crescător, $a$ cu $m$ elemente și $b$ cu $n$ elemente ($m, n \ge 1$), comparând la fiecare pas elementele curente, până când unul dintre șiruri se epuizează; restul celuilalt se copiază fără comparații.

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

a) Pentru $a = (1, 4, 6)$ și $b = (2, 3, 7)$ se efectuează $6$ comparații.
b) Pentru $a = (1, 2, 3)$ și $b = (10, 20)$ se efectuează $3$ comparații.
c) Numărul de comparații poate fi mai mic decât $\min(m, n)$.
d) Numărul de comparații este cel mult $m + n - 1$.

Răspunsuri corecte: b), d)

Fiecare comparație trimite un element în rezultat; după epuizarea unui șir nu se mai compară. Pentru $(1,2,3)$ și $(10,20)$: $3$ comparații. Pentru $(1,4,6)$ și $(2,3,7)$: $5$ comparații ($1,2,3,4,6$ sunt plasate prin comparații, $7$ se copiază). Un șir trebuie epuizat, deci sunt cel puțin $\min(m,n)$ comparații și cel mult $m+n-1$.