[canonical]: https://grile.online/informatica/subiecte/model-admitere-mateinfo-ub-061

> Pagina completă: https://grile.online/informatica/subiecte/model-admitere-mateinfo-ub-061
> 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 MateInfo UB · Informatică #061

10 grile din Programare dinamică, Backtracking, Combinatorică, cu explicații. Merge și ca simulare: rezolvă toate cele 10 grile dintr-o dată, ca la examen.

Original, în stilul admitere MateInfo UB

## Teaser gratuit, fără cont

1. Graful neorientat cu $7$ noduri are muchiile $[1,2]$, $[1,3]$, $[2,3]$, $[2,4]$, $[3,5]$, $[4,5]$, $[4,6]$, $[5,7]$, $[6,7]$.

Câte noduri au gradul par?

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

Răspuns corect: f) $3$

Gradele sunt: $1\to2$, $2\to3$, $3\to3$, $4\to3$, $5\to3$, $6\to2$, $7\to2$. Au grad par nodurile $1$, $6$, $7$. (Verificare: suma gradelor, $18$, este dublul numărului de muchii.)

2. Care este scrierea în baza $16$ a numărului $2026$?

a) `7AE`
b) `AE7`
c) `7DA`
d) `6EA`
e) `7EA`
f) `7E10`

Răspuns corect: e) `7EA`

$2026=7\cdot256+234$, iar $234=14\cdot16+10$. Cifrele sunt $7$, $14$ (`E`) și $10$ (`A`): `7EA`.

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

a) $90$
b) $110$
c) $150$
d) $30$
e) $100$
f) $465$

Răspuns corect: e) $100$

Pentru fiecare $i$ bucla interioară face $\lfloor\sqrt{i}\rfloor$ pași: $1$ pentru $i=1..3$, $2$ pentru $i=4..8$, $3$ pentru $i=9..15$, $4$ pentru $i=16..24$, $5$ pentru $i=25..30$. Total $3+10+21+36+30=100$ (în general $O(n\sqrt n)$).

4. O broască trebuie să ajungă de pe prima pe ultima dintre $6$ pietre așezate în linie, cu înălțimile $10,30,40,20,50,30$. Dintr-o piatră sare fie pe următoarea, fie peste una, iar un salt costă diferența în modul dintre înălțimile celor două pietre.

Care este costul total minim?

a) $50$
b) $30$
c) $60$
d) $100$
e) $45$
f) $40$

Răspuns corect: f) $40$

Cu $d_i=\min(d_{i-1}+|h_i-h_{i-1}|,\ d_{i-2}+|h_i-h_{i-2}|)$ și $d_1=0$ se obțin pe rând $0,20,30,30,40,40$. Un drum optim: $10\to30\to20\to30$ peste pietre, cu costurile $20+10+10=40$.

5. Un arbore binar are parcurgerea în inordine `H D B E A F I C G` și parcurgerea în postordine `H D E B I F G C A`. Care este parcurgerea lui în preordine?

a) `A B E D H C F I G`
b) `A B D H E C I F G`
c) `A B D H E C F I G`
d) `A B D E H C F G I`
e) `A D H B E C F I G`
f) `A B H D E C F I G`

Răspuns corect: c) `A B D H E C F I G`

Rădăcina este ultimul nod din postordine, `A`; în inordine, `H D B E` formează subarborele stâng, iar `F I C G` pe cel drept. Repetând: stânga are rădăcina `B` (cu `D`, care îl are pe `H` ca fiu stâng, și `E`), dreapta are rădăcina `C` (cu `F`, al cărui fiu drept e `I`, și `G`). Preordinea: `A B D H E C F I G`.