Test inițial · Clasa a XII-a

1.00 nota curentă oficiu 1.00 · grilă 0.00 · probleme 0.00

Cum se rezolvă: problemele se scriu în C++. Fiecare subpunct are punctajul lui, iar baremul conține rezolvarea completă, comentată. Subiectul III de BAC se construiește aproape în întregime din materia verificată aici — tratează testul ca pe o simulare, nu ca pe o formalitate.

Subiectul I — grilă

5 × 0,2 p = 1 p

Un singur răspuns corect. Apeși pe variantă și afli imediat dacă ai nimerit, cu explicație.

Subiectul II — probleme

4 × 2 p = 8 p

Fiecare problemă e împărțită pe subpuncte cu punctaj propriu. Rezolvi pe hârtie sau în editor, apoi deschizi baremul și te autoevaluezi: apasă pe butonul din dreapta fiecărui subpunct pentru nerezolvat → parțial (jumătate) → corect.

Backtracking: schema și o variație

M01 · M022 p

Se citește un număr natural n (n ≤ 10). Toate generările se fac cu metoda backtracking, folosind vectorul soluție sol.

a)Scrie schema generală recursivă back(k) și explică rolul funcției valid(k) în cazul permutărilor.0,5 p

b)Scrie programul complet care generează toate permutările mulțimii {1, 2, …, n}.0,75 p

c)Modifică metoda pentru a genera toate submulțimile mulțimii {v₁, …, vₙ} care au suma elementelor egală cu o valoare S citită.0,75 p

Barem de corectare & rezolvare

a) 0,5 p

Schema este aceeași pentru toate generările — se schimbă doar valid și mulțimea de valori încercate. Pentru permutări, valid(k) verifică dacă valoarea aleasă pe poziția k nu a mai apărut pe pozițiile 1..k−1.

C++

void back(int k) {
    for (int i = 1; i <= n; i++) {      // toate valorile candidate
        sol[k] = i;
        if (valid(k)) {                 // e acceptabila pe pozitia k ?
            if (k == n) afisare();      // solutie completa
            else back(k + 1);           // trec la pozitia urmatoare
        }
    }
}

b) 0,75 p

Pentru n = 3 se afișează, în această ordine: 1 2 3 / 1 3 2 / 2 1 3 / 2 3 1 / 3 1 2 / 3 2 1. Varianta cu vector de frecvență (folosit[]) în locul buclei din valid este și ea corectă și mai rapidă.

C++

#include <iostream>
using namespace std;

int n, sol[15];

bool valid(int k) {
    for (int i = 1; i < k; i++)
        if (sol[i] == sol[k]) return false;   // valoare deja folosita
    return true;
}

void afisare() {
    for (int i = 1; i <= n; i++) cout << sol[i] << ' ';
    cout << '\n';
}

void back(int k) {
    for (int i = 1; i <= n; i++) {
        sol[k] = i;
        if (valid(k)) {
            if (k == n) afisare();
            else back(k + 1);
        }
    }
}

int main() {
    cin >> n;
    back(1);
    return 0;
}

c) 0,75 p

Se schimbă semnificația vectorului soluție: sol[k] ∈ {0, 1} înseamnă „elementul k nu se ia / se ia". Aici valid nu mai restrânge nimic — condiția se testează la soluție completă.
Optimizare (bonus): se poate ține suma parțială și se taie ramura imediat ce depășește S (pentru valori pozitive).

C++

int n, S, v[15], sol[15];

void afisare() {
    for (int i = 1; i <= n; i++)
        if (sol[i] == 1) cout << v[i] << ' ';
    cout << '\n';
}

void back(int k) {
    for (int i = 0; i <= 1; i++) {      // 0 = nu iau, 1 = iau
        sol[k] = i;
        if (k == n) {
            int s = 0;
            for (int j = 1; j <= n; j++)
                if (sol[j] == 1) s += v[j];
            if (s == S) afisare();
        } else back(k + 1);
    }
}

Graf neorientat: grade și componente conexe

M03 · M052 p

Se citesc n (numărul de noduri, n ≤ 100) și m (numărul de muchii), apoi m perechi de noduri care descriu muchiile. Graful se reține prin matricea de adiacență.

Exemplun = 6, m = 4
1 2 2 3 1 3 4 5

a) gradele: 2, 2, 2, 1, 1, 0
b) nod izolat: 6 · grad maxim 2, nodurile 1, 2, 3
c) 3 componente conexe: {1,2,3}, {4,5}, {6}

a)Construiește matricea de adiacență și afișează gradul fiecărui nod.0,5 p

b)Afișează nodurile izolate și nodurile de grad maxim.0,75 p

c)Determină și afișează numărul de componente conexe ale grafului.0,75 p

Barem de corectare & rezolvare

