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

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

10 grile din Backtracking, Programare dinamică, Căutare, 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. Care dintre următoarele afirmații sunt adevărate?

a) $177_{(8)} = 128$
b) $1A3_{(16)} = 4 \cdot 105$
c) $110011_{(2)} = 51$
d) $2101_{(3)} = 65$

Răspunsuri corecte: c)

$110011_{(2)}=32+16+2+1=51$; $177_{(8)}=64+7\cdot8+7=127$; $1A3_{(16)}=256+10\cdot16+3=419$; $2101_{(3)}=2\cdot27+1\cdot9+0\cdot3+1=64$.

2. Pentru șirul $x = (2, 7, 1, 8, 2, 8, 1, 8)$ se construiește șirul $d$ cu $d[1] = x[1]$ și $d[i] = \max(d[i-1], x[i])$ pentru $2 \le i \le 8$. Care dintre următoarele afirmații sunt adevărate?

a) $d[3]$ este egal cu $7$.
b) $d[8]$ este egal cu $8$.
c) $d[3]$ este egal cu $1$.
d) $d[2]$ este egal cu $2$.

Răspunsuri corecte: a), b)

$d[i]$ este maximul primelor $i$ elemente: $d = (2, 7, 7, 8, 8, 8, 8, 8)$.

3. 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) Apelul $f(123)$ afișează $321123$.
b) Pentru $n \ge 1$, $f(n)$ afișează fiecare cifră a lui $n$ de două ori.
c) Apelul $f(123)$ afișează $123321$, iar $f(7)$ afișează $77$.
d) Apelul $f(505)$ afișează $505505$.

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

Prima instrucțiune Write se execută la coborârea în recursivitate (cifrele de la ultima la prima), a doua la revenire (de la prima la ultima): $f(123)$ afișează $321$, apoi $123$. Pentru $505$ se obține $505505$, iar pentru $7$, $77$. Fiecare cifră este afișată de două ori.

4. Se consideră secvența de mai jos, aplicată șirului $x = (3, 1, 4, 1, 5, 2)$, cu $n = 6$ și $k = 5$ (valorile sunt între $0$ și $k$). Care dintre următoarele afirmații sunt adevărate?

a) În punctul $P$, $fr[1] = 2$.
b) După ultima buclă, $fr[3] = 4$.
c) După ultima buclă, $fr[5] = 5$.
d) După ultima buclă, $fr[0] = 1$.

Răspunsuri corecte: a), b)

În $P$, $fr$ conține frecvențele: $fr = (0, 2, 1, 1, 1, 1)$ pentru valorile $0..5$. Ultima buclă face sume parțiale, deci $fr[v]$ devine numărul de elemente $\le v$: $fr = (0, 2, 3, 4, 5, 6)$. Astfel $fr[3] = 4$, $fr[5] = 6$, $fr[0] = 0$.

5. Se generează prin backtracking toate șirurile corecte de paranteze cu $n$ perechi (de exemplu, pentru $n = 2$: $\texttt{(())}$ și $\texttt{()()}$). Câte șiruri se generează pentru $n = 4$?

a) $14$
b) $10$
c) $16$
d) $8$

Răspunsuri corecte: a)

Numărul șirurilor corecte cu $n$ perechi este numărul lui Catalan: $1, 2, 5, 14, \ldots$, deci $14$ pentru $n=4$.