Pre-admitere Informatică 2022 — 30 aprilie — Varianta A

Fie un graf neorientat cu $n$ vârfuri, pe care vrem să le împărțim în 3 mulțimi disjuncte nenule (dacă $V$ este mulțimea vârfurilor, fie $V_1, V_2, V_3$ cele trei mulțimi disjuncte, $V_1\subset V$, $V_2\subset V$, $V_3\subset V$, $V_1\cap V_2=\emptyset$, $V_1\cap V_3=\emptyset$, $V_2\cap V_3=\emptyset$). Știind că vârfurile din aceeași mulțime nu pot avea muchii între ele, care este numărul maxim de grafuri care se pot construi respectând aceste condiții pentru $n=2022$?

a) $2^{4088484}$; b) $2^{681414}$; c) $2^{2043231}$; d) $2^{1362828}$; e) $2^{4086462}$; f) $2^{2022}$.

Fie funcția recursivă definită prin următorul pseudocod. Care este rezultatul apelului $f(1, 3, 2022)$?

int f(int a, int b, int k)
{
    dacă (k==1) returnează a+b
    dacă (a+2>b) returnează f(a+2, b, k-1)
    returnează f(1, b+2, k-1)
}

a) $4$; b) $169$; c) $170$; d) $139$; e) $4044$; f) $140$.

Se consideră tabloul $v$ cu $n=10$ elemente, $v=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$. Care este numărul de comparații executate pentru sortarea crescătoare, prin metoda bulelor, a tabloului $v$? a) $n$; b) $\log_2(n)$; c) $n-1$; d) $n\cdot\log_2(n)$; e) $n+1$; f) $5$.

Fie un arbore cu următoarele proprietăți. Fiecare nod intern (un nod intern este orice nod care nu este o frunză) are 3 copii. Toate nivelurile arborelui sunt pline cu noduri, mai puțin ultimul, unde frunzele completează nivelul de la stânga la dreapta. Care e numărul minim, respectiv maxim, de noduri pe care le poate avea un astfel de arbore dacă înălțimea acestuia este $h$, considerând că rădăcina are nivelul $0$ și $h\ge 2$?

a) $\frac{1}{2}(3^h-1)+3$, $\frac{1}{2}(3^{h+1}-1)$; b) $3^h+3$, $3^{h+1}-1$; c) $3^h+2$, $3^{h+1}-1$; d) $\frac{1}{2}(3^h-1)+2$, $\frac{1}{2}(3^{h+1}-1)$; e) $\frac{1}{2}(3^h-1)+1$, $\frac{1}{2}(3^{h+1}-1)$; f) $3^h+1$, $3^{h+1}-1$.

Fie o matrice cu $n$ linii și $m$ coloane. În câte moduri se poate ajunge din colțul stânga-sus (de coordonate $1$ și $1$) în cel din dreapta-jos (de coordonate $n$ și $m$), dacă ne putem deplasa, la fiecare pas, câte o poziție doar pe verticală (în sus sau jos) sau orizontală (în dreapta sau stânga), iar numărul de pași realizați trebuie să fie minim? Se știe că $n=11$ și $m=8$.

a) $524288$ moduri; b) $176$ moduri; c) $19448$ moduri; d) $131072$ moduri; e) $88$ moduri; f) $9724$ moduri.