Subiecte examen SDA

Subiecte examen SDA

sesiunea vara

1. Din fisierul "p1.txt" se citeste un arbore dat sub forma parantezata. Arborele contine identificatori (un identificator este un  cuvant ce incepe cu o litera si contine litere, cifre sau caracterul '_' ). Se cere sa se afiseze urmatoarele informatii:
1. Numarul de noduri
2. Numarul de muchii
3. Inaltimea
4. Arborele parcurs in preordine

Exemplu:

2. Fisierul "p2.txt" contine identificatori, cate unul pe linie (un identificator este un  cuvant ce incepe cu o litera si contine litere, cifre sau caracterul '_'). Se cere sa se urmatoarele:
1. Sa se introduca acesti identificatori intr-un arbore de cautare
2. Sa se afiseza arborele sub forma parantezata
3. Sa se afiseze identificatorii sortati lexicografic descrescator folosind urmatorul algoritm:

i. i.cat timp mai sunt noduri in arbore

ii. ii.Gaseste cel mai mare element

iii. iii.Afiseaza elementul gasit

iv. iv.Sterge nodul din arbore

Exemplu:

3. In fisierul "p3.txt" se gasesc mai multe numere intregi. Se cere sa se sorteze aceste numere dupa urmatorul algoritm:
1. Se introduc toate numerele intr-un heap
2. Se scoate pe rand elementul din varful heap-ului

Exemplu:

4. Din fisierul "p4.txt" se citeste un graf neorientat, precizat prin numarul de noduri, numarul de muchii si muchiile sale. Se cere sa se afiseze componentele conexe ale grafului folosind o parcurgere DF. Arborele va fi retinut in reprezentarea prin liste de adiacenta (fiecare nod retine vecinii sai). Se cere deasemenea sa se precizeze complexitatea algoritmului si sa se argumenteze aceasta complexitate.

Exemplu:

5. Din fisierul "p5.txt" se citeste un graf orientat, precizat prin numarul de noduri, numarul de muchii si muchiile sale. Costul este acelasi pentru toate muchiile grafului. Se cere sa se afiseze lungimea drumurilor (evident cele mai scurte) de la nodul 0 la toate celelalte noduri la care se poate ajunge. Pentru aceasta se va folosi o parcurgere BF (nu se accepta algoritmul Floyd sau Dijkstra). Graful va fi retinut prin liste de adiacenta (fiecare nod retine vecinii sai). Se cere deasemenea sa se precizeze complexitatea algoritmului si sa se argumenteze aceasta complexitate.

Exemplu:

6. Din fisierul "p6.txt" se citesc mai multe relatii de forma "Id1 < Id2" sau "Id1 > Id2" (unde id1 si id2 sunt identificatori, i.e. un identificator este un  cuvant ce incepe cu o litera si contine litere, cifre sau caracterul '_'). Se cere sa se gaseasca o sortare topologica a acestor identificatori (o insiruire a acestor identificatori in asa fel incat daca exista relatia "Id1 < Id2" atunci Id1 apara inaintea lui Id2, iar daca exista relatia "Id3 > Id4" atunci Id3 apare dupa Id4. Evident exista cazuri cand aceasta sortare nu este posibile (Ex. Id1 > Id2, Id1 < Id2) caz in care porgramul va genera eroare.

Exemplu:

7. Din fisierul "p7.txt" se citeste un graf neorientat, precizat prin numarul de noduri, numarul de muchii si muchiile sale.Sa se determine arborele partial de cost minim folosind algoritmul lui Kruskal. Pentru implementare se vor folosi multimi disjuncte (evident cu path compression si  union by size/union by rank).

Algoritmii Kruskal si Prim produc acelasi arbore partial de cost minim ? Argumentati raspunsul.

Exemplu:

8. Din fisierul "p8.txt" se citeste un graf neorientat, precizat prin numarul de noduri, numarul de muchii si muchiile sale. Se cere sa se afiseze drumurile minime (si costul acestora) dintre nodul 0 si toate celelalte noduri. Se va folosi algoritmul Dijkstra.

Exemplu:

9. Din fisierul "p9.txt" se citeste un graf neorientat, precizat prin numarul de noduri, numarul de muchii si muchiile sale. Se doreste afisarea lungimii drumurilor minime intre oricare doua noduri i si j. Deasemenea se va calcula si lungimea "masurata in noduri" intre oricare doua noduri (i.e. cate noduri contine drumul minim de la i la j). Se va folosi algoritmul Floyd-Warshall.

Exemplu: