Fie noțiunea de arbore orientat. Care din următoarele afirmații referitoare la acesta sunt adevărate?

1) grateful suport este ciclic

2) Este arbore direcționat cu rădăcina

3) Este Graf simetric și ciclic

4) Grateful suport este neconex

5) Este arbore direcționat fără rădăcina

Daca în cadrul unui arbore se elimina o muchie atunci se obține:

Care dintre următoarele afirmații NU este adevarata în ceea ce privește metoda Backtracking?

Fie un Graf neorientat și următoarele noțiuni: 1. Drum; 2. Lanț; 3. Circuit simplu 4. Circuit elementar; 5. Ciclu simplu; 6. Lungimea unui drum

In ceea ce privește metoda Divide et Impera, care dintre următoarele afirmații NU este adevarata:

Care dintre urmatoarele afirmații NU este specifica algoritmului Kruskal?

Un algoritm recursiv conține: 1. O formula de calcul recursiv 2. Mai multe formule de calcul recursiv 3. O formula de calcul direct 4. Mai multe formule de calcul direct

Care dintre următoarele operații sunt specifice metodei Greedy: 1. Adăugare, 2. Initializare, 3. Eliminare, 4. Verificare, 5. Alegerea, 6. Combinarea

Verificarea conexitatii unui Graf care este reprezentat prin matricea de adiacentă se poate face utilizând: 1. Algoritmul Roy-Floyd, 2. Parcurgerea în adâncime, 3. Dijkstra 4. Parcurgerea în lățime 5. Algoritmul Roy-Warshall

Ce metoda de sortare mentionata mai jos permite compararea și rearanjarea elementelor aflate la distante mai mari în vector:

Fie următoarele afirmații:

1) G este arbore

2) G este Graf aciclic și conex

3) G este graf conex minimal

4) G este graf conex maximal

5) G este graf fara cicluri, maximal in raport cu aceasta proprietate

6) G este graf fara cicluri, minimal in raport cu aceasta proprietate

Fie G un graf arbore. Care dintre următoarele afirmații sunt echivalente? 1. G este graf aciclic maximal; 2. G este graf conex minimal; 3. G este graf aciclic minimal; 4. G este graf conex maximal

Într-un graf, drumul hameltonian reprezintă:

.Care din urmatoarele afirmatii referitoare la metoda Divide et Impera sunt adevarate? 1. este utilizata in rezolvarea unor probleme complexe; 2.implementarea este realizata de obicei prin subprograme recursive; 3.se aplica pentru problemele care pot fi descompuse in probleme cu complexitate mai mica; 4. rezolvarea problemelor rezultate in urma descompunerii este mai usoara decat rezolvarea intregii probleme initiale; 5.pentru fiecare din problemele rezultate in urma descompunerii se aplica un procedeu diferit de descompunere

Elementele matricei de adiacentă a unui graf neorientat cu n vârfuri:

In configuratia următoare este prezentata:

v1 … vi-1 | xi … xn

c1 … ci-1 | ci vida vida

In configuratia următoare este prezentata:

… vi-1 | xi xi+1 … … vi-1 vi | xi+1 …

…. ci-1 | ci vida … -> …. ci-1 ci u vi | vida …

In configuratia următoare este prezentata:

… vi-1 | xi xi+1 … … vi-1 vi | xi+1 …

…. ci-1 | ci vida … === …. ci-1 ci u vi | vida …

… vn | … vn-1 … cn | <<< … cn-1

Care din următoarele afirmații legate de subprogramele recursive NU este adevarata:

. Parcurgerea generalizată a unui graf se face:

Care din urmatoarele afirmatii referitoare la metoda Divide Et Impera NU este adevarata:

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:

Reteaua strazilor auto din Bucuresti se reprezinta corect cu ajutorul structurii de date:

Care din urmatoarele afirmatii legate de subprogramele recursive sunt adevarate: 1. pot fi bazate pe o metoda de tip reducere

2. pot fi bazate pe o metoda de tip descompunere

3. pot fi folosite in rezolvarea problemelor care utilizeaza metoda divide et impera

4. pot fi folosite la implementarea algoritmilor de parcurgere a arborilor

5. nu pot fi scrise pentru implementarea unor algoritmi iterativi

. Care din urmatoarele afirmatii NU este valabila pentru algoritmul lui Kruskal

Metoda Greedy:

Un graf reprezentat prin matrice de adiacenta poate fi verificat daca este conex prin urmatoarele metode:

1. folosind parcurgerea in adancime

2. folosind parcurgerea in latime

3. folosind matricea existentei drumurilor

4. folosind metoda backtracking

Secventa realizeaza:

for (inc = n/2; inc > 0; inc = inc /2)

for(I = inc; I < n; I ++)

for (j = I – inc; (j >= 0) && (v[j] >= v[j + inc] ); j = j – inc)

{ a = v[j]; v[j] = v[j + inc]; v [j + inc] = a; }

Daca G este un graf neorientat, conex si aciclic, atunci graful:

Care din urmatoarele afirmatii legate de subprogramele recursive NU este adevarata:

Intr-un graf neorientat G, notam cu n nr de varfuri si cu m nr de muchii. Daca graful este un arbore atunci intre n si m exista urmatoarea relatie matematica:

Care din urmatoarele operatii NU fac parte din operatiile specifice metodei optimului local:

1. alegerea unui element candidat x din multimea A

2. construirea unui element candidat x

3. verificarea acceptabilitatii elementului ales

4. adaugarea elementului ales la solutia partiala, .. ea ramane acceptabila

