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

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

10 grile din Subprograme, Grafuri, Complexitate, 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 $s(v, n)$, unde $v$ este un șir de $n$ numere naturale $v[1], \dots, v[n]$ ($0 \le n \le 100$). Fie $v = (3, 8, 5, 6, 2)$. Care dintre următoarele afirmații sunt adevărate?

a) $s(v, 5)$ returnează $16$.
b) $s(v, n)$ calculează suma elementelor aflate pe poziții pare.
c) Dacă toate elementele lui $v$ sunt impare, $s(v, n)$ returnează $0$.
d) $s(v, 3)$ returnează $8$.

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

Algoritmul adună elementele cu valoare pară dintre primele $n$: $8+6+2=16$, iar pentru primele trei, doar $8$. Pozițiile pare ar da $8+6=14$ — testul este pe valoare, nu pe indice. Fără valori pare, niciun termen nu se adună.

2. Câte grafuri neorientate distincte (fără bucle și fără muchii multiple) se pot construi pe mulțimea de noduri $\{1, 2, 3, 4\}$? Două grafuri sunt distincte dacă diferă prin cel puțin o muchie.

a) $6$
b) $4096$
c) $64$
d) $16$

Răspunsuri corecte: c)

Există $\binom{4}{2}=6$ muchii posibile, iar fiecare poate fi prezentă sau nu: $2^6=64$ de grafuri.

3. Se consideră graful neorientat cu $7$ noduri și muchiile $[1,2]$, $[1,5]$, $[2,3]$, $[2,6]$, $[5,6]$, $[3,4]$, $[6,7]$, $[4,7]$. Se parcurge graful în lățime (BFS) pornind din nodul $1$, vecinii fiecărui nod fiind vizitați în ordine crescătoare.

Care este ordinea de vizitare?

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

Răspunsuri corecte: d)

Din $1$ se pun în coadă $2$, $5$; din $2$: $3$, $6$; din $5$ nimic nou; din $3$: $4$; din $6$: $7$. Ordinea este $1, 2, 5, 3, 6, 4, 7$.

4. Se inserează, în ordine, valorile $40, 25, 60, 15, 30, 70, 65, 67, 20, 10$ într-un arbore binar de căutare inițial vid (valorile mai mici merg în subarborele stâng).

Care este înălțimea arborelui obținut (numărul de muchii de pe cel mai lung drum rădăcină–frunză)?

a) $3$
b) $4$
c) $5$
d) $9$

Răspunsuri corecte: b)

$67$ se inserează pe drumul $40 \to 60 \to 70 \to 65$, ca fiu drept al lui $65$: drumul $40\text{-}60\text{-}70\text{-}65\text{-}67$ are $4$ muchii. Pe partea stângă, $20$ și $10$ ajung fiii lui $15$, la adâncimea $3$.

5. Se consideră recurențe pentru timpul de execuție $T(n)$ al unor algoritmi recursivi, cu $T(1)$ constant. Care dintre următoarele afirmații sunt adevărate?

a) $T(n) = T(n/2) + 1$ are soluția $\Theta(\log n)$.
b) $T(n) = 2T(n-1) + 1$ are soluția $\Theta(n^2)$.
c) $T(n) = 2T(n/2) + n$ are soluția $\Theta(n \log n)$.
d) $T(n) = T(n-1) + n$ are soluția $\Theta(n \log n)$.

Răspunsuri corecte: a), c)

$T(n)=T(n/2)+1$ este recurența căutării binare, cu soluția $\Theta(\log n)$, iar $T(n)=2T(n/2)+n$ este recurența sortării prin interclasare, cu soluția $\Theta(n \log n)$. $T(n)=T(n-1)+n$ se desface în $n+(n-1)+\dots+1=\Theta(n^2)$. $T(n)=2T(n-1)+1$ se dublează la fiecare nivel: $2^n-1$, deci $\Theta(2^n)$.