Subiecte admitere UBB Informatică 2027 — 10 grile rezolvate C++

Ce valoare returnează apelul f(2027)?

1. La fiecare pas, n % 2 este ultima cifră a lui n în baza 2, iar n /= 2 o elimină.
2. Deci funcția numără cifrele de 1 din scrierea binară a lui n.
3. $2027 = 1024 + 512 + 256 + 128 + 64 + 32 + 8 + 2 + 1$, adică $2027 = 11111101011_{(2)}$.
4. Cifrele de 1 sunt 9, deci f(2027) = 9.

A este corect: în $11111101011_{(2)}$ apar nouă cifre de 1. B = 11 este numărul total de cifre binare (lungimea scrierii), nu numărul de cifre 1. C = 4 ar fi numărul de cifre zecimale ale lui 2027. D = 8 omite unul dintre biții de 1 (de obicei $2^0$, pentru că 2027 este impar).

Ce valoare returnează apelul g(1071, 462)?

1. Funcția este algoritmul lui Euclid recursiv, deci calculează $\text{cmmdc}(a, b)$.
2. $g(1071, 462)$: $1071 \bmod 462 = 147$ → $g(462, 147)$.
3. $462 \bmod 147 = 21$ → $g(147, 21)$.
4. $147 \bmod 21 = 0$ → $g(21, 0)$, care returnează $21$.

C este corect: $1071 = 3^2 \cdot 7 \cdot 17$ și $462 = 2 \cdot 3 \cdot 7 \cdot 11$, deci cmmdc este $3 \cdot 7 = 21$. A = 7 este doar un divizor comun, nu cel mai mare. B = 42 nu divide 1071 (1071 este impar). D = 147 este un rest intermediar, nu rezultatul final.

Ce se afișează după executarea secvenței?

1. Este o singură trecere a metodei bulelor, de la stânga la dreapta.
2. $i=1$: $8 < 3$? nu. $i=2$: $1 < 8$ → interschimbare: 3 1 8 9 4 7.
3. $i=3$: $9 < 8$? nu. $i=4$: $4 < 9$ → 3 1 8 4 9 7.
4. $i=5$: $7 < 9$ → 3 1 8 4 7 9. Se afișează 3 1 8 4 7 9.

B este corect: o singură trecere duce doar maximul (9) la final. A este vectorul complet sortat, care ar necesita mai multe treceri. C este vectorul inițial, ca și cum nu s-ar face nicio interschimbare. D presupune că 1 ajunge pe prima poziție, dar el se mută doar cu un pas spre stânga, pentru că 3 nu mai este comparat a doua oară.

Ce valoare are cnt după executarea secvenței?

1. Pentru un i fixat, j ia valorile $i, i+1, \dots, n$, adică $n - i + 1$ valori.
2. Totalul este $\sum_{i=1}^{n} (n - i + 1) = n + (n-1) + \dots + 1 = \frac{n(n+1)}{2}$.
3. Pentru $n = 10$: $\frac{10 \cdot 11}{2} = 55$.

D este corect: se numără perechile $(i, j)$ cu $1 \le i \le j \le 10$. A = $10^2$ ar fi corect dacă j ar porni mereu de la 1. B = $C_{10}^2$ numără doar perechile cu $i < j$ strict (ar corespunde lui j = i + 1). C = 50 = $\frac{n^2}{2}$ este o estimare care uită că perechile cu $i = j$ (10 la număr) se adaugă integral: $\frac{100 - 10}{2} + 10 = 55$.

Ce se afișează după executarea secvenței? (se presupune inclusă biblioteca <cstring>)

1. strchr("aeiou", s[i]) returnează un pointer nenul dacă s[i] este vocală.
2. Vocalele din informatica sunt pe pozițiile 0 (i), 3 (o), 6 (a), 8 (i), 10 (a).
3. Fiecare este înlocuită cu * și k crește de 5 ori.
4. Se afișează *nf*rm*t*c* 5.

A este corect: toate cele 5 vocale devin *. B are șirul bun, dar numără greșit (uită o vocală). C ar corespunde ștergerii vocalelor, însă codul le înlocuiește, nu le elimină. D ar rezulta dacă bucla s-ar opri înainte de ultimul caracter (de exemplu, cu condiția s[i + 1]).

Ce afișează secvența următoare?

