Admitere Informatică 2021 — iulie — Varianta C

Se dă problema: calculați suma primelor $n$ elemente din șirul lui Fibonacci. Care sunt complexitățile timp, respectiv, spațiu minime pentru a obține soluția pentru această problemă? a) $O(2^n)$ și $O(1)$; b) $O(n^2)$ și $O(n)$; c) $O(n^2)$ și $O(1)$; d) $O(n)$ și $O(1)$; e) $O(n)$ și $O(n)$; f) $O(2^n)$ și $O(n)$.

Fie o matrice $M$ cu $20$ de linii și $21$ de coloane, care conține următoarele elemente: $M[i][j]=i\cdot i$ dacă $i=j$, $M[i][j]=\min\{i,j\}$ dacă $i\neq j$, pentru $1\le i\le 20$, $1\le j\le 21$. Care este suma tuturor elementelor din matrice?

a) $10040$; b) $4042$; c) $2560$; d) $6760$; e) $5240$; f) $5740$.

Utilizând metoda backtracking, se generează, în ordine strict descrescătoare, toate numerele naturale de câte patru cifre distincte din mulțimea $\{0,1,2,3,4,5\}$. Primele șase numere generate sunt, în această ordine: $5432$, $5431$, $5430$, $5423$, $5421$, $5420$. Al șaptelea număr generat este:

a) $5415$; b) $5321$; c) $5340$; d) $5421$; e) $5413$; f) $5342$.

Pentru a genera submulțimile unei mulțimi $M=\{x_1,x_2,\ldots,x_n\}$ cu $n=10$ elemente se folosește metoda backtracking. Câte submulțimi cu cardinal impar se generează, submulțimi care conțin numai unul dintre elementele $x_1$ și $x_3$ și nu conțin elementul $x_2$?

a) $510$; b) $128$; c) $511$; d) $255$; e) $256$; f) $127$.