[canonical]: https://grile.online/informatica/subiecte/model-admitere-politehnica-bucuresti-069

> Pagina completă: https://grile.online/informatica/subiecte/model-admitere-politehnica-bucuresti-069
> 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 Model Admitere Politehnica București · Informatică #069

10 grile din Expresii, Căutare, Grafuri, cu explicații. Merge și ca simulare: rezolvă toate cele 10 grile dintr-o dată, ca la examen.

Original, în stilul Admitere Politehnica București

## Teaser gratuit, fără cont

1. Ce afișează secvența alăturată?

a) $15$
b) $3$
c) $19$
d) $17$
e) $20$
f) $12$

Răspuns corect: d) $17$

Împărțirea întreagă dă $17/5=3$, apoi $3\cdot5=15$, iar $17\%5=2$. $15+2=17$.

2. Ce afișează secvența alăturată?

a) `1 2`
b) `1 1`
c) `5 6`
d) `1 7`
e) `2 2`
f) `5 7`

Răspuns corect: a) `1 2`

Căutarea se oprește la prima apariție: la $i=1$ se găsește $8$, deci $p=1$, apoi `i` se incrementează încă o dată, la $2$, înainte de testul care încheie bucla.

3. Câte muchii trebuie eliminate, cel puțin, dintr-un graf complet cu $6$ noduri pentru a obține un arbore?

a) $10$
b) $9$
c) $5$
d) $15$
e) $11$
f) $6$

Răspuns corect: a) $10$

Graful complet are $C_6^2=15$ muchii, iar un arbore cu $6$ noduri are $5$. Trebuie eliminate $15-5=10$.

4. Subprogramul `f` este definit alăturat. Ce valoare returnează apelul `f(13,11)`?

a) $130$
b) $156$
c) $121$
d) $143$
e) $117$
f) $24$

Răspuns corect: d) $143$

Este înmulțirea „a țăranului rus”: `a` se dublează, `b` se înjumătățește, iar când `b` e impar se adună `a`. $11=1011_{(2)}$, deci $13+26+104=143=13\cdot11$.

5. Care este complexitatea timp a secvenței de mai jos, în funcție de $n$?

`for(i=1;i<=n;i++) for(j=i;j<=n;j+=i) k++;`

a) $O(n\log n)$
b) $O(n)$
c) $O(n^2)$
d) $O(\log n)$
e) $O(n\sqrt{n})$
f) $O(\log^2 n)$

Răspuns corect: a) $O(n\log n)$

Pentru un `i` fixat, bucla interioară face aproximativ $n/i$ pași. Suma $n(1+\frac12+\dots+\frac1n)$ este de ordinul $n\log n$ (seria armonică).