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

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

10 grile din Căutare, Backtracking, 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. Se consideră algoritmul $c(v, n, x)$, unde $v$ are $n$ elemente ($1 \le n \le 1000$) și poziția $n + 1$ a vectorului este disponibilă. Care dintre următoarele afirmații sunt adevărate?

a) Pentru $v = (4, 2, 9)$ și $x = 9$, $c$ returnează $3$.
b) Pentru ca algoritmul să fie corect, șirul trebuie să fie sortat.
c) Dacă $x$ nu apare în $v[1..n]$, $c$ returnează $n + 1$.
d) Dacă $x$ apare de mai multe ori, $c$ returnează ultima poziție pe care apare.

Răspunsuri corecte: a), c)

Este căutarea secvențială cu santinelă: copia lui $x$ de pe poziția $n+1$ garantează oprirea buclei fără test de depășire. Se returnează prima apariție, iar $n+1$ semnalează că $x$ lipsește. Ordinea elementelor nu contează.

2. Care dintre următoarele egalități între scrieri în baze de numerație sunt adevărate?

a) $45_{(10)} = 2E_{(16)}$
b) $101101_{(2)} = 45_{(10)}$
c) $45_{(10)} = 1200_{(3)}$
d) $45_{(10)} = 55_{(8)}$

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

$101101_{(2)}=32+8+4+1=45$; $55_{(8)}=40+5=45$; $2E_{(16)}=32+14=46$ (corect ar fi $2D$); $1200_{(3)}=27+2 \cdot 9=45$.

3. Un algoritm backtracking generează, în ordine lexicografică, toate șirurile strict crescătoare de $3$ elemente din mulțimea $\{1, 2, 3, 4, 5\}$. Primele soluții sunt $(1,2,3)$, $(1,2,4)$, $(1,2,5)$, $(1,3,4)$.

Care este a șaptea soluție generată?

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

Răspunsuri corecte: b)

După $(1,3,4)$ urmează $(1,3,5)$, $(1,4,5)$ (a șasea), apoi $(2,3,4)$ (a șaptea). Soluțiile care încep cu $1$ sunt $\binom{4}{2}=6$.

4. Se folosește algoritmul de căutare binară $cb$ (varianta care returnează poziția sau $0$), pe un șir sortat cu $n$ elemente. Care dintre următoarele afirmații sunt adevărate?

a) Pentru $n = 1000$, bucla While se execută de cel mult $10$ ori.
b) Pentru $n = 1023$, bucla While se execută de cel mult $10$ ori.
c) Pentru $n = 100$, există valori $x$ pentru care bucla While se execută de $8$ ori.
d) Pentru $n = 7$, bucla While se execută de cel mult $3$ ori.

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

În cazul cel mai defavorabil, căutarea binară face $\lfloor \log_2 n \rfloor + 1$ iterații: $10$ pentru $n=1000$, $10$ pentru $n=1023$, $3$ pentru $n=7$ și $7$ pentru $n=100$.

5. Se consideră algoritmul $f(n)$, unde $n$ este număr natural ($0 \le n \le 30$). Care dintre următoarele afirmații sunt adevărate?

a) Numărul total de apeluri pentru $f(n)$ crește liniar cu $n$.
b) $f(6)$ returnează $11$, adică $f(5) + f(3)$.
c) $f(5)$ determină în total $15$ apeluri, inclusiv apelul inițial.
d) $f(5)$ returnează $8$.

Răspunsuri corecte: c), d)

$f(0)=f(1)=1$, apoi $f(2)=2$, $f(3)=3$, $f(4)=5$, $f(5)=8$, $f(6)=f(5)+f(4)=13$. Numărul de apeluri verifică $A(n)=1+A(n-1)+A(n-2)$ cu $A(0)=A(1)=1$: $3, 5, 9, 15$ pentru $n=2,\dots,5$ — crește exponențial, nu liniar.