1. În binar: $13 = 1101_{(2)}$, $6 = 0110_{(2)}$.
2. ȘI pe biți: $1101 \,\&\, 0110 = 0100_{(2)} = 4$.
3. SAU pe biți: $1101 \mid 0110 = 1111_{(2)} = 15$.
4. SAU exclusiv: $1101 \oplus 0110 = 1011_{(2)} = 11$.
5. Se afișează 4 15 11.

B este corect după calculul bit cu bit. A presupune greșit că & și | returnează unul dintre operanzi (6, respectiv 13), ceea ce nu e adevărat pe biți. C are x ^ 6 = 19 = 13 + 6, adică confundă XOR cu adunarea. D confundă operatorii pe biți cu operații aritmetice ($13 \bmod 6 = 1$, $13 + 6 = 19$, $13 \cdot 6 = 78$).

Folosind metoda backtracking, se generează în ordine lexicografică toate permutările mulțimii $\{1, 2, 3, 4\}$. Prima este 1 2 3 4, a doua 1 2 4 3. Pe ce poziție se află permutarea 3 1 4 2?

1. Permutările care încep cu 1: $3! = 6$ (pozițiile 1–6). Cele care încep cu 2: încă 6 (pozițiile 7–12).
2. Cu prefixul 3 urmează, în ordine: 3 1 2 4 (13), 3 1 4 2 (14), 3 2 1 4 (15), ...
3. Deci 3 1 4 2 este a 14-a permutare.

C este corect: înainte de ea sunt $6 + 6 + 1 = 13$ permutări. A = 13 este poziția lui 3 1 2 4, imediat anterioară. B = 15 este poziția lui 3 2 1 4. D = 16 ar fi 3 2 4 1, rezultat al numărării greșite a permutărilor cu prefixul 3 2.

Un graf neorientat are 8 noduri, numerotate de la 1 la 8, și muchiile $[1,2], [2,5], [3,4], [6,7], [7,8], [8,6]$. Câte componente conexe are graful?

1. Pornim o parcurgere (DFS/BFS) din fiecare nod nevizitat.
2. Din 1 ajungem la 2 și 5: componenta $\{1, 2, 5\}$.
3. Din 3 ajungem la 4: componenta $\{3, 4\}$.
4. Din 6 ajungem la 7 și 8: componenta $\{6, 7, 8\}$ (care conține un ciclu).
5. Toate cele 8 noduri sunt acoperite, deci sunt 3 componente conexe.

B este corect: $\{1,2,5\}$, $\{3,4\}$, $\{6,7,8\}$. A unește greșit două componente care nu au nicio muchie între ele. C = 4 ar rezulta dacă se omite muchia $[3,4]$, considerând nodurile 3 și 4 izolate. D = 5 ar presupune că nodurile 6, 7, 8 nu sunt toate legate.

Se construiește matricea a cu 4 linii și 4 coloane (indexate de la 0) astfel:

Ce valoare are s la final?

1. Pe diagonala principală $i = j$, deci $a[i][i] = 2i \bmod 3$.
2. $i = 0$: $0$; $i = 1$: $2$; $i = 2$: $4 \bmod 3 = 1$; $i = 3$: $6 \bmod 3 = 0$.
3. $s = 0 + 2 + 1 + 0 = 3$.

D este corect. A = 6 este suma $0+1+2+3$ a indicilor (sau numărul de zerouri din matrice), nu suma de pe diagonală. B = 0 ar fi corect dacă toate elementele diagonalei ar fi multipli de 3. C = 2 se obține dacă se calculează greșit $(i \cdot j) \bmod 3$ în loc de $(i + j) \bmod 3$: $0 + 1 + 1 + 0 = 2$.

Câte apeluri ale funcției h (inclusiv apelul inițial) se execută pentru h(6)?

1. Notăm $c(n)$ numărul de apeluri pentru h(n). Avem $c(0) = c(1) = 1$ și $c(n) = 1 + c(n-1) + c(n-2)$.
2. $c(2) = 3$, $c(3) = 5$, $c(4) = 9$, $c(5) = 15$.
3. $c(6) = 1 + 15 + 9 = 25$.

B este corect după recurența numărului de apeluri. A = 13 este valoarea returnată de h(6), nu numărul de apeluri. C = 21 este un termen Fibonacci apropiat, fără apelul curent adăugat la fiecare nivel. D = $2^6$ presupune un arbore de apeluri complet, dar ramura h(n - 2) este mai scurtă.