Grile si probleme ATP PDF

Preview

Summary

Grile si probleme ATP 2019- Pentru un algoritm recursiv formula recursiva: R: sugereaza conditia de oprire a generarii de noiautoapeluri Care dintre urmatoarele afirmatii sunt echivalente? 1. G este un graf aciclic minimal; 2. G este un graf aciclic maximal; 3. G este un graf conex maximal; 4. G est...

Description

Grile si probleme ATP 2019-2020

1. Pentru un algoritm recursiv formula recursiva: R: sugereaza conditia de oprire a generarii de noiautoapelu ri

2. Care dintre urmatoarele afirmatii sunt echivalente? 1. G este un graf aciclic minimal; 2. G este un graf aciclic maximal; 3. G este un graf conex maximal; 4. G este un graf conex minimal; 5. G este un graf arbore; 6. G esteun digraf. R: 2, 4, 5

3. Pentru un algoritm recursiv formula recursiva: R: arata cand se termina algoritmul

4. Implementarea recursiva este preferabila celei iterative: R: cand implementarea iterativa este foarte complicata iar cea recursiva foarte simpla

5. Fie graful G=(V,E) cu V={(1,2),(1,3),(1,5),(1,7)(2,4)(3,4)(3,6),(4,5),(4,7),(6,7)} v0=1. Ordinea in care sunt vizitate varfurile corespunzator parcurgerii in adancime DF este: R:1,2,4,3,6,5,7;

6. Elementele matricei de adiacenta a unui graf neorientat cu n varfuri : R: sunt simetrice fata de diagonala principal

7. Fie arborele din figura alaturata. Care sunt nodurile frunza? Alegeti o optiune: R: 5,6,7,3,8

8. Fie arborele din figura alaturata. Parcurgerea prin metoda A-preordine Fiu-Frate determina urmatoarea evolutie: 5,9,10,11,12,13,6,7,2,3,8,4,1

9. Care din urmatoarele afirmatii este adevarata pentru un algoritm recursiv. R: poate fi implementat printr-o functie recursiva:

10.Care dintre urmatoarele afirmatii sunt adevarate pentru un algoritm iterativ: R: poate fi implementat printr-o functie recursiva;

11.Fie graful G=(V,E), cu V={1,2,3,4,5,6,7}, E={(1,2),(1,3),(1,5),(1,7),(2,4),(3,4),(3,6),(4,5),(4,7),(6,7)} si v0=1. Ordinea in care sunt vizitate varfurile corespunzator parcurgerii in adancime DF este: R:1,2,3,5,7,4,6

12.Daca G este un graf neorientat, conex si aciclic, atunci graful: R: este arbore

13. Un algoritm de tip backtracking genereaza, in ordine, toate permutarile unei multimi cu 4 elemente {1,2,3,4}. Care este a 4-a solutie generata de acest algoritm? R: 1342

14.Care dintre urmatoarele afirmatii referitoare la arborele orientat nu este adevarata? R: este arbore directionat fara radacina

15.Pentru un algoritm recursiv formula recursiva: R: se aplica pentru descompunerea problemei

16.Un algoritm de tip backtracking genereaza, in ordine, toate permutarile unei multimi cu 5 elemente {a,b,c,d,e}. Care este a 3-a solutie generata de aces algoritm? R:abdce

17.Care din urmatoarele operatii nu fac parte din operatiile specifice metodei optimului local? R: construirea unui element candidat x

18.Graful orientat G este reprezentat prin matricea de adiacenta alaturata. Cate varfuri din graful dat au gradul interior egal cu gradul exterior? R: 2

19.Coada utilizata in implementarea parcurgerii in adancime are rolul: R: nu se foloseste coada la parcurgerea in adancime

20. Parcurgerea generalizata a unui graf se face: R: in adancime sau in latime

1.Fie un grav complet cu 10 varfuri. Care este nr. De muchii pentru acest graf? R:c.45 2. Un algoritm recursive contine : 1)o forma de calcul recursive 2)mai multe forme de calcul recursiv 3)o formula de calcul direct

