[canonical]: https://grile.online/informatica/subiecte/admitere-politehnica-bucuresti-2022-informatica-pista-ia-varianta-f-iulie > Pagina completă: https://grile.online/informatica/subiecte/admitere-politehnica-bucuresti-2022-informatica-pista-ia-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 Ia, Varianta F (iulie) · Informatică #168 10 grile din Grafuri, Șiruri de caractere, Combinatorică, cu explicații. Transcrise din Admitere Politehnica București 2022 — Informatică, pista Ia, 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 Ia, Varianta F (iulie)) ## Teaser gratuit, fără cont 1. Care este șirul de caractere conținut în variabila `result` după execuția secvenței de cod de mai jos? a) `ANAAREMERE` b) `ana are 4 mere` c) `anaaremere` d) `ANA ARE MERE` e) `ANAARE4MERE` f) `ANA ARE 4 MERE` Răspuns corect: a) `ANAAREMERE` Bucla parcurge `input`: o literă mică este transformată în majusculă (se scade `'a'-'A'`), o majusculă este copiată ca atare, iar celelalte caractere (spațiile și cifra `4`) nu sunt copiate deloc, pentru că nu intră pe nicio ramură. Din `Ana are 4 mere` rămân doar literele, toate majuscule: `ANAAREMERE`. Subiect oficial · Admitere UPB 2022, AC/ETTI, Informatică, pista Ia, Varianta F (18 iulie), itemul 1 2. Un muzician generează toate secvențele de trei note muzicale din mulțimea {DO, RE, MI, FA, SOL, LA, SI}. Într-o secvență notele muzicale se pot repeta. Fie $n$ numărul total de secvențe obținute și $m$ numărul de secvențe obținute care conțin cel puțin o notă care se repetă. Care sunt valorile pentru $n$ și $m$? a) $n=2187$, $m=133$ b) $n=2187$, $m=1977$ c) $n=343$, $m=308$ d) $n=210$, $m=35$ e) $n=343$, $m=133$ f) $n=245$, $m=35$ Răspuns corect: e) $n=343$, $m=133$ Fiecare dintre cele $3$ poziții poate primi oricare dintre cele $7$ note: $n=7^3=343$. Secvențele fără nicio repetare sunt aranjamentele $A_7^3=7\cdot6\cdot5=210$, deci $m=343-210=133$. Subiect oficial · Admitere UPB 2022, AC/ETTI, Informatică, pista Ia, Varianta F (18 iulie), itemul 2 3. Se consideră funcția recursivă. Dacă apelul `S(10, a, b)` are ca rezultat $2045$, iar apelul `S(5, a, b)` are ca rezultat $560$, atunci: a) $a=1$, $b=2$ b) $a=10$, $b=5$ c) $a=1$, $b=37$ d) $a=37$, $b=1$ e) $a=37$, $b=38$ f) $a=5$, $b=10$ Răspuns corect: d) $a=37$, $b=1$ Desfăcând recursivitatea, $S(n,a,b)=a(1+2+\ldots+n)+nb=a\dfrac{n(n+1)}{2}+nb$. Rezultă sistemul $55a+10b=2045$ și $15a+5b=560$. Din a doua ecuație $b=112-3a$; înlocuind, $55a+1120-30a=2045$, deci $25a=925$, $a=37$ și $b=1$. Subiect oficial · Admitere UPB 2022, AC/ETTI, Informatică, pista Ia, Varianta F (18 iulie), itemul 3 4. 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 5. Fie un graf neorientat oarecare și o submulțime de $k$ noduri ($k\geq1$) ale acesteia. Nodurile acestei submulțimi au gradele $2^0, 2^1, \ldots, 2^{k-1}$. Toate celelalte noduri din graf sunt legate la cel puțin un nod din această submulțime. Care este numărul minim, respectiv maxim, de noduri pe care le poate avea graful, în funcție de $k$. a) $\text{min}=2^{k-1}+1$, $\text{max}=2^k+k-1$ b) $\text{min}=k$, $\text{max}=2^k-1$ c) $\text{min}=k+1$, $\text{max}=2^k+k-1$ d) $\text{min}=2^{k-1}+1$, $\text{max}=2^{k-1}+1$ e) $\text{min}=2^{k-1}$, $\text{max}=2^k+k$ f) $\text{min}=k+2$, $\text{max}=2^{k+1}$ Răspuns corect: a) $\text{min}=2^{k-1}+1$, $\text{max}=2^k+k-1$ Minim: nodul de grad $2^{k-1}$ are $2^{k-1}$ vecini distincți, deci graful are cel puțin $2^{k-1}+1$ noduri. Valoarea se atinge: legăm acest nod de toate celelalte, iar fiecare nod de grad $2^i$ ($i