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

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

10 grile din Șiruri de caractere, Programare dinamică, 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. Algoritmul $c(s, n)$ înlocuiește fiecare literă mică a șirului $s$ ($1 \le n \le 100$) cu litera aflată cu $3$ poziții mai departe în alfabetul englez ($26$ de litere), circular: după `z` urmează `a`.

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

a) Aplicând de $9$ ori algoritmul $c$, fiecare literă se deplasează cu $1$ poziție.
b) Aplicând de $26$ de ori algoritmul $c$ pe un șir, se obține șirul inițial.
c) $c$ transformă `zebra` în `cehud`, fiecare literă avansând cu $3$ poziții.
d) $c$ transformă `xyz` în `abc`.

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

Poziția literei (de la $0$) devine $(p+3) \operatorname{MOD} 26$. `zebra` devine `cheud`. $26$ de aplicări deplasează cu $78 \equiv 0 \pmod{26}$ — identitate. $9$ aplicări deplasează cu $27 \equiv 1 \pmod{26}$ poziții.

2. Un poligon convex are $10$ vârfuri. Care dintre următoarele afirmații sunt adevărate?

a) Numărul de triunghiuri cu vârfurile printre vârfurile poligonului este $120$.
b) Poligonul are $35$ de diagonale.
c) Numărul de diagonale care pleacă dintr-un vârf este $8$.
d) Numărul de segmente care unesc două vârfuri (laturi și diagonale) este $90$.

Răspunsuri corecte: a), b)

Segmentele dintre vârfuri sunt $\binom{10}{2}=45$, dintre care $10$ laturi, deci $35$ de diagonale; dintr-un vârf pleacă $10-3=7$ diagonale. Triunghiurile: $\binom{10}{3}=120$.

3. Se consideră secvența de mai jos, unde $n$ este număr natural ($1 \le n \le 10^{12}$). Care dintre următoarele afirmații sunt adevărate?

a) Pentru $n = 50$, se afișează $7$, deoarece $7^2 = 49 \le 50$.
b) Numărul de iterații ale buclei While este de ordinul $\Theta(\sqrt{n})$.
c) Numărul de iterații ale buclei While este de ordinul $\Theta(\log n)$.
d) Pentru $n = 100$, bucla While se execută de $11$ ori, ultima dată cu $i = 11$.

Răspunsuri corecte: b)

Bucla continuă cât timp $i^2 \le n$, deci se oprește la primul $i$ cu $i^2>n$: pentru $n=50$, $i=8$ ($7^2=49 \le 50$). Pentru $n=100$ se execută de $10$ ori ($i=1,\dots,10$). Numărul de pași este $\lfloor\sqrt{n}\rfloor$, adică $\Theta(\sqrt{n})$.

4. Se consideră algoritmul $u(s, n)$, unde $s$ este un șir de $n$ litere mici ($1 \le n \le 1000$). Care dintre următoarele afirmații sunt adevărate?

a) Pentru $s$ = `abc`, $u$ returnează $3$.
b) Pentru $s$ = `aabb`, $u$ returnează $0$.
c) În cazul cel mai defavorabil, algoritmul are complexitatea timp $\Theta(n)$.
d) Pentru $s$ = `alabala`, $u$ returnează $4$.

Răspunsuri corecte: b), d)

$u$ returnează poziția primului caracter care apare o singură dată în șir, sau $0$ dacă nu există: în `alabala` este `b`, pe poziția $4$, iar în `abc` este `a`, pe poziția $1$. Pentru fiecare $i$ se poate parcurge tot șirul, deci cazul cel mai defavorabil este $\Theta(n^2)$.

5. Un arbore binar cu $7$ noduri și rădăcina $1$ este memorat prin vectorii $st = (2, 4, 6, 0, 0, 0, 0)$ și $dr = (3, 0, 7, 5, 0, 0, 0)$ (fiul stâng, respectiv drept, al fiecărui nod; $0$ dacă lipsește).

Se consideră algoritmul $f(x)$. Care dintre următoarele afirmații sunt adevărate?

a) $f(1)$ returnează $3$.
b) $f(2)$ returnează $2$, câte unu pentru nodurile $4$ și $5$.
c) $f(x)$ returnează numărul de frunze ale subarborelui cu rădăcina $x$.
d) $f(3)$ returnează $3$, numărul de noduri ale subarborelui cu rădăcina $3$.

Răspunsuri corecte: a), c)

Nodul $1$ are fiii $2$ și $3$, nodul $2$ doar fiul stâng $4$, nodul $4$ doar fiul drept $5$, iar nodul $3$ are fiii $6$ și $7$. $f$ întoarce $1$ pentru o frunză și adună rezultatele fiilor, deci numără frunzele, nu toate nodurile: $f(2)=1$ (frunza $5$), $f(3)=2$ (frunzele $6$ și $7$), $f(1)=3$.