a) 0,5 p

Graf neorientat ⇒ matricea este simetrică: se setează și a[x][y], și a[y][x]. Gradul unui nod = suma elementelor de pe linia lui.

C++

#include <iostream>
using namespace std;

int n, m, a[105][105], g[105];

int main() {
    int x, y;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;        // neorientat -> simetric
    }

    for (int i = 1; i <= n; i++) {
        g[i] = 0;
        for (int j = 1; j <= n; j++) g[i] += a[i][j];
        cout << "grad(" << i << ") = " << g[i] << '\n';
    }
    return 0;
}

b) 0,75 p

Nod izolat = nod de grad 0 (nu aparține niciunei muchii). Gradul maxim se caută într-o parcurgere, iar nodurile care îl ating într-a doua.

C++

cout << "Noduri izolate: ";
for (int i = 1; i <= n; i++)
    if (g[i] == 0) cout << i << ' ';
cout << '\n';

int gmax = 0;
for (int i = 1; i <= n; i++)
    if (g[i] > gmax) gmax = g[i];

cout << "Grad maxim = " << gmax << ", nodurile: ";
for (int i = 1; i <= n; i++)
    if (g[i] == gmax) cout << i << ' ';

c) 0,75 p

Ideea: pornești o parcurgere (DFS sau BFS) din fiecare nod nevizitat. De fiecare dată când trebuie să pornești una nouă, ai descoperit o componentă nouă.
Graful este conex dacă numărul de componente este 1.

C++

bool viz[105];

void dfs(int x) {
    viz[x] = true;
    for (int y = 1; y <= n; y++)
        if (a[x][y] == 1 && !viz[y]) dfs(y);
}

// in main:
int nc = 0;
for (int i = 1; i <= n; i++)
    if (!viz[i]) { nc++; dfs(i); }      // componenta noua

cout << "Componente conexe: " << nc;
if (nc == 1) cout << " -> graful este CONEX";

Drumuri de cost minim — Dijkstra

M07 · M082 p

Se dă graful ponderat neorientat din figură, cu 5 noduri. Nodul 1 este sursa.

Exemplu

muchii (cost): [1,2]=4 · [1,3]=1 · [2,3]=2 · [2,4]=5 · [3,5]=8 · [4,5]=3

a)Aplică algoritmul lui Dijkstra din nodul 1 și completează tabelul distanțelor, pas cu pas. Precizează la final costul minim până la fiecare nod și drumul efectiv până la nodul 5.0,75 p

b)Scrie implementarea O(n²) a algoritmului, cu reconstruirea drumului prin vectorul tata.0,75 p

c)De ce cere Dijkstra costuri nenegative? Prin ce diferă de algoritmul lui Prim, deși ambele sunt Greedy și arată aproape la fel?0,5 p

Barem de corectare & rezolvare

a) 0,75 p

Se pornește cu d[i] = c[1][i], se fixează de fiecare dată nodul nevizitat cu d minim și se relaxează vecinii lui.

Pas | Nod fixat | d[1] d[2] d[3] d[4] d[5] | observatie
----+-----------+--------------------------+---------------------------
ini |     1     |   0    4    1    oo   oo | vecinii directi ai lui 1
 1  |  3 (d=1)  |   0    3    1    oo    9 | 1+2=3 < 4  -> d[2] SCADE
 2  |  2 (d=3)  |   0    3    1     8    9 | 3+5=8      -> d[4]
 3  |  4 (d=8)  |   0    3    1     8    9 | 8+3=11 > 9 -> NU schimba
 4  |  5 (d=9)  |   0    3    1     8    9 | gata

Costuri minime din 1:  d = [0, 3, 1, 8, 9]

tata[3]=1, tata[2]=3, tata[4]=2, tata[5]=3
Drum 1 -> 5 :  1 - 3 - 5   (cost 1 + 8 = 9)
Drum 1 -> 4 :  1 - 3 - 2 - 4 (cost 1 + 2 + 5 = 8), mai ieftin decat 1-2-4 = 9

b) 0,75 p

Structura de date: matricea costurilor, cu INF (nu 0!) acolo unde muchia lipsește — pentru că un cost poate fi chiar 0. Bucla exterioară se execută de n−1 ori: atâtea noduri mai sunt de fixat după sursă.

C++

const int INF = 1000000000;
int n, c[105][105], d[105], tata[105];
bool viz[105];

void dijkstra(int start) {
    for (int i = 1; i <= n; i++) {
        d[i] = c[start][i];
        if (c[start][i] < INF && i != start) tata[i] = start;
    }
    d[start] = 0;  viz[start] = true;

    for (int pas = 1; pas < n; pas++) {
        int u = -1;
        for (int i = 1; i <= n; i++)                 // alegerea lacoma
            if (!viz[i] && (u == -1 || d[i] < d[u])) u = i;
        if (u == -1 || d[u] == INF) break;
        viz[u] = true;                               // FIXAT definitiv

        for (int v = 1; v <= n; v++)                 // relaxarea
            if (!viz[v] && d[u] + c[u][v] < d[v]) {
                d[v] = d[u] + c[u][v];
                tata[v] = u;
            }
    }
}

