[canonical]: https://grile.online/informatica/subiecte/admitere-politehnica-bucuresti-2021-informatica-varianta-c-iulie

> Pagina completă: https://grile.online/informatica/subiecte/admitere-politehnica-bucuresti-2021-informatica-varianta-c-iulie
> 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 Admitere Politehnica București 2021 — Informatică, Varianta C (iulie) · Informatică #140

10 grile din Expresii, Subprograme, Complexitate, cu explicații. Transcrise din Admitere Politehnica București 2021 — Informatică, Varianta C (iulie). Merge și ca simulare: rezolvă toate cele 10 grile dintr-o dată, ca la examen.

Subiect oficial (Admitere Politehnica București 2021 — Informatică, Varianta C (iulie))

## Teaser gratuit, fără cont

1. Variabila `x` este de tip întreg și poate memora un număr natural format din exact două cifre. Indicați cea mai mare valoare pe care o poate avea expresia:

a) $7$
b) $6$
c) $9$
d) $10$
e) $4$
f) $8$

Răspuns corect: d) $10$

Pentru $x=\overline{ab}$, `x / 10` este cifra zecilor $a$, iar `x % 10` cifra unităților $b$, deci expresia este $|a-b+1|$, cu $a\in\{1,\ldots,9\}$ și $b\in\{0,\ldots,9\}$.

Cea mai mare valoare a lui $a-b+1$ este $9-0+1=10$, iar cea mai mică $1-9+1=-7$, cu modulul $7$. Maximul este deci $10$, obținut pentru $x=90$.

Subiect oficial · Admitere UPB 2021, Concurs unificat, Informatică, Varianta C (iulie), itemul 1 · cheie din baremul oficial

2. Se dă problema: calculați suma primelor $n$ elemente din șirul lui Fibonacci. Care sunt complexitățile timp, respectiv, spațiu minime pentru a obține soluția pentru această problemă?

a) $O(2^n)$ și $O(1)$
b) $O(n^2)$ și $O(n)$
c) $O(n^2)$ și $O(1)$
d) $O(n)$ și $O(1)$
e) $O(n)$ și $O(n)$
f) $O(2^n)$ și $O(n)$

Răspuns corect: d) $O(n)$ și $O(1)$

Termenii se pot genera pe rând, păstrând doar ultimii doi termeni și suma parțială: $n$ pași, cu un număr constant de variabile.

Dintre variantele propuse, cea mai bună este deci timp $O(n)$ și spațiu $O(1)$. Timpul exponențial corespunde recursivității naive, iar spațiul $O(n)$ apare doar dacă se memorează inutil tot șirul.

Subiect oficial · Admitere UPB 2021, Concurs unificat, Informatică, Varianta C (iulie), itemul 2 · cheie din baremul oficial

3. Se consideră declarările de mai jos:

Câmpul `descriere` al variabilei `p` a fost inițializat cu un șir de caractere de lungime $10$, iar câmpul `cod` al variabilei `p` a fost inițializat cu o valoare între $1$ și $499$.

Care dintre următoarele instrucțiuni nu este corectă din punct de vedere sintactic?

a) `m.produse[p.cod].cod++;`
b) `p.descriere[12]++;`
c) `m.produse[p.cod].cod=p.cod;`
d) `m.produse[p.cod].nume[2]='n';`
e) `m.nume[3]=p.descriere[2];`
f) `m.produse[p.cod]=p;`

Răspuns corect: d) `m.produse[p.cod].nume[2]='n';`

`m.produse[p.cod]` este o structură `Produs`, care are doar câmpurile `cod` și `descriere`; câmpul `nume` aparține lui `Magazin`, deci `m.produse[p.cod].nume[2]` nu se compilează.

Celelalte instrucțiuni sunt valide: incrementarea unui caracter (`p.descriere[12]`, cu indicele sub $50$), atribuiri între câmpuri de același tip și atribuirea unei structuri întregi.

Subiect oficial · Admitere UPB 2021, Concurs unificat, Informatică, Varianta C (iulie), itemul 3 · cheie din baremul oficial

4. Fie o matrice `M` cu $20$ de linii și $21$ de coloane, care conține următoarele elemente: `M[i][j] = i*i` dacă `i = j`, `M[i][j] = min{i, j}` dacă `i ≠ j`, pentru $1\le i\le20$, $1\le j\le21$. Care este suma tuturor elementelor din matrice?

a) $10040$
b) $4042$
c) $2560$
d) $6760$
e) $5240$
f) $5740$

Răspuns corect: f) $5740$

Dacă toate elementele ar fi $\min\{i,j\}$, linia $i$ ar avea suma $(1+2+\ldots+i)+i(21-i)$; însumând pentru $i$ de la $1$ la $20$ se obține $1540+1540=3080$.

Pe diagonală elementul este $i^2$ în loc de $i$, ceea ce adaugă $\sum_{i=1}^{20}(i^2-i)=2870-210=2660$. Suma este $3080+2660=5740$.

Subiect oficial · Admitere UPB 2021, Concurs unificat, Informatică, Varianta C (iulie), itemul 4 · cheie din baremul oficial

5. Fie `a`, `b`, `c` și `d` patru variabile întregi care pot lua valori $0$ sau $1$. Care din expresiile de mai jos este echivalentă cu următoarea expresie:

a) `!((a || b) && (c || d))`
b) `!((!a && !b) || (!c && !d))`
c) `!((!a || !b) && (!c || !d))`
d) `!(!(a && b) || !(c && d))`
e) `!(!(a || b) && !(c || d))`
f) `(!a || !b) && (!c || !d)`

Răspuns corect: c) `!((!a || !b) && (!c || !d))`

Din legile lui De Morgan, `!a || !b` este negația lui `a && b`, iar `!c || !d` este negația lui `c && d`. Notând $P$ = `a && b` și $Q$ = `c && d`, expresia `!((!a || !b) && (!c || !d))` este $\lnot(\lnot P \land \lnot Q) = P \lor Q$, adică exact expresia dată.

Celelalte expresii se reduc, de exemplu, la `(a || b) && (c || d)`, la `(a && b) && (c && d)` sau la negația expresiei date, care diferă pe unele combinații de valori.

Subiect oficial · Admitere UPB 2021, Concurs unificat, Informatică, Varianta C (iulie), itemul 5 · cheie din baremul oficial