[canonical]: https://grile.online/informatica/sortare > Pagina completă: https://grile.online/informatica/sortare > 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 Sortare · Informatică 1 grilă, în 1 set, cu explicații. ## Teaser gratuit, fără cont 1. Fie algoritmul în pseudocod de mai jos, unde `determinareMaxim` este o funcție care determină elementul cu valoare maximă dintr-un tablou unidimensional cu $n$ elemente, numit `vect`. Toate tablourile din acest algoritm sunt unidimensionale și indexate de la $0$. Tabloul `t1` are $10$ elemente, iar `t2` are $n$ elemente; ambele sunt inițializate cu valori de $0$. Ce valoare are elementul cu indexul $2026$ din `vect`, după aplicarea algoritmului, dacă $n=4000$, iar `vect` a fost inițializat (înainte de algoritm) cu `vect[i] = i % 10`, unde `x % y` reprezintă restul împărțirii lui $x$ la $y$? a) $5$ b) $4$ c) $9$ d) $3$ e) $6$ f) $7$ Răspuns corect: b) $4$ Algoritmul este o sortare prin numărare („counting sort”): primele două bucle construiesc, în `t1`, poziția finală a fiecărei valori din intervalul $0,\dots,\max$ dinaintea ultimei scăderi; a treia buclă plasează fiecare element din `vect` pe poziția lui în `t2`, obținând șirul sortat crescător; ultima buclă îl inversează, scriind rezultatul descrescător înapoi în `vect`. Cu `vect[i] = i \bmod 10` pentru $n=4000$, fiecare cifră $0,1,\dots,9$ apare de exact $400$ de ori, deci elementul de pe poziția $j$ din `t2` (sortat crescător) este $\lfloor j/400 \rfloor$. Din ultima buclă, `vect[2026]` preia `t2[n-2026-1] = t2[1973]`, adică $\lfloor 1973/400 \rfloor = 4$. 2. Fie un tablou unidimensional $v$ cu $n$ numere întregi distincte și două numere întregi $L$ și $R$, $L \le R$. Dorim să determinăm numărul de perechi de indici $(i,j)$ pentru care $L \le v[i]+v[j] \le R$. Care este complexitatea timp a algoritmului optim care rezolvă problema? a) $O(1)$ b) $O(n^2)$ c) $O(n \log n)$ d) $O(\log n)$ e) $O(n^2 \log n)$ f) $O(\sqrt{n})$ Răspuns corect: c) $O(n \log n)$ Vectorul se sortează în $O(n \log n)$, apoi se parcurge cu doi indici („two pointers”): pentru fiecare capăt al ferestrei, numărul de perechi cu suma $\le R$ minus numărul celor cu suma $\le L-1$ se determină într-o singură trecere liniară, $O(n)$. Timpul total este dominat de sortare, deci $O(n \log n)$ — sub acest prag nu se poate coborî, întrucât simpla citire a datelor este deja $\Omega(n)$, iar orice algoritm bazat pe comparații pentru acest tip de numărare are complexitatea minimă $\Omega(n \log n)$. (din capitolul Complexitate) 3. Se consideră șirul de caractere `s` care conține `primavara2026` și funcția `func` definită mai jos. Care este rezultatul apelului `func(s)`? a) $8$ b) $1$ c) $4$ d) $3$ e) $11$ f) $6$ Răspuns corect: c) $4$ Funcția parcurge șirul cu `strchr("aeiou", s[i])` și incrementează `rez` pentru fiecare caracter care este vocală; în `primavara2026` vocalele sunt `i`, `a`, `a`, `a` (cifrele nu se potrivesc cu niciun caracter din `"aeiou"`), deci `func(s)` returnează $4$. (din capitolul Șiruri de caractere) 4. Considerăm $G$ un graf neorientat cu $2026$ de noduri și $2000$ de muchii. Fie $m$ numărul minim de componente conexe și $M$ numărul maxim de componente conexe pentru un graf cu proprietățile lui $G$. Ce valoare are $M-m$? a) $1925$ b) $\text{nu se poate calcula}$ c) $63$ d) $1937$ e) $199$ f) $1999$ Răspuns corect: d) $1937$ Fiecare muchie adăugată poate reduce numărul de componente conexe cu cel mult $1$, deci numărul minim de componente se obține când graful este o pădure (fără cicluri): $m = 2026-2000 = 26$. Pentru maxim, muchiile se concentrează pe cât mai puține noduri: cel mai mic $k$ pentru care $\binom{k}{2} \ge 2000$ este $k=64$ (din $\binom{64}{2}=2016 \ge 2000$, iar $\binom{63}{2}=1953<2000$); o singură componentă cu aceste $64$ de noduri și restul de $2026-64=1962$ noduri izolate dau $M=1+1962=1963$. Rezultă $M-m = 1963-26 = 1937$. (din capitolul Grafuri) 5. Două numere naturale distincte, fiecare cu exact $3$ cifre, sunt considerate partenere dacă primele două cifre ale primului număr sunt egale cu ultimele două cifre ale celui de-al doilea număr, în aceeași ordine. Indicați numărul perechilor de numere partenere cu exact $3$ cifre, în care primul număr din pereche este strict mai mic decât al doilea. a) $8100$ b) $3996$ c) $4104$ d) $4005$ e) $8091$ f) $4095$ Răspuns corect: f) $4095$ Notăm primul număr $P=\overline{abc}$ (cu $a\in\{1,\dots,9\}$, $b,c\in\{0,\dots,9\}$) și al doilea $Q=\overline{dab}$ (cu $d\in\{1,\dots,9\}$), astfel încât ultimele două cifre ale lui $Q$ sunt exact $a$ și $b$. Alegerile libere ale lui $a,b,c,d$ dau $9\cdot10\cdot10\cdot9=8100$ perechi $(P,Q)$; dintre acestea, $P=Q$ doar când $a=b=c=d$ ($9$ cazuri), deci rămân $8091$ perechi cu numere distincte. Comparând $Q-P = 100d-90a-9b-c$: dacă $d>a$, atunci $100d\ge100a+100$, deci $Q-P\ge10a+100-9b-c\ge10+100-81-9=20>0$ — $PQ$ mereu — niciun caz favorabil. Dacă $d=a$, condiția devine $10a>9b+c$; numărând direct triplele $(a,b,c)$ care o satisfac se obțin $495$ de perechi suplimentare. În total, $3600+495=4095$ de perechi cu $P