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

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

10 grile din Programare dinamică, Combinatorică, Grafuri, 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. Se generează, în ordine lexicografică, submulțimile cu $3$ elemente ale mulțimii $\{1,2,3,4,5\}$ (combinări de $5$ luate câte $3$). Ce submulțime urmează imediat după `145`?

a) `345`
b) `234`
c) `123`
d) `245`
e) `235`
f) `146`

Răspuns corect: b) `234`

După `145` nu mai există combinări care încep cu $1$ (ultimul element are deja valoarea maximă $5$), deci se trece la prima care începe cu $2$: `234`.

2. Un arbore cu $10$ noduri este dat prin vectorul de tați $t=(3,3,0,3,1,1,4,6,6,2)$, unde $t_i$ este tatăl nodului $i$ și $0$ marchează rădăcina. Câte frunze are arborele?

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

Răspuns corect: a) $5$

Nodurile care apar ca tată sunt $3$, $1$, $4$, $6$, $2$; celelalte, $5$, $7$, $8$, $9$, $10$, nu au fii, deci sunt frunze: $5$.

3. În câte moduri se poate plăti suma de $10$ lei folosind monede de $1$, $2$ și $5$ lei (oricâte din fiecare; contează doar câte monede de fiecare tip se folosesc, nu ordinea)?

a) $128$
b) $12$
c) $9$
d) $8$
e) $10$
f) $11$

Răspuns corect: e) $10$

Cu $d_s$ numărul de moduri pentru suma $s$, se adaugă pe rând fiecare tip de monedă: $d_s \mathrel{+}= d_{s-c}$. Direct: cu două monede de $5$ — $1$ mod; cu una de $5$ — restul $5$ din $1$ și $2$: $3$ moduri; fără — $10$ din $1$ și $2$: $6$ moduri. Total $10$.

4. Câte submulțimi cu $3$ elemente ale mulțimii $\{1,2,\dots,10\}$ nu conțin două numere consecutive?

a) $120$
b) $64$
c) $84$
d) $35$
e) $72$
f) $56$

Răspuns corect: f) $56$

Dacă $a<b<c$ nu sunt consecutive, atunci $a<b-1<c-2$ sunt trei numere distincte din $\{1,\dots,8\}$, și invers. Deci sunt $C_8^3=56$ submulțimi.

5. Care este lungimea celui mai lung subșir comun (nu neapărat din caractere consecutive) al cuvintelor `ALGORITM` și `LOGARITM`?

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

Răspuns corect: c) $6$

Cu $d_{i,j}=d_{i-1,j-1}+1$ dacă ultimele caractere coincid și $\max(d_{i-1,j},d_{i,j-1})$ altfel se obține $6$; de exemplu `LORITM`.