Pre-admitere Informatică 2025 — 5 aprilie

Fie $a$ și $b$ două valori întregi, cu $a \le b$, și $v$ un vector sortat descrescător cu $n$ elemente (numere întregi). Dorim să determinăm numărul de elemente din $v$ care sunt în intervalul $[a, b]$. Care este complexitatea temporală a algoritmului optim? a) $O(\log^2 n)$; b) $O(n\log n)$; c) $O(1)$; d) $O(\log n)$; e) $O(n)$; f) $O(n^2)$.

O matrice rară (cu multe elemente nule) este reprezentată prin dimensiunile ei: numărul de linii și numărul de coloane ($nl$ și $nc$), numărul de elemente nenule ($nn$) și un vector $\mathtt{term}$ care conține maxim $100$ de termeni nenuli caracterizați prin poziție ($\mathtt{lin}$, $\mathtt{col}$) și valoare ($\mathtt{val}$).

typedef struct {
  int lin, col, val;
} termen;

typedef struct {
  int nl, nc, nn;
  termen term[100];
} matrice_rara;

Matricea $$A=\begin{pmatrix} 0 & 0 & 0 & 0 & 7 \\ 2 & 0 & 0 & 1 & 0 \\ 0 & 3 & 0 & 0 & 1 \\ 0 & 4 & 0 & 0 & 9 \end{pmatrix}$$ se va reprezenta (în ordinea parcurgerii pe linii, de la stânga la dreapta) folosind variabila $\mathtt{mr}$. Ce va afișa secvența următoare?

printf("%d", mr.term[1].val); // Pascal: Write(mr.term[2].val);

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

Se definește $ARB(n)$ un arbore binar în care: toate nodurile au $0$ sau $2$ copii; toate frunzele sunt pe același nivel; numărul de niveluri este $n$. Rădăcina este pe nivelul $1$ și are valoarea $1$. Un nod cu valoarea $x$ (care nu este frunză) are: copilul stâng: $2x$; copilul drept: $2x+1$. Exemplu: $ARB(3)$ conține $7$ noduri, iar $sum(ARB(3))=103$. Cât este: $sum(ARB(5))-sum(ARB(4))$? a) $3072$; b) $2987$; c) $2869$; d) $3061$; e) $2976$; f) $3125$.

Care dintre următoarele expresii verifică proprietatea $|x-a| < b$ pentru $a, b, x$ întregi?

I1. a-b < x && x < a+b
I2. a-b < x || x < a+b
I3. a+b < x && x < a-b
I4. a-b < x < a+b
I5. x < a+b

a) I3; b) I5 și I5; c) I4; d) I1; e) I2 și I5; f) I5.

Fie un graf orientat cu nodurile $1, 2, 3, 4, 5$. [Figura: nodul $1$ sus, nodurile $2$ și $3$ pe rândul din mijloc, nodurile $4$ și $5$ pe rândul de jos; arcele: $1\to 2$, $1\to 3$, $2\to 3$, $2\to 4$, $2\to 5$, $3\to 4$, $4\to 5$, $5\to 3$.] Numărul de drumuri elementare de la $1$ la $5$ este: a) $6$; b) $3$; c) $2$; d) $5$; e) $4$; f) $1$.

Ce afișează programul:

void func(char sir[10]) {
  int i = 0;
  while (i < strlen(sir)) {
    if (i % 2) {
      sir[i] = '*';
    } else {
      sir[i] = '|';
    }
    i = i + 1;
    printf("%s", sir);
  }
}

int main() {
  char sir[10] = "PUB";
  func(sir);
  printf("%s", sir);
  return 0;
}

a) |UB|*B|*|BPU    b) |PB|*B|*|UPB    c) |UB|*B|*|UPB
d) |UB|*B|*||*|    e) |PB|B|||*|      f) |UB|*B|*|PUB

Funcția:

int f(int n) {
  if (n == 0) return 0;
  if (n % 2) return f(n / 2) - 2;
  return f(n + 1) + 1;
}

Rezultatul apelului $f(2025)$: a) $-19$; b) $10$; c) $-13$; d) $3$; e) $-18$; f) $-12$.