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

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

10 grile din Arbori binari, Șiruri de caractere, 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. Ș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 ($1 \le \text{lungime}(s) \le 100$), literele comparându-se după ordinea din alfabet.

Pentru care dintre următoarele șiruri $f(s)$ returnează $1$?

a) $\texttt{aabz}$
b) $\texttt{abcz}$
c) $\texttt{zab}$
d) $\texttt{abdc}$

Răspunsuri corecte: b)

$f$ returnează $1$ exact când literele sunt în ordine strict crescătoare. $\texttt{aabz}$ are două litere egale alăturate, $\texttt{zab}$ și $\texttt{abdc}$ au o scădere; doar $\texttt{abcz}$ trece testul.

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

a) $f(4, 6)$ returnează $12$.
b) $f(5, 7)$ returnează $1$.
c) $f(9, 3)$ returnează $9$.
d) $f(8, 12)$ returnează $4$.

Răspunsuri corecte: a), c)

La ieșirea din buclă, $x$ este cel mai mare divizor comun al lui $a$ și $b$, deci se returnează $\dfrac{a}{(a, b)} \cdot b$, cel mai mic multiplu comun. $[4, 6] = 12$, $[5, 7] = 35$, $[9, 3] = 9$, $[8, 12] = 24$; $4$ este cmmdc-ul.

3. Ș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 ale alfabetului englez ($1 \le \text{lungime}(s) \le 255$), iar $\text{cod}(c)$ este codul ASCII al caracterului $c$ ($\text{cod}(\texttt{a}) = 97$).

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

a) $f(\texttt{abc})$ returnează $6$.
b) $f(\texttt{z})$ returnează $26$.
c) $f(\texttt{ab})$ și $f(\texttt{ba})$ returnează aceeași valoare.
d) $f(\texttt{aaaa})$ returnează $1$.

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

Fiecare literă contribuie cu poziția ei în alfabet ($\texttt{a} = 1$, …, $\texttt{z} = 26$): $1 + 2 + 3 = 6$, $26$, iar suma nu depinde de ordinea literelor. Pentru $\texttt{aaaa}$ se obține $4$.

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

a) $f(12321, 2)$ returnează $131$.
b) $f(505, 5)$ returnează $0$.
c) $f(1000, 1)$ returnează $1000$.
d) Pentru orice $n \ge 1$, $f(n, c)$ are mai puține cifre decât $n$.

Răspunsuri corecte: a), b)

Algoritmul elimină din $n$ toate cifrele egale cu $c$, păstrând ordinea celorlalte: $12321 \to 131$, $505 \to 0$, iar $1000$ fără cifra $1$ devine $000$, adică $0$. Dacă $n$ nu conține cifra $c$, $f(n, c) = n$, deci numărul de cifre nu scade.

5. Un șir ordonat strict crescător are $n = 15$ elemente. Pentru câte dintre cele $15$ valori ale șirului căutarea binară clasică (cu $st$, $dr$ și $m = (st + dr) \operatorname{DIV} 2$, oprită la găsire) execută corpul buclei de exact $3$ ori?

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

Răspunsuri corecte: b)

Mijloacele formează un arbore echilibrat: la pasul $1$ se testează poziția $8$, la pasul $2$ pozițiile $4$ și $12$, la pasul $3$ pozițiile $2, 6, 10, 14$, iar la pasul $4$ cele $8$ poziții impare. Deci $4$ valori.