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

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

10 grile din Backtracking, Programare dinamică, Combinatorică, 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) $f(1234)$ returnează $10$.
b) $f(9)$ returnează $9$.
c) $f(n)$ returnează numărul de cifre ale lui $n$.
d) $f(1000)$ returnează $0$.

Răspunsuri corecte: a), b)

Algoritmul adună ultima cifră la suma cifrelor lui $n$ fără ultima cifră, deci calculează suma cifrelor: $f(1234)=1+2+3+4=10$, $f(9)=9$, iar $f(1000)=1$, nu $0$. Numărul de cifre ar cere $1+f(n \operatorname{DIV} 10)$.

2. Se consideră algoritmul $cb(v, n, x)$ (căutare binară), unde $v$ este un șir sortat crescător de $n$ numere întregi ($1 \le n \le 10^5$). Fie $v = (2, 5, 8, 12, 16, 23, 38, 56, 72, 91)$ și $n = 10$.

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

a) Pentru $x = 91$, algoritmul efectuează $3$ iterații.
b) Pentru $x = 23$, algoritmul returnează $6$ după $2$ iterații ale buclei While.
c) Pentru $x = 5$, valorile comparate cu $x$ sunt, în ordine, $16$, $5$.
d) Pentru $x = 40$, algoritmul returnează $0$ după $4$ iterații.

Răspunsuri corecte: c), d)

Mijloacele sunt $m=5$ ($16$), apoi $8$ ($56$), $6$ ($23$) pentru $x=23$: $3$ iterații. Pentru $x=5$: $16$, apoi $m=2$ ($5$). Pentru $x=40$: $16, 56, 23, 38$, apoi intervalul devine vid: $4$ iterații. Pentru $x=91$: $16, 56, 72, 91$: $4$ iterații.

3. Se consideră algoritmul $w(s, n)$, unde $s$ este un șir de $n$ caractere, litere mici și spații ($0 \le n \le 255$). Fie $s$ șirul `␣␣ana␣are␣␣mere␣` (simbolul ␣ marchează un spațiu). Care dintre următoarele afirmații sunt adevărate?

a) Pentru șirul vid ($n = 0$), $w$ returnează $0$.
b) $w$ returnează $3$ pentru acest șir.
c) Pentru acest șir, numărul de spații plus $1$ este egal cu valoarea returnată de $w$.
d) Pentru `a␣b␣c`, $w$ returnează $5$.

Răspunsuri corecte: a), b)

$w$ numără începuturile de cuvânt: o literă aflată pe prima poziție sau precedată de spațiu. Șirul are $3$ cuvinte, dar $6$ spații, deci „spații + $1$” ar da $7$. `a␣b␣c` are $3$ cuvinte.

4. Se generează prin backtracking, în ordine lexicografică, permutările mulțimii $\{1, 2, 3, 4\}$. Care dintre următoarele afirmații sunt adevărate?

a) Ultima permutare generată care începe cu $2$ este $(2, 4, 1, 3)$.
b) Permutarea $(3, 1, 2, 4)$ este a $13$-a generată.
c) Permutarea $(1, 4, 3, 2)$ este a $6$-a generată.
d) Permutarea generată imediat după $(2, 4, 3, 1)$ este $(3, 1, 2, 4)$.

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

Pentru fiecare primă valoare sunt $3!=6$ permutări: cele cu $1$ ocupă pozițiile $1$–$6$ (ultima, a $6$-a, fiind $(1,4,3,2)$), cele cu $2$ pozițiile $7$–$12$ (ultima $(2,4,3,1)$), iar $(3,1,2,4)$ este prima cu $3$, a $13$-a.

5. Într-un rucsac de capacitate $5$ se pot pune obiecte, fiecare cel mult o dată, cu greutățile $2, 3, 4, 5$ și valorile $3, 4, 5, 6$. Care este valoarea totală maximă?

a) $7$
b) $6$
c) $9$
d) $8$

Răspunsuri corecte: a)

Obiectele de greutate $2$ și $3$ încap împreună și valorează $3+4=7$; orice alt obiect singur valorează cel mult $6$, iar alte perechi depășesc capacitatea.