Pre-admitere Informatică 2026 — 28 martie

Fie un tablou unidimensional $v$ cu $n$ numere întregi distincte și două numere întregi $L$ și $R$, $L \le R$. Dorim să determinăm numărul de perechi de indici $(i,j)$, pentru care $L \le v[i]+v[j] \le R$. Care este complexitatea timp a algoritmului optim care rezolvă problema? a) $O(1)$; b) $O(n^2)$; c) $O(n\log n)$; d) $O(\log n)$; e) $O(n^2\log n)$; f) $O(\sqrt{n})$.

Considerăm $G$ un graf neorientat cu $2026$ de noduri și $2000$ de muchii. Fie $m$ numărul minim de componente conexe și $M$ numărul maxim de componente conexe pentru un graf cu proprietățile lui $G$. Ce valoare are $M-m$?

a) $1925$; b) nu se poate calcula; c) $63$; d) $1937$; e) $199$; f) $1999$.

Fie următorul algoritm în pseudocod, unde determinareMaxim este o funcție care determină elementul cu valoare maximă dintr-un tablou unidimensional cu $n$ elemente denumit vect. Toate tablourile folosite în acest algoritm sunt unidimensionale și vor fi indexate de la $0$. Tabloul t1 are $10$ elemente, t2 are $n$ elemente. Atât t1 cât și t2 sunt inițializate cu valori de $0$.

max <- determinareMaxim(vect, n)
pentru i <- 0, n-1, pas=1 executa
|   t1[vect[i]] <- t1[vect[i]] + 1
|_
pentru i <- 1, max, pas=1 executa
|   t1[i] <- t1[i] + t1[i - 1]
|_
pentru i <- n - 1, 0, pas=-1 executa
|   t2[t1[vect[i]] - 1] <- vect[i]
|   t1[vect[i]] <- t1[vect[i]] - 1
|_
pentru i <- 0, n - 1, pas=1 executa
|   vect[i] <- t2[n - i - 1]
|_

Ce valoare are elementul cu indexul $2026$ din vect, după aplicarea algoritmului, dacă n are valoarea $4000$, iar tabloul vect a fost inițializat (înainte de aplicarea algoritmului propus) folosind vect[i] = i % 10, unde x % y reprezintă restul împărțirii lui x la y?

a) $5$; b) $4$; c) $9$; d) $3$; e) $6$; f) $7$.

Două numere naturale distincte, fiecare având exact $3$ cifre, sunt considerate partenere dacă primele două cifre ale primului număr sunt egale cu ultimele două cifre ale celui de-al doilea număr, în aceeași ordine. Indicați numărul perechilor de numere partenere cu exact $3$ cifre în care primul număr din pereche este strict mai mic decât al doilea.

a) $8100$; b) $3996$; c) $4104$; d) $4005$; e) $8091$; f) $4095$.

Fie următoarea funcție definită în pseudocod, unde x % y reprezintă restul împărțirii lui x la y. Care este rezultatul apelului f(1234567, 0)?

intreg f(intreg n, intreg k) {
    daca (n == 0) returneaza 1;
    rez <- f(n / 10, k);
    daca ((k % 10 - n % 10) != 1)
        rez <- rez + f(n / 10, k * 10 + n % 10);
    returneaza rez;
}

a) $7$; b) $128$; c) $14$; d) $64$; e) $10$; f) $34$.