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

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

10 grile din Programare dinamică, Ș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 ale alfabetului englez ($1 \le \text{lungime}(s) \le 100$).

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

a) $\texttt{infrmtc}$
b) $\texttt{nfrmtc}$
c) $\texttt{ioaia}$
d) $\texttt{nformtc}$

Răspunsuri corecte: b)

Se păstrează doar caracterele care nu sunt vocale: din $\texttt{informatica}$ rămân $\texttt{n},\texttt{f},\texttt{r},\texttt{m},\texttt{t},\texttt{c}$.

2. Variabilele întregi $a$, $b$, $c$ au valorile $a = 5$, $b = 3$, $c = 0$. Care dintre următoarele expresii au valoarea adevărat?

a) $((a - b) \operatorname{DIV} 3 = 1)$ or $(c = 1)$
b) $(a \operatorname{MOD} b = 2)$ or $(c > a)$
c) $(a > b)$ and $(c \ne 0)$
d) not $(a < b)$ and $(b \operatorname{DIV} 2 = 1)$

Răspunsuri corecte: b), d)

$c \ne 0$ este fals, deci prima conjuncție e falsă. $5 \operatorname{MOD} 3=2$ face adevărată a doua. $a<b$ este fals, negația e adevărată, iar $3 \operatorname{DIV} 2=1$. $(5-3) \operatorname{DIV} 3 = 0$ și $c \ne 1$, deci ultima e falsă.

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 ($1 \le \text{lungime}(s) \le 1000$).

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

a) $f(\texttt{aaabaaaa})$ returnează $7$.
b) $f(\texttt{aabbbbcaa})$ returnează $4$.
c) $f(\texttt{abcabcabc})$ returnează $3$.
d) $f(\texttt{zzz})$ returnează $2$.

Răspunsuri corecte: b)

Algoritmul determină lungimea celei mai lungi secvențe de caractere identice consecutive: $\texttt{bbbb}$ dă $4$; în $\texttt{abcabcabc}$ nicio literă nu se repetă consecutiv ($1$); în $\texttt{aaabaaaa}$ litera $\texttt{b}$ rupe secvența, deci rezultatul este $4$, nu $7$; $\texttt{zzz}$ dă $3$.

4. Un arbore binar are parcurgerea în inordine $(2, 5, 4, 1, 6, 8, 3, 7)$ și parcurgerea în postordine $(5, 4, 2, 8, 6, 7, 3, 1)$. Care este parcurgerea lui în preordine?

a) $(1, 2, 5, 4, 3, 6, 8, 7)$
b) $(1, 2, 4, 5, 3, 8, 6, 7)$
c) $(1, 2, 4, 5, 3, 6, 7, 8)$
d) $(1, 2, 4, 5, 3, 6, 8, 7)$

Răspunsuri corecte: d)

Rădăcina este ultima în postordine: $1$. Inordinea dă subarborele stâng $\{2, 5, 4\}$ și drept $\{6, 8, 3, 7\}$. În stânga, rădăcina $2$ nu are fiu stâng, fiul drept este $4$, iar $5$ este fiul stâng al lui $4$. În dreapta, rădăcina $3$ are fiul stâng $6$ (cu fiul drept $8$) și fiul drept $7$. Preordinea: $1, 2, 4, 5, 3, 6, 8, 7$.

5. Un rucsac are capacitatea $7$. Obiectele au greutățile $1, 3, 4, 5$ și valorile $1, 4, 5, 7$, fiecare putând fi luat cel mult o dată și nefracționat. Care dintre următoarele afirmații sunt adevărate?

a) Strategia greedy după raportul valoare/greutate obține tot valoarea maximă.
b) Valoarea maximă care încape în rucsac este $9$.
c) Dacă obiectele ar putea fi fracționate, valoarea maximă ar fi strict mai mare decât în varianta nefracționată.
d) Pentru capacitatea $8$, valoarea maximă este $12$.

Răspunsuri corecte: b), c)

Obiectele de greutate $3$ și $4$ încap exact și dau $4+5=9$; alte combinații ($5+1$: $8$; $5$ singur: $7$) sunt mai slabe. Greedy după raport ia obiectul $5$ (raport $1{,}4$), apoi $1$: $8$. Cu fracționare: $7+\frac{2}{3}\cdot4 \approx 9{,}67>9$. Pentru capacitatea $8$ optimul este $11$ ($3+5$).