[canonical]: https://grile.online/informatica/subiecte/admitere-politehnica-bucuresti-2022-informatica-pista-ib-varianta-f-iulie

> Pagina completă: https://grile.online/informatica/subiecte/admitere-politehnica-bucuresti-2022-informatica-pista-ib-varianta-f-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 2022 — Informatică, pista Ib, Varianta F (iulie) · Informatică #169

10 grile din Grafuri, Complexitate, Combinatorică, cu explicații. Transcrise din Admitere Politehnica București 2022 — Informatică, pista Ib, Varianta F (iulie). Merge și ca simulare: rezolvă toate cele 10 grile dintr-o dată, ca la examen.

Subiect oficial (Admitere Politehnica București 2022 — Informatică, pista Ib, Varianta F (iulie))

## Teaser gratuit, fără cont

1. Fie o matrice cu $n$ linii și $n$ coloane, care conține numere reale, cu următoarea proprietate: elementele de pe fiecare linie, precum și de pe fiecare coloană, sunt sortate crescător.

Putem construi un algoritm pentru a verifica dacă un număr $x$ dat apare în matrice. Care este complexitatea timp minimă a acestuia?

a) $O(\log(n))$
b) $O(n^2)$
c) $O(n*\log(n))$
d) $O(n)$
e) $O(n^2*\log(n))$
f) $O(1)$

Răspuns corect: d) $O(n)$

Se pornește din colțul din dreapta-sus: dacă elementul curent este mai mare decât $x$, coloana lui se elimină (se merge la stânga), iar dacă este mai mic, linia lui se elimină (se coboară). La fiecare pas dispare o linie sau o coloană, deci sunt cel mult $2n-1$ pași: $O(n)$.

Mai repede nu se poate în general: elementele unei antidiagonale nu sunt ordonate între ele și oricare dintre ele poate fi $x$, deci toate trebuie inspectate.

Subiect oficial · Admitere UPB 2025, AC/ETTI, Informatică, Varianta S (iulie), itemul 8 · cheie din baremul oficial

2. Un muzician generează toate secvențele de trei note muzicale din mulțimea {DO, RE, MI}. Într-o secvență notele muzicale se pot repeta. Fie $n$ numărul total de secvențe obținute. Care este valoarea lui $n$?

a) $n=3$
b) $n=1$
c) $n=81$
d) $n=9$
e) $n=27$
f) $n=12$

Răspuns corect: e) $n=27$

Fiecare dintre cele $3$ poziții ale secvenței poate primi oricare dintre cele $3$ note, independent de celelalte.

$n=3\cdot3\cdot3=3^3=27$.

Subiect oficial · Admitere UPB 2022, AC/ETTI, Informatică, pista Ib, Varianta F (18 iulie), itemul 2

3. Se consideră `n`, `f` și `i` numere întregi pozitive, cu $n\geq2$, și următoarea secvență în pseudocod.

Care dintre următoarele secvențe de pseudocod conduc la aceeași valoare a lui `f` ca secvența de mai sus?

a) I, II și III
b) II și III
c) I, II și IV
d) II și IV
e) I și II
f) I și IV

Răspuns corect: e) I și II

Secvența dată calculează $f=2\cdot3\cdot\ldots\cdot n=n!$.

I: `i` crește la $2, 3, \ldots, n$ și `f` se înmulțește de fiecare dată, iar bucla se oprește când `i` ajunge la `n` (pentru $n=2$ face un singur pas): $n!$. II: înmulțește cu $2, \ldots, n$: $n!$. III: crește `i` înainte de înmulțire, deci înmulțește doar cu $3, \ldots, n$: $\dfrac{n!}{2}$. IV: ultimul factor este $n-n=0$, deci $f=0$. Corecte: I și II.

Subiect oficial · Admitere UPB 2022, AC/ETTI, Informatică, pista Ia, Varianta F (18 iulie), itemul 10

4. Fie o mulțime de $k$ simboluri cu care se pot forma șiruri distincte de lungime $n$ ($n\geq k$). Fiecare dintre cele $k$ simboluri apare în fiecare șir de $f_1, f_2, \ldots, f_k$ ori, $f_i\geq1$, $1\leq i\leq k$.

Pentru simbolurile {A, B, C} care apar de $1$, $3$ și, respectiv, $2$ ori, primele $4$ șiruri generate cu metoda backtracking sunt: `ABBBCC`, `ABBCBC`, `ABBCCB`, `ABCBBC`. Care este următorul șir care va fi generat?

a) `ACCBBB`
b) `ABCBCB`
c) `ABCCBB`
d) `ABBBCC`
e) `ACBBBC`
f) `BABCCB`

Răspuns corect: b) `ABCBCB`

Șirurile apar în ordine lexicografică (A < B < C): backtracking-ul modifică întâi ultima poziție care mai poate primi un simbol mai mare.

După `ABCBBC`, prefixul `ABCB` poate continua și cu `CB` (rămân de pus un B și un C), deci următorul șir este `ABCBCB`; abia apoi urmează `ABCCBB`.

Subiect oficial · Admitere UPB 2022, AC/ETTI, Informatică, pista Ia, Varianta F (18 iulie), itemul 8

5. Fie un graf neorientat cu $n$ noduri ($n\geq1$). Care este numărul maxim de muchii ale grafului?

a) $n*(n-1)/2$
b) $n*(n+1)/2$
c) $n-1$
d) $2*n$
e) $n*n$
f) $n+1$

Răspuns corect: a) $n*(n-1)/2$

Numărul de muchii este maxim când graful este complet: fiecare pereche de noduri distincte este unită printr-o muchie.

Numărul perechilor este $C_n^2=\dfrac{n(n-1)}{2}$.

Subiect oficial · Admitere UPB 2022, AC/ETTI, Informatică, pista Ib, Varianta F (18 iulie), itemul 5