[canonical]: https://grile.online/informatica/subiecte/model-admitere-ubb-cluj-mate-info-094 > Pagina completă: https://grile.online/informatica/subiecte/model-admitere-ubb-cluj-mate-info-094 > 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ă #094 10 grile din Complexitate, Sortare, Șiruri de caractere, 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ă secvența de mai jos, unde $n$ este număr natural ($1 \le n \le 10^4$). Care dintre următoarele afirmații sunt adevărate? a) Numărul de execuții ale instrucțiunii $c \leftarrow c + 1$ este de ordinul $\Theta(n \log n)$. b) Pentru $n = 10$, se afișează $55$. c) Pentru $n = 10$, instrucțiunea $c \leftarrow c + 1$ se execută de $100$ de ori. d) Numărul de execuții ale instrucțiunii $c \leftarrow c + 1$ este de ordinul $\Theta(n^2)$. Răspunsuri corecte: b), d) Pentru fiecare $i$, bucla interioară face $n-i+1$ pași, deci în total $n+(n-1)+\dots+1=\frac{n(n+1)}{2}$: $55$ pentru $n=10$, ordinul $\Theta(n^2)$. 2. Se sortează $n$ numere naturale cu valori între $0$ și $k$ prin numărare: se construiește vectorul de frecvențe $f[0..k]$, apoi se scriu valorile în ordine crescătoare, fiecare de câte ori apare. Care dintre următoarele afirmații sunt adevărate? a) Metoda compară între ele elementele șirului. b) Complexitatea timp este $\Theta(n + k)$. c) Metoda este eficientă pentru $n = 10$ numere cu valori până la $10^{12}$. d) Vectorul de frecvențe are $k$ componente. Răspunsuri corecte: b) Se parcurge șirul o dată ($n$ pași) și vectorul de frecvențe o dată ($k+1$ componente, de la $0$ la $k$): $\Theta(n+k)$. Nu se fac comparații între elemente, iar pentru valori foarte mari vectorul de frecvențe devine uriaș, deși sunt doar $10$ numere. 3. Se consideră algoritmii $a(s, n)$, $b(s, n)$ și $c(s, n)$, unde $s$ este un șir de $n$ cifre ($1 \le n \le 9$), iar $cifra(x)$ este valoarea cifrei-caracter $x$. Care dintre următoarele afirmații sunt adevărate? a) $a$ returnează $452$ pentru $s$ = `0452`. b) $c$ returnează $21$ pentru $s$ = `12`. c) $c$ returnează aceeași valoare ca $a$ pentru orice $s$ din domeniu. d) $b$ returnează aceeași valoare ca $a$ pentru orice $s$ din domeniu. Răspunsuri corecte: a), b), d) $a$ aplică schema lui Horner, iar $b$ adună cifrele de la dreapta cu ponderi $1, 10, 100, \dots$ — ambele dau numărul scris în $s$. $c$ dă ponderea $10^{i-1}$ cifrei de pe poziția $i$, deci citește șirul în oglindă: pentru `12` dă $1+20=21$. 4. Problema celor $n$ regine cere așezarea a $n$ regine pe o tablă $n \times n$ astfel încât oricare două să nu se atace (pe linie, coloană sau diagonală). Soluțiile se generează prin backtracking. Care dintre următoarele afirmații sunt adevărate? a) Pentru $n = 5$ există exact $8$ soluții. b) Pentru $n = 3$ nu există nicio soluție. c) Pentru $n = 4$ există exact $2$ soluții. d) Pentru $n = 6$ există mai multe soluții decât pentru $n = 5$. Răspunsuri corecte: b), c) Numărul de soluții este $1, 0, 0, 2, 10, 4$ pentru $n = 1, \dots, 6$: pentru $n=4$ sunt $2$, pentru $n=3$ niciuna, iar pentru $n=5$ sunt $10$, mai multe decât cele $4$ pentru $n=6$. 5. Se consideră algoritmii $A(v, n)$, $B(v, n)$, $C(v, n)$ și $D(v, n)$, unde $v$ este un șir de $n$ numere întregi ($1 \le n \le 100$). Care dintre algoritmi sortează crescător orice astfel de șir? a) $A$ b) $C$ c) $B$ d) $D$ Răspunsuri corecte: a), c) $A$ fixează pe rând minimul pe poziția $i$ (sortare prin comparare directă). $B$ este metoda bulelor: după pasul $i$, ultimele $i$ poziții sunt definitive. $C$ nu compară niciodată $v[i]$ cu $v[i+1]$ la pozițiile de început, de exemplu $(2,1)$ rămâne nesortat. $D$ interschimbă când $v[i]>v[j]$ și pentru $j