Atp final toate gtile si probleme PDF

Preview

Summary

Download Atp final toate gtile si probleme PDF

Description

1. Care dintre urmatoarele afirmatii legate de metoda Backtracking sunt adevarate: R: - Este o metoda lenta - Este o metoda costisitoare - Este o metoda de complexitate mare - Solutia se construieste element cu element - Verificarea conditiei de continuare NU garanteaza obtinerea unei solutii rezultat

2. Alg. Dijkstra : R: calculeaza distantele si drumurile minime de la un nod al unui graf la toate celelalte noduri din graf 3. Fie functia : int calc (int n) { int rez ; if (n==0 || n==1) rez=1; else rez=2* calc(n-1)+calc(n-2); return rez; }

calc(3) rez=2*calc(2)+calc(1)=7 =3 =1 calc(2) rez=2*calc(1)+calc(0)=3 =1 =1

Ce va returna apelul calc(3)? R: 7 4. Care dintre urmatoarele afirmatii NU corespunde metodei Greedy : F: problema se descompune in problem de complexitate mai mica sau problem cu rezolvare imediata A: problema poate fi imaginata ca o mult A cu n elemente A: pot exista mai multe submult. diferite acceptabile (solutii posibile), dintre care una este considerata solutie optima pe baza unui criteriu care trebuie maximizat (minimizat) A: o solutie posibila este o multime (B) care indeplineste o conditie data (B este acceptabila) A: se repeat selectarea unui elem. din mult. A de maxim n ori (nr. de elem. corespunzator mult. A)

5. Un graf G este arbore daca G este: R: aciclic si conex

6. Prin recursivitate indirecta (mutuala) se intelege: R: un subprogram A apeleaza un alt subprogram B, iar subprog. B apeleaza subprog. A 7. Fie graful G=(V,E) , cu V={1,2,3,…,9} , E={(1,2);(1,4);(2,7);(2,8);(3,6);(3,9); (4,5);(4,7);(7,8)} si =4 . Ordinea in care sunt vizitate varfurile corespunzatoare parcurgerii in adancime DF este: R: 4,1,2,7,8,5

8. Care dintre urmatoarele afirmatii legate de sortarea crescatoare prin interclasarea unei secvente de nr. reale este adevarata : R: utilizeaza metoda Divide et Impera 9. Determinarea arborelui partial de cost minim se poate face folosind: R: - Alg. lui Prim - Alg. lui Kruskal

10. Un algoritm de tip backtracking genereaza, in ordine, toate permutarile unei multimi cu 4 elem. Primele 3 solutii generate sunt: 1234 , 1243 , 1324 . Care este a 4-a solutie generata de acest algoritm ? R: 1342

11. Care dintre afirmatiile urmatoare referitoate la Divide et Impera NU este adevarata F - descompune problema in problem de complexitate mai mica pt. care se apeleaza alte metode de descompunere diferite de metoda de descompunere initial A - implementarea este realizata de obicei prin subprograme recursive A – descompune problema in problem de complexitate mai mica de acelasi tip cu problema initiala sau in probleme cu rezolvare imediata (primitive) A – combina (asambleaza) solutiile problemelor obtinute in urma decompunerii pt. a obtine Solutia problemei initiale

A – sunt definite subprograme primitive (conditii terminale) a caror solutie este ,,cunoscuta” sau data. 12. Subprogramul : int cauta (float v[] , int n , float val) { int rez; if(n==0) rez=-1; else if (v[n-1]==val) rez=n-1; else rez=cauta(v, n-1, val); return rez; } calculeaza: R: ultima aparitie a unei valori date (val) intr-un vector 13. Care dintre urm. afirmatii referitoare la arborele orientat sunt adevarate? R: -graful suport este conex - graful suport este aciclic - este graf asimetric - este arbore directionat cu radacina

14. In configuratia urmatoare (specifica metodei backtracking):

Este prezentata operatia de: R: incercare esuata 15. Reteaua strazilor auto din Bucuresti se reprezinta correct cu ajutorul structurilor de date : R: graf orientat

16. Care dintre urmatoarele afirmatii legate de subprogramele recursive sunt adevarate: A – pot fi bazate pe o metoda de tip reducere A – pot fi bazate pe o metoda de tip descompunere A - pot fi folosie in rezolvarea problemelor care utilizeaza metoda Divide et Impera A- pot fi folosite la implementarea algoritmilor de parcurgere a arborilor F – nu pot fi scrise pt. implementarea algoritmilor iterative

17. Fie subprogramul : void Test (int I, int n) { printf(“*”); if(i...