Admitere Informatică 2024 — 22 iulie — Varianta A

Fie funcția dată prin următorul pseudocod (% reprezintă restul împărțirii întregi). Care dintre următoarele apeluri au ca rezultat numai valori pare?

intreg f(intreg n, intreg y) {
  dacă (n > 0)
    dacă (n % 2 == 0) returnează f(n - 1, y + 1) + y;
    altfel returnează f(n - 1, y + 1);
  altfel returnează 0;
}

a) f(117, 200), f(222, 300), f(322, 485), f(422, 653); b) f(116, 100), f(220, 181), f(321, 281), f(420, 551); c) f(117, 130), f(222, 461), f(323, 771), f(422, 891); d) f(117, 240), f(222, 480), f(322, 795), f(422, 833); e) f(116, 150), f(222, 81), f(321, 331), f(420, 671); f) f(118, 241), f(222, 291), f(322, 481), f(422, 451).

Un graf de tip scară are 2n noduri și este reprezentat ca în figură. [Figura: graf „scară" — nodurile x1,…,xn pe un rând, y1,…,yn pe rândul de jos; muchii: xi—x(i+1), yi—y(i+1) pentru 1≤i<n și xi—yi pentru 1≤i≤n.] Dacă n=11, în câte moduri putem alege n dintre muchiile acestuia, astfel încât oricare două dintre ele să nu aibă capete comune?

a) 377; b) 55; c) 75; d) 98; e) 144; f) 110.

Definim un tip înregistrare pentru reținerea unei fracții de forma a/b unde a este numărătorul și b este numitorul.

typedef struct fractie { int a, b; } Fractie;

Fie un vector care reține 31 de fracții în care primul element este pe poziția 0 și reține fracția 1/1. Definim restul elementelor din vector după următoarele formule, unde i>=0:

v[2*i+1].a = v[i].a;
v[2*i+1].b = v[i].a + v[i].b;
v[2*i+2].a = v[i].a + v[i].b;
v[2*i+2].b = v[i].b;

Ce fracție va reține elementul de pe poziția 9 din vector (adică v[9])?

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

Următoarea secvență de cod generează, folosind cifre de la 0 la 5, numere de 5 cifre. Primul șir afișat este 00000. La un moment dat se afișează 11521. La al câtelea apel al funcției genereaza se întâmplă acest lucru?

void genereaza(char* nr, int p) {
  if (p == 5) {
    nr[p] = '\0';
    printf("%s\n", nr); // cout<<nr<<endl;
    return;
  }
  for (int cifra = 0; cifra <= 5; cifra++) {
    nr[p] = '0' + cifra;
    genereaza(nr, p + 1);
  }
}
int main() {
  char nr[6];
  genereaza(nr, 0);
  return 0;
}

a) 2024; b) 1701; c) 1704; d) 2050; e) 1706; f) 2048.

Fie $v_1$ și $v_2$ doi vectori unidimensionali cu $n$ și, respectiv, $m$ elemente întregi sortate crescător. Să se determine diferența minimă absolută între orice element din $v_1$ și orice element din $v_2$. Care este complexitatea algoritmului optim pentru această problemă? a) $O(\log(n^m))$; b) $O(n\cdot\log(m))$; c) $O(n^2\cdot\log(m))$; d) $O(1)$; e) $O(n+m)$; f) $O(m^2\cdot\log(n))$.