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

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

10 grile din Grafuri, Sortare, Tablouri, 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ă graful neorientat cu $7$ noduri și muchiile $[1,2]$, $[1,3]$, $[2,4]$, $[3,4]$, $[4,5]$, $[6,7]$. Câte componente conexe are graful?

a) $3$
b) $2$
c) $1$
d) $6$

Răspunsuri corecte: b)

Nodurile $1,2,3,4,5$ sunt legate între ele, iar $6$ și $7$ formează o a doua componentă. Toate nodurile apar în muchii, deci nu există noduri izolate: $2$ componente.

2. Se consideră algoritmul $f(x, n)$, unde $x$ este un șir de $n$ numere întregi ($1 \le n \le 1000$). Pentru ce șir $x$ returnează algoritmul valoarea $0$?

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

Răspunsuri corecte: c)

Algoritmul numără pozițiile $i$ în care $x[i] > x[i+1]$ („coborâri”); rezultatul este $0$ exact când șirul este ordonat crescător (nu neapărat strict). Doar $(1,2,2,5,9)$ îndeplinește condiția.

3. Se consideră secvența de mai jos, aplicată unui șir $x[1], x[2], \ldots, x[n]$ de numere întregi ($2 \le n \le 100$). Pentru $x = (7, 3, 9, 4)$, ce conține șirul după executarea secvenței?

a) $(7, 7, 3, 9)$
b) $(3, 9, 4, 4)$
c) $(7, 7, 7, 7)$
d) $(4, 7, 3, 9)$

Răspunsuri corecte: c)

Parcurgerea de la stânga la dreapta suprascrie fiecare element cu valoarea deja copiată în poziția anterioară: $x[2] \leftarrow 7$, apoi $x[3] \leftarrow x[2]=7$ și așa mai departe, deci toate devin $7$. Deplasarea corectă cere parcurgerea de la $n$ spre $2$.

4. Se sortează crescător șirul $x = (4, 8, 1, 6, 3)$ prin selecția maximului: la pasul $i$ ($i = 1, 2, 3, 4$), maximul dintre $x[1], \ldots, x[n - i + 1]$ este interschimbat cu $x[n - i + 1]$, iar dacă maximul se află deja pe acea poziție nu se face nicio interschimbare.

Câte interschimbări se efectuează în total?

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

Răspunsuri corecte: b)

Pasul $1$: maximul $8$ trece pe poziția $5$ → $(4, 3, 1, 6, 8)$. Pasul $2$: maximul $6$ este deja pe poziția $4$. Pasul $3$: maximul $4$ trece pe poziția $3$ → $(1, 3, 4, 6, 8)$. Pasul $4$: $3$ este deja pe poziția $2$. În total $2$ interschimbări.

5. Se consideră algoritmul $f(x, n)$, unde $x$ este un șir de $n$ numere naturale ($2 \le n \le 1000$), aplicat pentru $x = (3, 2, 7, 10, 1, 6)$ și $n = 6$. Care dintre următoarele afirmații sunt adevărate?

a) $f(x, 6)$ returnează $19$.
b) După execuție, $d[4] = 13$.
c) După execuție, $d[3] = 7$.
d) Algoritmul are complexitatea $O(2^n)$.

Răspunsuri corecte: a), b)

$d[i]$ este suma maximă a unor elemente dintre primele $i$, fără două poziții alăturate. $d = (3, 3, 10, 13, 13, 19)$: $d[3] = 3 + 7$, $d[4] = 3 + 10$, $d[6] = 13 + 6$. O singură parcurgere, deci $O(n)$.