// initializarea matricei costurilor:
//   c[i][j] = (i == j) ? 0 : INF;  apoi  c[x][y] = c[y][x] = cost;

c) 0,5 p

Costuri ≥ 0: când fixezi nodul u cu cea mai mică estimare, orice alt drum spre u ar trece prin noduri cu estimări ≥ d[u] și ar mai aduna costuri — deci nu-l poate ieftini. Cu muchii de cost negativ, un drum „mai lung" ar putea scădea totalul, iar certificatul cade: Dijkstra dă rezultate greșite.

Dijkstra vs Prim — aceeași schemă, alt criteriu de alegere:
• Dijkstra minimizează d[u] + c[u][v] — distanța de la sursă; rezultatul e un set de drumuri minime dintr-un nod.
• Prim minimizează doar c[u][v] — costul muchiei care leagă un nod nou de arbore; rezultatul e arborele parțial de cost total minim (toată rețeaua, cablu minim).
Aceasta este capcana clasică de la BAC: se dă un graf și se cere să spui care algoritm produce ce rezultat.

Arbori binari și arbore binar de căutare

M10 · M112 p

Un arbore binar cu 7 noduri are parcurgerea în preordine (RSD): 5 3 2 4 8 7 9 și parcurgerea în inordine (SRD): 2 3 4 5 7 8 9.

a)Reconstruiește arborele și scrie parcurgerea lui în postordine (SDR).0,75 p

b)Este acest arbore un arbore binar de căutare? Justifică. Inserează valoarea 6 și precizează al cui fiu devine.0,75 p

c)Care este înălțimea arborelui inițial (numărul de muchii de la rădăcină la cea mai depărtată frunză) și câte frunze are? Câte noduri poate avea, cel mult, un arbore binar de înălțime h?0,5 p

Barem de corectare & rezolvare

a) 0,75 p

Metoda: primul element din preordine este rădăcina; în inordine el taie lista în subarborele stâng (înainte) și cel drept (după); se repetă recursiv.

Pas 1: preordine 5 ... -> radacina = 5
       inordine: [2 3 4]  5  [7 8 9]
                  stanga      dreapta

Pas 2: subarborele STANG, preordine 3 2 4 -> radacina = 3
       inordine [2] 3 [4]  ->  2 la stanga, 4 la dreapta

Pas 3: subarborele DREPT, preordine 8 7 9 -> radacina = 8
       inordine [7] 8 [9]  ->  7 la stanga, 9 la dreapta

Arborele:              5
                    /     \
                   3       8
                  / \     / \
                 2   4   7   9

Postordine (SDR): 2 4 3 7 9 8 5

b) 0,75 p

Da, este ABC. Justificarea cea mai scurtă: parcurgerea în inordine este 2 3 4 5 7 8 9, adică strict crescătoare — proprietatea care caracterizează un arbore binar de căutare.

Inserarea lui 6 coboară din rădăcină comparând: 6 > 5 → dreapta (la 8); 6 < 8 → stânga (la 7); 6 < 7 → stânga, unde nu există nimic. Deci 6 devine fiul stâng al lui 7.

C++

Nod* inserare(Nod *r, int x) {
    if (r == NULL) {
        Nod *nou = new Nod;
        nou->info = x;
        nou->st = nou->dr = NULL;
        return nou;
    }
    if (x < r->info)      r->st = inserare(r->st, x);
    else if (x > r->info) r->dr = inserare(r->dr, x);
    return r;                        // valorile egale se ignora
}

Dupa inserarea lui 6:        5
                          /     \
                         3       8
                        / \     / \
                       2   4   7   9
                              /
                             6

c) 0,5 p

Arborele inițial: rădăcina 5 → nivelul 0, nodurile 3 și 8 → nivelul 1, nodurile 2, 4, 7, 9 → nivelul 2. Înălțimea este 2, iar frunzele sunt 4: 2, 4, 7 și 9.

Un arbore binar de înălțime h are cel mult 2^(h+1) − 1 noduri (arborele plin): pentru h = 2 → 7 noduri — exact cazul nostru, deci arborele este plin. De aici vine și puterea ABC-ului: dacă rămâne echilibrat, căutarea face O(log n) pași; dacă degenerează în „liană" (inserare în ordine crescătoare), ajunge la O(n).

Nota ta

1.00

Începe cu grila — nota pornește de la 1 punct din oficiu.

← Recapitulează materia