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

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

10 grile din Tablouri, Șiruri de caractere, Grafuri, 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 $f(v, n)$, unde $v$ este un șir de $n$ numere întregi $v[1], \dots, v[n]$ ($1 \le n \le 1000$). Care dintre următoarele afirmații sunt adevărate?

a) Pentru $v = (4, 7, 1, 9, 3)$, $f(v, 5)$ returnează $4$.
b) Dacă valoarea maximă apare de mai multe ori, $f$ returnează poziția primei apariții.
c) Pentru $v = (5, 5, 5)$, $f(v, 3)$ returnează $3$, poziția ultimei apariții a maximului.
d) Cu $v[i] \ge m$ în loc de $v[i] > m$, pentru $v = (2, 8, 8, 1)$ se returnează $3$.

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

Algoritmul returnează poziția maximului. Cu comparația strictă, o valoare egală cu maximul curent nu mai actualizează poziția, deci rămâne prima apariție: pentru $(5,5,5)$ se returnează $1$. Cu $\ge$ se reține ultima apariție: $3$ pentru $(2,8,8,1)$.

2. Câte componente conexe are graful neorientat cu $10$ noduri și muchiile $[1,4]$, $[2,5]$, $[4,7]$, $[3,8]$, $[5,9]$, $[8,10]$?

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

Răspunsuri corecte: c)

Componentele sunt $\{1,4,7\}$, $\{2,5,9\}$, $\{3,8,10\}$ și nodul izolat $\{6\}$: $4$ componente. Cu $10$ noduri și $6$ muchii, fără cicluri, numărul lor este $10-6=4$.

3. Se consideră algoritmul $r(v, n)$, care modifică șirul $v[1], \dots, v[n]$ ($2 \le n \le 1000$). Care dintre următoarele afirmații sunt adevărate?

a) Pentru $v = (1, 2, 3, 4)$, după trei apeluri succesive $r(v, 4)$ se obține $v = (3, 4, 1, 2)$.
b) Pentru $v = (1, 2, 3, 4)$, după un apel $r(v, 4)$ se obține $v = (2, 3, 4, 1)$.
c) După $n$ apeluri succesive $r(v, n)$, șirul revine la forma inițială.
d) Dacă bucla For ar parcurge indicii descrescător, de la $n-1$ la $1$, rezultatul unui apel ar fi același.

Răspunsuri corecte: b), c)

Un apel rotește șirul cu o poziție spre stânga; după trei rotiri, $(1,2,3,4)$ devine $(4,1,2,3)$, iar după $n$ rotiri revine. Parcurs descrescător, $v[n-1] \leftarrow v[n]$ se propagă spre stânga: $(4,4,4,1)$.

4. Câte numere naturale de $3$ cifre au suma cifrelor egală cu $5$?

a) $21$
b) $10$
c) $15$
d) $18$

Răspunsuri corecte: c)

Pentru $\overline{abc}$ cu $a \ge 1$, notăm $a' = a - 1$: ecuația $a' + b + c = 4$, cu $a', b, c \ge 0$, are $\binom{6}{2} = 15$ soluții. $21 = \binom{7}{2}$ ar permite și prima cifră $0$.

5. Se sortează prin interclasare (divide et impera) un șir cu $n = 2^k$ elemente ($k \ge 1$), împărțind mereu în două jumături egale. Care dintre următoarele afirmații sunt adevărate?

a) Arborele de apeluri recursive are $k + 1$ niveluri.
b) Pentru $n = 8$, se efectuează $7$ interclasări, iar fiecare prelucrează $8$ elemente.
c) Pe fiecare nivel care conține interclasări, acestea prelucrează în total $n$ elemente.
d) Numărul total de apeluri ale procedurii de sortare este $2n - 1$.

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

Dimensiunile subproblemelor sunt $n, n/2, \dots, 1$: $k+1$ niveluri. Pe fiecare nivel în afară de cel al frunzelor (subșiruri de lungime $1$, fără interclasare), subșirurile interclasate acoperă tot șirul, deci $n$ elemente. Arborele este binar complet cu $n$ frunze, deci are $2n-1$ noduri (apeluri). Pentru $n=8$ sunt $7$ interclasări (nodurile interne), dar de dimensiuni $8$, $4$, $4$, $2, 2, 2, 2$.