examen_algoritmi

Examen Algoritmi și Structuri de Date - 19.08.2025

Durata: 3 ore
Total: 100 puncte (+15p bonus)

Instrucțiuni

• Clonați acest repository la începutul examenului.
• Rezolvați fiecare problemă în fișiere separate (ex. problema1.py, problema2.py etc.).
• La final, faceți commit și push cu soluțiile voastre.
• Se acordă puncte parțiale pentru pași corecți, chiar dacă soluția nu este completă.
• Nota finală = punctaj_total / 10 (maxim 10 în catalog).
• Problema 8 este bonus și nu afectează nota de trecere.

Problema 1 – Sortare (20p)

Implementează algoritmul Merge Sort pentru un vector de numere întregi și afișează vectorul sortat.

• Cod corect: 15p
• Complexitatea algoritmului (cel mai bun și cel mai rău caz): 5p

Problema 2 – Căutare liniară (15p)

Scrie o funcție care caută un element într-o listă folosind căutare liniară.

• Cod corect: 10p
• Exemplu de rulare cu input și output: 5p

Problema 3 – Căutare într-o matrice sortată (15p)

Dată o matrice sortată crescător pe linii și coloane, scrie o funcție care verifică dacă un element x există.

• Cod corect: 10p
• Explicația pașilor algoritmului: 5p

Problema 4 – Stivă (20p)

Implementează o stivă (stack) cu operațiile push, pop, peek.
Aplică următoarele operații și afișează rezultatul final:
push(5), push(7), pop(), push(9), peek().

• Implementare structură și operații: 15p
• Rezultat final corect: 5p

Problema 5 – Algoritmi pe grafuri: A* (10p)

a) Explică pe scurt principiul algoritmului A*: funcția de cost f(n) = g(n) + h(n) (unde g = cost real, h = euristică). 5p
b) Dă un exemplu simplu (matrice 3x3 cu obstacol) și arată pașii principali ai algoritmului. 5p

Problema 6 – Fibonacci recursiv (10p)

Scrie o funcție recursivă care calculează Fibonacci(n).

• Cod corect: 7p
• Exemplu de apel și rezultat: 3p

Problema 7 – Criba lui Eratostene (10p)

Scrie o funcție care generează toate numerele prime ≤ n folosind Criba lui Eratostene.

• Cod corect: 7p
• Exemplu de rulare: 3p

Problema 8 – Bonus (max. 15p)

Implementează în Python o clasă Graph care să permită:

• adăugarea de noduri și muchii (5p)
• o metodă bfs(start) care să parcurgă graful în lățime (5p)
• o metodă shortest_path(start, end) care să returneze drumul minim (5p)