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

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

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

a) Pentru $n \ge 1$, $f(n)$ returnează ultima cifră (cea mai puțin semnificativă) a lui $n$.
b) Pentru $n \ge 1$, $f(n)$ returnează prima cifră (cea mai semnificativă) a lui $n$.
c) $f(4721)$ returnează $4$.
d) $f(90)$ returnează $0$.

Răspunsuri corecte: b), c)

Fiecare autoapel elimină ultima cifră, până rămâne un număr de o cifră, adică prima cifră a lui $n$: $f(4721)=4$, $f(90)=9$. Ultima cifră nu se obține: pentru $4721$ ar fi $1$.

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

a) $f(17, 5)$ returnează $2$.
b) $f(3, 7)$ returnează $0$.
c) $f(a, b) = a \operatorname{MOD} b$ pentru orice $a$, $b$ din domeniu.
d) $f(20, 4)$ returnează $5$, câtul împărțirii lui $20$ la $4$.

Răspunsuri corecte: a), c)

Se scade $b$ din $a$ cât timp $a \ge b$, deci rezultatul este restul împărțirii: $17 \to 12 \to 7 \to 2$. $f(3, 7) = 3$, iar $f(20, 4) = 0$; $5$ este câtul, nu restul.

3. Un algoritm backtracking construiește soluții $x[1], x[2], \ldots, x[k]$ cu valori din $\{1, 2, \ldots, n\}$ și acceptă o valoare pe poziția $p > 1$ doar dacă $x[p] > x[p-1]$. Pentru $n = 6$ și $k = 3$, câte soluții se afișează?

a) $56$
b) $20$
c) $120$
d) $216$

Răspunsuri corecte: b)

Condiția $x[p]>x[p-1]$ impune elemente strict crescătoare, deci fiecare soluție corespunde unei submulțimi de $3$ elemente: $C_6^3=20$. Fără condiție, cu elemente distincte, s-ar obține $A_6^3=120$ aranjamente; cu repetiție, $6^3=216$.

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

a) $f(21)$ returnează $1$.
b) $f(100)$ returnează $1$.
c) Pentru $n = 34$, bucla While se execută de $8$ ori.
d) $f(n)$ returnează $1$ pentru orice $n$ de forma $2^k$; de exemplu, $f(4) = 1$.

Răspunsuri corecte: a), c)

$b$ parcurge termenii șirului lui Fibonacci $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \ldots$ până atinge sau depășește $n$; se returnează $1$ dacă $n$ este termen al șirului. $21$ este, $100$ și $4$ nu ($1$, $2$ și $8$ sunt termeni, dar $4$ nu). Pentru $34$, $b$ ia după fiecare pas valorile $1, 2, 3, 5, 8, 13, 21, 34$ — opt pași.

5. Șirurile de caractere au pozițiile numerotate de la $1$, iar $\text{lungime}(s)$ este numărul de caractere al lui $s$. Se consideră algoritmul $f(s)$, unde $s$ este un șir de litere mici ($2 \le \text{lungime}(s) \le 1000$), iar $\text{sub}(s, i, k)$ returnează subșirul de $k$ caractere consecutive al lui $s$ care începe la poziția $i$.

Ce returnează $f(\texttt{abracadabra})$?

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

Răspunsuri corecte: c)

Se caută cel mai lung prefix propriu care este și sufix. Pentru $k$ de la $10$ la $5$ nu există potrivire; pentru $k = 4$, prefixul $\texttt{abra}$ coincide cu sufixul $\texttt{abra}$. $1$ ar corespunde doar lui $\texttt{a}$, care nu este cel mai lung.