Admitere Informatică 2022 — 18 iulie — Ia, Varianta F

Se consideră funcția recursivă (varianta C/C++):

int S(int n, int a, int b)
{
  if(n==0) return 0;
  else return a*n + b + S(n-1,a,b);
}

Dacă apelul $S(10,a,b)$ are ca rezultat $2045$, iar apelul $S(5,a,b)$ are ca rezultat $560$, atunci:

a) $a=1,\ b=2$; b) $a=10,\ b=5$; c) $a=1,\ b=37$; d) $a=37,\ b=1$; e) $a=37,\ b=38$; f) $a=5,\ b=10$.

Fie $v$ un tablou unidimensional sortat ce conține $n$ întregi. Un algoritm determină dacă există două elemente din $v$ a căror sumă este mai mică decât $1024$. Care este complexitatea timp minimă pe care o poate avea acest algoritm?

a) $O(n^2)$; b) $O(\log n)$; c) $O(1)$; d) $O(n)$; e) $O(2^{10})$; f) $O(n\log n)$.

Fie un graf neorientat oarecare și o submulțime de $k$ noduri ($k\ge 1$) ale acestuia. Nodurile acestei submulțimi au gradele $2^0, 2^1, \ldots, 2^{k-1}$. Toate celelalte noduri din graf sunt legate la cel puțin un nod din această submulțime. Care este numărul minim, respectiv maxim, de noduri pe care le poate avea graful, în funcție de $k$.

a) $\min=2^{k-1}+1$, $\max=2^k+k-1$; b) $\min=k$, $\max=2^k-1$; c) $\min=k+1$, $\max=2^k+k-1$; d) $\min=2^{k-1}+1$, $\max=2^{k-1}+1$; e) $\min=2^{k-1}$, $\max=2^k+k$; f) $\min=k+2$, $\max=2^{k+1}$.

Fie o mulțime de $k$ simboluri cu care se pot forma șiruri distincte de lungime $n$ ($n\ge k$). Fiecare dintre cele $k$ simboluri apare în fiecare șir de $f_1, f_2, \ldots, f_k$ ori, $f_i\ge 1$, $1\le i\le k$. Pentru simbolurile $\{A, B, C\}$ care apar de $1$, $3$ și, respectiv, $2$ ori, primele $4$ șiruri generate cu metoda backtracking sunt: ABBBCC, ABBCBC, ABBCCB, ABCBBC. Care este următorul șir care va fi generat?

a) ACCBBB; b) ABCBCB; c) ABCCBB; d) ABCBBC; e) ACBBBC; f) BABCCB.