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

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

10 grile din Backtracking, Expresii, Tablouri, 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. În câte moduri se poate plăti suma $5$ folosind monede de valoare $1$ și $2$ (în număr nelimitat), dacă ordinea monedelor nu contează?

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

Răspunsuri corecte: a)

Se alege numărul monedelor de $2$: $0$, $1$ sau $2$, restul fiind completat cu monede de $1$ ($5 = 1 \cdot 5 = 2 + 1 \cdot 3 = 2 \cdot 2 + 1$). $8$ ar fi numărul de moduri dacă ordinea ar conta.

2. Cu metoda backtracking se generează toate cuvintele de $3$ litere distincte formate cu literele $\texttt{a}$, $\texttt{b}$, $\texttt{c}$, care nu încep cu litera $\texttt{a}$. Câte cuvinte se generează?

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

Răspunsuri corecte: c)

Cu litere distincte sunt $3! = 6$ cuvinte; cele care încep cu $\texttt{a}$ sunt $2$ ($\texttt{abc}$, $\texttt{acb}$). Rămân $4$: $\texttt{bac}$, $\texttt{bca}$, $\texttt{cab}$, $\texttt{cba}$.

3. Un arbore binar se numește strict dacă fiecare nod are fie $0$, fie $2$ fii. Înălțimea este numărul de muchii de pe cel mai lung lanț de la rădăcină la o frunză. Care dintre următoarele afirmații sunt adevărate?

a) Un arbore binar strict cu $10$ frunze are $19$ noduri.
b) Orice arbore binar strict are un număr impar de noduri.
c) Orice arbore binar cu $7$ noduri are înălțimea cel puțin $2$.
d) Orice arbore binar cu $7$ noduri are cel mult $3$ frunze.

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

Într-un arbore binar strict numărul nodurilor interne este cu $1$ mai mic decât al frunzelor: $f$ frunze dau $2f - 1$ noduri ($19$ pentru $f = 10$), număr impar. Pe înălțimea $1$ încap cel mult $3$ noduri, deci $7$ noduri cer înălțimea cel puțin $2$. Arborele plin cu $7$ noduri are $4$ frunze.

4. Se consideră algoritmul $f(n)$, unde $n$ este număr natural ($2 \le n \le 10^9$). Care dintre următoarele afirmații sunt adevărate?

a) $f(121)$ returnează $1$.
b) $f(91)$ returnează $7$.
c) Pentru $n = 97$, condiția buclei While este evaluată de exact $8$ ori.
d) $f(97)$ returnează $1$.

Răspunsuri corecte: b), d)

Bucla caută cel mai mic divizor $d \ge 2$ cu $d^2 \le n$; dacă nu există, $n$ este prim și se returnează $1$. $91=7\cdot 13$ dă $7$, $121=11^2$ dă $11$, $97$ este prim și dă $1$. Pentru $97$, condiția se evaluează pentru $d=2,3,\ldots,10$, adică de $9$ ori.

5. Se consideră algoritmul $f(x, n)$, unde $x$ este un șir de $n$ cifre $x[1], \ldots, x[n]$ ($1 \le n \le 1000$, $0 \le x[i] \le 9$), iar vectorul $fr$ are pozițiile $0, 1, \ldots, 9$. Care dintre următoarele afirmații sunt adevărate?

a) Pentru $x = (3, 1, 3, 1, 2)$, $f(x, 5)$ returnează $1$.
b) Pentru $x = (0, 0, 9)$, $f(x, 3)$ returnează $0$.
c) Pentru $x = (3, 1, 3, 1, 2)$, $f(x, 5)$ returnează $3$.
d) Pentru $x = (5)$, $f(x, 1)$ returnează $0$.

Răspunsuri corecte: b), c)

$fr$ numără aparițiile fiecărei cifre, apoi se caută cifra cea mai frecventă; din cauza lui $\ge$, la egalitate câștigă cifra mai mare. În $(3,1,3,1,2)$, $1$ și $3$ apar de câte două ori, deci rezultatul este $3$. În $(0,0,9)$ câștigă $0$ (două apariții). Pentru $(5)$, cifra $5$ are o apariție, mai mult decât $0$.