Admitere Informatică 2025 — Simulare 15 martie — Varianta B

Fie următoarea afirmație: „Orice graf pentru care 2 este numărul minim de culori este un graf bipartit sau este un graf eulerian.”; unde numărul minim de culori al unui graf reprezintă numărul cel mai mic de culori necesare pentru a colora vârfurile grafului astfel încât două vârfuri adiacente să nu aibă aceeași culoare. Câte dintre următoarele grafuri reprezintă un contra-exemplu pentru această afirmație?

[Graf 1: noduri D, A, B, C; muchii D—A, D—B, D—C, A—B, A—C, B—C.]

[Graf 2: noduri A, B, C, D, E, F; muchii A—B, A—D, B—C, C—D, D—E, C—E; nodul F este izolat (fără muchii).]

[Graf 3: noduri A, B, C; muchii A—B, A—C, B—C.]

[Graf 4: noduri A, B, C, D, E, F; muchii A—D, A—E, B—D, B—E, B—F, C—E, C—F.]

[Graf 5: noduri A, B, C, F, G; muchii A—B, A—C, C—F, C—G.]

a) 5; b) 0; c) 3; d) 2; e) 4; f) 1.

Fie următoarea funcție recursivă definită prin pseudocod. Câte apeluri ale funcției se realizează pentru a calcula func(20, 2025)?

intreg func(intreg x, intreg n) {
    daca x < 2 atunci
        intoarce n;
    intoarce func(x-2, n+2) + 2*func(x-4, n-1);
}

a) 2024; b) 1706; c) 144; d) 89; e) 2025; f) 287.

Considerăm șirul lui Fibonacci unde $fib(0)=0$, $fib(1)=1$ și $fib(k)=fib(k-1)+fib(k-2)$, pentru orice $k>1$, natural. Se construiește un arbore definit în funcție de numărul de nivele, rădăcina se află pe nivelul 1, și fiecare nod de pe nivelul $h$ are $fib(h+2)$ copii. Calculăm $N$ ca fiind numărul de noduri pentru un astfel de arbore cu 10 nivele. Pentru că numărul $N$ este destul de mare, se cere $N \bmod 13$ (restul împărțirii lui $N$ la 13).

a) 7; b) 3; c) 8; d) 4; e) 11; f) 6.

Pentru mulțimea $\{1, 2, 3, \ldots, n\}$ se generează printr-un program toate permutările în care nu există numere vecine alăturate. Două numere $a$ și $b$ sunt vecine dacă $|a-b|=1$ (de exemplu 3 și 4 sunt vecine, 2 și 1 sunt vecine). Știind că pentru $n=5$ au fost generate 14 permutări distincte în care nu există numere vecine, câte permutări se vor genera pentru $n=6$?

a) 72; b) 56; c) 144; d) 90; e) 89; f) 120.