Examen PA Var2

A vibrant and engaging educational graphic representing various algorithms like sorting, traversal, and pathfinding, with visual elements of graphs and nodes in a colorful design.

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

15 Questions4 MinutesCreated by LearningTree42

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

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

Examen PA Var2

Test Your Knowledge on Algorithms and Graph Theory

More Quizzes