Examen PA Var2
Test Your Knowledge on Algorithms and Graph Theory
Welcome to the "Examen PA Var2" quiz, where you can challenge your understanding of algorithms and graph theory. This quiz consists of 15 questions designed to assess your knowledge in various algorithmic concepts and techniques.
Engage with topics such as:
- Graph Traversal Techniques
- Algorithm Complexity
- Minimum Spanning Trees
- Residual Graphs
- Randomized Algorithms
1) Care afirmatie este adevarata:
A. Algoritmul NC-1 foloseste ca parte a sa algoritmul AC-1
B. Algoritmul NC-1 foloseste ca parte a sa functia REVISE
C. Algoritmul AC-3 foloseste ca parte a sa functia REVISE
D. Algoritmul AC-1 nu foloseste ca parte a sa functia REVISE
2) Functia REVISE se refera la relatia dintre:
A. Celelalte variante sunt incorecte
B. 2 variabile
C. 3 variabile
D. Toate variabilele problemei
3) Care afirmatie este adevarata pentru parcurgerea in latime (BFS)?
A. Nu se garanteaza ca parcurge tot graful si foloseste o stiva ca structura de date
B. Se garanteaza ca parcurge tot graful si foloseste o coada ca structura de date
C. Nu se garanteaza ca parcurge tot graful si foloseste o coada ca structura de date
D. Se garanteaza ca parcurge tot graful si foloseste o stiva ca structura de date
4) Care afirmatie este adevarata pentru parcurgerea in adancime (DFS)?
A. Se garanteaza ca parcurge tot graful si foloseste o coada ca structura de date
B. Nu se garanteaza ca parcurge tot graful si foloseste o stiva ca structura de date
C. Se garanteaza ca parcurge tot graful si foloseste o stiva ca structura de date
D. Nu se garanteaza ca parcurge tot graful si foloseste o coada ca structura de date
5) Facem urmatoarele notatii: - Alg_sort_top = algoritmul de sortare topologica - Alg_det_CTC = algoritmul de determinare a CTC Care afirmatie este adevarata?
A. Alg_sort_top are complexitate temporala polinomiala, iar Alg_det_CTC are copmplexitate temporala suprapolinomiala
B. Alg_sort_top si Alg_det_CTC au complexitate temporala polinomiala
C. Alg_sort_top are complexitate temporala suprapolinomiala, iar Alg_det_CTC are complexitate temporala polinomiala
D. Alg_sort_top si Alg_det_CTC au complexitate temporala suprapolinomiala
6) Fie G=(V,E) un graf neorientat si (u,v) in E. (u,v) este punte in G daca:
Exista x, y in V, x diferit de y, astfel incat orice drum x .. Y in G contine muchia (u,v)
Exista x, y in V, x diferit de y, astfel incat exista drum x .. Y in G care contine muchia (u,v)
Orice x, y in V, x diferit de y, orice drum x .. Y in G contine muchia (u,v)
E. Orice x, y in V, x diferit de y, exista drum x .. Y in G care contine muchia (u, v)
7) Fie G=(V,E) un graf neorientat si u in V. U este punct de articulatie in G daca:
Orice x, y in V \ {u}, x diferit de y, orice drum x .. Y in G trece prin u
Orice x, y in V \ {u}, x diferit de y, exista drum x .. Y in G care trece prin u
Exista x, y in V \ {u}, x diferit de y, astfel incat exista drum x .. Y in G care trece prin u
Exista x, y in V \ {u}, x diferit de y, astfel incat orice drum x .. Y in G trece prin u
8) Algoritmul Bellman-Ford calculeaza:
Cate un drum de cost minim de la un nod s din graf la orice alt nod din graf
Cate un drum de cost minim intre orice 2 noduri din graf
Cate un drum de cost maxim intre orice 2 noduri din graf
Cate un drum de cost maxim de la un nod s din graf la orice alt nod din graf
9) Algoritmul Floyd-Warshall calculeaza:
Cate un drum de cost minim de la un nod s din graf la orice alt nod din graf
B. Cate un drum de cost minim intre orice 2 noduri din graf
C. Cate un drum de cost maxim de la un nod s din graf la orice alt nod din graf
D. Cate un drum de cost maxim intre orice 2 noduri din graf
10) Care afirmatie este adevarata?
Algoritmii Prim si Kruskal au complexitate temporala suprapolinomiala
Complexitatea temporala a algoritmului Prim depinde de implementarea multimilor disjuncte
Complexitatea temporala a algoritmului Kruskal se calculeaza asemanator cu cea a algoritmului Dijkstra
Complexitatea temporala a algoritmului Prim se calculeaza asemanator cu cea a algoritmului Dijkstra
11) (u,v) se numeste arc rezidual daca:
F(u,v) > c(u,v)
F(u,v) = c(u,v)
F(u,v) < c(u,v)
F(u,v) >= c(u,v)
12) Care dintre urmatorii algoritmi este algoritm informat irevocabil?
A. A*
B. Gradient maxim
C. Best first
D. Explorare lacoma
13) Care afirmatie este adevarata?
Un algoritm se numeste complet daca a fost scris intregul lui cod si a fost testat pe un numar suficient de mare de probleme.
Un algoritm se numeste optimal daca are o complexitate temporala mai mica decat a tuturor celorlalti algoritmi cunoscuti pentru o problema data.
Un algoritm se numeste optimal daca descopera solutia optima a problemei.
Un algoritm se numeste complet daca poate rezolva orice problema data.
14) Care afirmatie este adevarata?
Algoritmii Las Vegas sunt algoritmi aleatorii, iar algoritmii Monte Carlo nu sunt algoritmi aleatorii
Algoritmii Monte Carlo sunt algoritmi aleatorii, iar algoritmii Las Vegas nu sunt algoritmi aleatorii
Problema capitolelor cartii se rezolva (conform cursului) cu un algoritm Las Vegas
Problema capitolelor cartii se rezolva (conform cursului) cu un algoritm Monte Carlo
15) Care afirmatie este adevarata?
In general algoritmii Minimax si alfa-beta au complexitate temporala foarte scazuta
Algoritmul Minimax reprezinta o optimizare a algoritmului alfa-beta
In cazul ideal algoritmul Minimax are o complexitate temporala mai scazuta decat algoritmul alfa-beta
Algoritmul alfa-beta reprezinta o optimizare a algoritmului Minimax
{"name":"Examen PA Var2", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"Welcome to the \"Examen PA Var2\" quiz, where you can challenge your understanding of algorithms and graph theory. This quiz consists of 15 questions designed to assess your knowledge in various algorithmic concepts and techniques.Engage with topics such as:Graph Traversal TechniquesAlgorithm ComplexityMinimum Spanning TreesResidual GraphsRandomized Algorithms","img":"https:/images/course5.png"}