4)mai multe formule de calcul direct R:d.1 sau 2 si 3 sau 4 3.Fie graful G=(V,E) cu V={1,2,3,4,5} si E={(1,2);(1,4);(2,3);(2,5);(3,4);(3,5);(4;5)}.Determinati care este nr. Minim de muchii care pot fi eliminate din graf astfel incat in graful partial rezultat sa existe exact un vf de grad 0? R:b.4 4.Fie urmatoarea situatie : un subprogram X apeleaza un alt subprogram Y, care apeleaza subprogramul X.Ce tip de recursivitate este aceasta R:a.mutuala 5.Fie urmatorul arbore cu 8 varfuri si radacina R=3 in reprezentarea fiu-frate: Fiu: [7,0,5,6,2,0,0,0] Frate: [0,4,0,0,8,0,0,1] Care este inaltimea arborelui? R:e.3 6.Fie utilizarea metodei Backtracking pentru generarea tuturor numerelor palindrom formate din 4 cifre din multimea {1,2,3}.Exemplu de solutie :1221.Nr. solutiilor identificare sunt: R:c.9 7.Care dintre urmatoarele afirmatii nu este specifica alg. Kruskal R:b.se da un vf initial de la care se pleaca 8.In ceea ce priveste implementarea recursive, care din urmatoarele afirmatii este adevarata: R:d.Se poate aplica numai pt rezolvarea unor probleme complexe, care nu pot fi rezolvate prin implementarea iterative. 9.Fie graful G(V,E) cu 6 varfuri si multimea de muchii E={(1,6);(1,4);(2,4);(2,3);(2,5)}.Identificati nodul ce poate fi ales ca radacina a

arborelui astfel incat fiecare nod care nu este de tip frunza sa aiba un nr.impar de descendenti directi(fii)? R:e.2 10.Fie G un graf arbore.Care dintre urmatoarele afirmatii sunt echivalente: 1)G este graf aciclic maximal 2)G este graf conex minimal 3)G este graf acyclic minimal 4)G este graf conex maximal R:b.1,2 11.Verificarea conexitatii unui graf care este reprezentat prin matricea de adiacenta se poate face utilizand: 1)alg Roy Floyd 2)parcurgerea in adancime 3)alg Dijkstra 4)parcurgerea in latime 5)alg Roy Warshall R:a.2,4,5 12.Intr un graf,drumul Hamiltonian, reprezinta: R:c.Un drum in care fiecare nod apare o singura data 13.Fie graful G(V,E) ,V={1,2,3,4,5,6,7}, E={(1,7,1),(1,2,2),(2,5,2),(2,3,3),(2,6,3),(2,7,3),(3,4,1),(3,5,2),(4,5,1),(5,6,3),(6,7 ,5)}.Aplicand algoritmul lui Prim, care va fi costul arborelui obtinut plecand din vf 2? R:a.10 14.In cee ace priveste metoda Divide et Impera , care din urmatoarele afirmatii nu este adevarata:

R:e.pt aceasta metoda , in general sunt definite subproblemele primitive a caror solutie nu este cunoscuta. 15.Fie un arbore cu radacina R=3, nr de varfuri 8 si cu multimea de muchii E={(1,3),(1,7),(2,5),(3,5),(3,8),(4,5),(4,6)}.Care este parcurgerea A-postordine pt. acest arbore? R:d.2,6,4,5,8,7,1,3;

21.Care dintre urmatoarele afirmatii legate de subprograme recursive nu este adevarata: R: pot fi folosite numai pentru implementarea unor algoritmi recursivi

22.Metoda Greedy este: R: o metoda rapida, de complexitate redusa, pentru obtinerea unei solutii acceptabile nu neaparat cea buna.

23. Care dintre urmatoarele afirmatii nu este valabila pentru algoritmul lui Kruskal: R: dintre arcele disponibile (care nu au fost analizate inca) se alege arcul cu ponderea cea mai mica si care formeaza un ciclu prin adaugarea la arbore.

24. Care dintre urmatoarele afirmatii legate de metoda Backtracking sunt adevarate: R: 1. Este o metoda lenta 2. Este o metoda costisitoare 3. Este o metoda de complexitate mare 4. Solutia se construieste element cu element 5. Verificarea condititi de continuare garanteaza obtinerea unei solutii rezultat

25. Algoritmul Dijkstra: R: calculeaza distantele si drumurile minime de la un nod al unui graf la toate celelalte noduri din graf.

26. Care dintre afirmatii nu este adevarata: R: la recursivitatea directa apelul recursiv se realizeaza prin intermediul mai multor functii care se apeleaza circular

Probleme:

1.

#include using namespace std; int maxim(int* pare, int s, int d) { int a, b, m; if (s == d) return pare[s]; else

{ m = (s + d) / 2; a = maxim(pare, s, m); b = maxim(pare, m + 1, d); if (a > b) return a; else return b; } } int main() { int i, * v, * pare, n; cout n; v = new int[n]; cout v[i]; if (n % 2 == 0) pare = new int[n / 2]; else pare = new int[(n / 2) + 1]; for (i = 0; i < n; i = i + 2) pare[i] = v[i]; int maxi = maxim(pare, 0, n - 1);

cout m; for (i=1; i> x >> y; ad[x][y]=1; } f.close(); }

void imp2(int n, int ad[21][21], int &l, int v[11]){ int i, j, *grad{new int[n+1]{}}; for (i=1; i...