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

> Pagina completă: https://grile.online/informatica/subiecte/model-admitere-politehnica-bucuresti-068
> 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ă #068

10 grile din Structuri de control, Arbori binari, Sortare, 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) $4$
b) $16$
c) $32$
d) $6$
e) $2$
f) $8$

Răspuns corect: f) $8$

`n` trece prin $5\to3\to1\to-1$, deci corpul se execută de $3$ ori, iar $p=2^3=8$.

2. Într-un arbore cu rădăcină, rădăcina are $3$ fii, alte $2$ noduri au câte $2$ fii, alte $4$ noduri au câte un singur fiu, iar toate celelalte noduri sunt frunze. Câte frunze are arborele?

a) $4$
b) $6$
c) $7$
d) $12$
e) $3$
f) $5$

Răspuns corect: f) $5$

Fiecare nod în afară de rădăcină este fiul cuiva, deci arborele are $3+2\cdot2+4\cdot1=11$ muchii și $12$ noduri. Nodurile cu fii sunt $1+2+4=7$, deci frunzele sunt $12-7=5$.

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

a) $4$
b) $6$
c) $3$
d) $5$
e) $10$
f) $7$

Răspuns corect: d) $5$

Interschimbările: $4\leftrightarrow1$; $7\leftrightarrow4$, $4\leftrightarrow3$; $7\leftrightarrow4$; $9\leftrightarrow7$. În total $5$ (nu $10$, numărul de comparații).

4. Se generează cu backtracking, în ordine lexicografică, toate șirurile de $4$ cifre binare care nu conțin două cifre $1$ alăturate. Primele trei sunt `0000`, `0001`, `0010`. Care este al șaptelea șir generat?

a) `1001`
b) `1000`
c) `1010`
d) `0101`
e) `0110`
f) `1100`

Răspuns corect: a) `1001`

Șirurile valide, în ordine: `0000`, `0001`, `0010`, `0100`, `0101`, `1000`, `1001`, `1010`. Al șaptelea este `1001`.

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

a) $4$
b) $3$
c) $5$
d) $7$
e) $2$
f) $6$

Răspuns corect: a) $4$

`d[i]` este lungimea celui mai lung subșir strict crescător care se termină în `a[i]`: $d=(1,1,2,2,3,3,4)$. Maximul $4$ corespunde subșirului $1,2,3,6$.