5. eliminarea elementului x selectat din solutia problemei

Care din urmatoarele afirmatii referitoare la metoda Divide et Impera sunt adevarate?

1. este utilizata in rezolvarea unor probleme complexe

2. implementarea este realizata de obicei prin subprograme recursive

3. se aplica pentru problemele care pot fi descompuse in probleme cu complexitate mai mica

4. rezolvarea problemelor rezultate in urma descompunerii este mai usoara decat rezolvarea intregii probleme initiale

5. pentru fiecare din problemele rezultate in urma descompunerii se aplica un procedeu diferit de descompunere

Care din urmatoarele afirmatii NU este adevarata:

Un graf neorientat G contine un arbore partial daca si numai daca G este:

Un arbore directionat este:

. Care din urmatoarele afirmatii legate de metoda Backtracking sunt adevarate:

1. este o metoda lenta

2. este o metoda costisitoare

3. este o metoda de complexitate mare

4. este o metoda rapida

5. solutia se construieste element cu element

6. verificarea conditiei de continuare nu garanteaza obtinerea unei solutii rezultat

Algoritmul Dijkstra:

Care din următoarele afirmații corespund metodei Greedy: 1. Problema poate fi imaginată ca o mulțime A cu n elemente; 2. Pot exista mai multe submultimi diferite acceptabile(soluții posibile), dintre care una este considerată soluție optima pe baza unui criteriu care trebuie maximizat(minimizat) 3. O solutie posibila este o submultime B care îndeplinește o condiție data B este acceptabila 4. Se repeta selectarea unui element din Mulțimea A de maxim n ori 5. Problema se descompune în probleme de complexitate mai mică sau probleme cu rezolvare imediata 6. Poate exista o singura submultime acceptabila, care este considerată soluție optima pe baza unui criteriu care trebuie maximizat

. Care din urmatoarele afirmatii NU corespunde metodei Greedy (metoda optimului local):

Un graf G este arbore daca G este:

Prin recursivitate indirecta se intelege:

Care din urmatoarele afirmatii legate de sortarea crescatoare prin interclasarea unei secvente de numere reale este adevarata:

Determinarea arborelui partial de cost minim se poate face folosind:

1. algoritmul lui Prim 2. algoritmul lui Kruskal 3. algoritmul Roy – Warshall 4. algoritmul Roy – Floyd

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

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

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; }

Ce va returna apelul calc (3)?

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

Fie functia:

int s(int n)

{ int rez; if (n == 0) rez = 0; else rez = n + s(n – 1); return rez; }

In cazul apelului s(3), functia va returna valorea:

Intr-un graf neorientat G, notam cu n nr de varfuri si cu m nr de muchii. Daca graful este un arbore atunci intre n si m exista urmatoarea relatie matematica:

2. Un algoritm de tip backtracking genereaza, in ordine, toate permutarile unei multimi cu 5 elemente. Primele 4 solutii generate sunt: 1 2 3 4 5, 1 2 3 5 4, 1 2 4 3 5, 1 2 4 5 3. Care este a 5-a solutie generata din acest algoritm?

Fie următorul graf reprezentat sub forma tabelara. Care este numărul muchiilor critice din cadrul sau?

1 7

1 8

2 5

2 7

3 4

3 6

4 6

5 6

6 7

Fie graful G, cu V={(1,2)(1,4)(1,5)(2,3)(2.6)(2,7)(3,5)(4,5)(6,7)} si v0=7. Ordinea în care sun vizitate vârfurile corespunzătoare parcurgerii în lățime BF este:

Fie utilizarea metodei Backtracking pentru generarea tuturor numerelor palindrom formate din 4 cifre din Mulțimea {1,2,3}. Numărul soluțiilor:

Fie următorul arbore cu rădăcina R=3, numărul de vârfuri 8 și cu Mulțimea de muchii E={(1,3)(1,7)(2,5) (3,5)(3,8)(4,5)(4,6)}. Care este parcurgerea pe niveluri?

Fie un graf complet cu 10 varfuri. Care este numărul de muchii?

Fie graful G, cu V={(1,2)(1,4)(1,6)(1,7)(2.6)(3,5)(5,6)} si v0=5. Ordinea în care sun vizitate vârfurile corespunzătoare parcurgerii în adancime DF este:

Fie graful G, E={(1,7,1)(1,2,2)(2,5,2)(2,3,3)(2,6,3)(3,4,1)(3,5,2)(4,5,1)(5,6,3)(6,7,5)}. Prim, costul arborelui plecând din vârful 2?

Fie următorul arbore cu rădăcina R=3, numărul de vârfuri 8 și cu Mulțimea de muchii E={(1,3)(1,7)(2,5) (3,5)(3,8)(4,5)(4,6)}. Care este parcurgerea A-postordine pentru acest arbore?

Fie următorul arbore cu rădăcina R=3, numărul de vârfuri 8 și cu Mulțimea de muchii E={(1,3)(1,7)(2,5) (3,5)(3,8)(4,5)(4,6)}. Care este parcurgerea A-preordine pentru acest arbore?

. Ce reprezinta un graf partial al unui graf neorientat?

Intr-un graf, prin circuit elementar se intelege: Un drum in care fiecare nod apare o singura data , cu exceptia celui final,care coincide cu cel initial

Spatiul solutiilor unei probleme:

Algoritmi care utilizeaza divide & impera: quick sort, metoda bisectiei pt ecuatii, cautarea binara intr-o multime sortata

Un subgraf al unui graf neorientat este: un graf din care se elimina noduri si muchii adiacente