Atp
Test Your Algorithm Knowledge
Are you ready to challenge your understanding of algorithms and data structures? This quiz covers various concepts including recursion, graph theory, and sorting methods.
Engage with questions that will:
- Test your knowledge of key algorithmic principles.
- Help you understand complex topics better.
- Provide essential insights for programming enthusiasts.
Care din urmatoarele afirmatii referitoare la metoda Divide Et Impera NU este adevarata:
Implementarea este realizata de obicei prin subprograme recursive
descompune problema in probleme de complexitate mai mica de acelasi tip cu problema initiala sau in probleme cu rezolvare imediata (primitive)
Combina (asambleaza) solutiile problemelor obtinute in urma descompunerii pentru a obtine solutia problemei initiale
Descompune problema in probleme de complexitate mai mica pentru care se apeleaza alte metode de descompunere diferite de metoda de descompunere initiala
Sunt definite subprobleme primitive(conditii terminale) a caror solutie este “cunoscuta” sau data.
Care din urmatoarele afirmatii referitoare la arborele orientat sunt adevarate?
1. Graful suport este conex
2. Graful suport este aciclic
3. Este graf asimetric
4. Este graf simetric
5. Este arbore directionat cu radacina 6. Este arbore directionat fara radacina
Toate
1, 2, 3, 5
1, 2, 3, 6
1, 2, 4, 5
6
atribuie si avanseaza
Incercare esuata
Revenire dupa construirea unei soluti
Revenire
Nu exista o astfel de operatie
Reteaua strazilor auto din Bucuresti se reprezinta corect cu ajutorul structurii de date:
graf neorientat
Arbore
lista liniara
Graf orientat
Lista dublu inlantuita
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
Toate
2, 3, 4, 5
1, 2, 3
2, 3, 4
1, 2, 3, 4
Fie subprogramul void Test (int I, int n) { printf (“ * “); if (i < n) Test (i + 1, n); printf (“ + “); } Ce va afisa apelul Test (1, 5) ?
*+++++
*****+
******
+++++
*****+++++
.Fie graful G = (V, E) cu V = {1, 2, 3, 4, 5, 6}, E = {(1,2), (1,4), (2,4), (4,5),(5,6)} si v0 = 2. Ordinea in care sunt vizitate varfurile corespunzator parcurgerii in latime BF este:
2, 1, 3, 4, 5, 6
2, 3, 1, 5, 6, 4
1, 2, 4, 5, 6
1, 2, 4, 5, 6
2, 1, 4, 5, 6
Care din urmatoarele afirmatii NU este valabila pentru algoritmul lui Kruskal
Determina arborele de cost minim
dintre arcele disponibile (care nu au fost analiza inca) se alege arcul cu ponderea cea mai mica si care nu formeaza un ciclu prin adaugarea la arbore
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
Multimea muchiilor selectate E0 se initializeaza la inceput cu multimea vida
Determina n – 1 muchii, unde n este numarul de varfuri
Metoda Greedy este
O metoda rapida, de complexitate redusa, care genereaza intotdeauna solutia optima a problemei tinand cont de contextul general
O metoda lenta, de complexitate mare, care genereaza toate solutiile posibile
O metoda rapida, de complexitate mare, care genereaza solutia optima a problemei
Este o metoda rapida, de complexitate redusa, pentru obtinerea unei solutii acceptabile nu neaparat cea mai buna
Este o metoda costisitoare, care la fiecare pas alege cea mai buna cale tinand cont de contextul general
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
1, 2, 3, 4
1, 2, 3
3
1,1
Nici una
Secventa: 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; }
realizeaza:
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; }
realizeaza:
Sortarea elementelor unui vector prin metoda Quicksor
Sortarea elementelor unui vector prin interclasare
Sortarea elementelor unui vector prin metoda Shell
sortarea elementelor unui vector prin interschimbare
Compactarea elementelor unui vector
Daca G este un graf neorientat, conex si aciclic, atunci graful:
este complet
Este arbore
este asimetric
Poate avea varfuri izolate
este digraf
Care din urmatoarele afirmatii legate de subprogramele recursive NU este adevarata:
Repetarea este asigurata prin autoapel
trebuie sa existe o conditie de oprire (sau de continuare) a generarii de noi apeluri
pot fi utilizate in rezolvarea unor probleme care utilizeaza metoda backtracking
Pot fi folosite numai pentru implementarea unor algoritmi recursivi
necesita consumul suplimentar de resurse
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?
1 3 2 4 5
1 3 2 5 4
1 3 4 2 5
1 2 5 3 4
1 2 5 4 3
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:
m = n + 2;
N = m – 1
N = m + 1;
N = m + 2
n = m
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
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
1, 2 si 3
...
4,5
2,5
1,5
In configuratia urmatoare (specifica metodei backtracking) este prezentata operatia de:
Atribuie si avanseaza
incercare esuata
Revenire dupa construirea unei solutii
Revenirea unui pas anterior, dupa consumarea tuturor valorilor posibile pentru pasul curent
Nu exista … de operatie
Fie functia:
int f (int n)
{ int rez; if (n == 0) rez = 0; else if (n % 2) rez = n + f (n – 1);
else rez =n / … 1); return rez; }
{ int rez; if (n == 0) rez = 0; else if (n % 2) rez = n + f (n – 1);
else rez =n / … 1); return rez; }
Ce va returna apelul f(4)?
10
7
9
17
5
Fie multimea de litere [a, b, c, d]. Se genereaza permutarile acestei multimi. Precizati care sunt solutiile anterioara si urmatoare solutiei cabd:
Bdac si cbad
Bdca si cadb
Bdca si cdba
Bcda si cdba
Bcda si cadb
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:
1
6
10
7
11
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
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
1,2,3,4,5
1,3,4,5
2,3,4,5
1,2,3,4
3,4
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:
1,2,4,5,7
2,3,6
2,1,7,5
2,4,1,7,5,3,6
2,4,1,7,5
Care din urmatoarele afirmatii NU este adevarata:
Un algoritm iterativ sau recursiv poate fi implementat printr-un subprogram iterativ sau recursiv
Un subprogram recursiv genereaza (cel putin) un apel catre el insusi
La recursivitatea directa, apelul recursiv se realizeaza prin intermediul mai multor functii care se apeleaza circular
Recursivitatea directa poate fi simpla sau multipla
Fiecare apel recursiv trebuie aplicat unei probleme mai simple decat in pasul urmator
Un graf neorientat G contine un arbore partial daca si numai daca G este:
Aciclic
Digraf
Eulerian
Hamiltonian
Conex
Un arbore directionat este:
Un graf orientat asimetric cu graful suport corespunzator lui de tip arbore
Un graf orientat simetric si graful suport corespunzator lui de tip arbore
Un graf neorientat si graful suport corespunzator lui de tip arbore
Un graf conex neorientat si graful suport corespunzator lui de tip arbore
niciuna din variantele de mai sus
In configuratia urmatoare (specifica metodei backtracking) este prezentata operatia de:
Atribuie si avanseaza
Incercare esuata
Revenire dupa construirea unei solutii
Revenire
Nu exista o astfel de operatie
Care din urmatoarele afirmatii referitoare la implementarea recursiva este adevarata:
Timp de executie mic
Usurinta in proiectare/programare (lungimea mica a codului sursa)
Scaderea numarului de operatii
Se poate aplica numai pentru rezolvarea unor probleme complexe, care nu pot fi rezolvate prin implementare iterativa
consum mic de resurse de memorie
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 garanteaza obtinerea unei solutii
rezultat
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 garanteaza obtinerea unei solutii
rezultat
1, 2, 3, 5, 7
2, 3, 4, 5, 6
1, 2, 3, 5, 6
1, 2, 3, 7
4, 7
Algoritmul Dijkstra:
Calculeaza distanta si drumul minim intre 2 noduri date ale unui graf
Determina distantele intre oricare 2 noduri ale unui graf
Determina distantele intre oricare 2 noduri ale unui graf
Determina toate drumurile posibile intre 2 noduri date
Calculeaza distantele si drumurile minime de la un nod al unui graf la toate celelalte noduri din graf
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; }
{ 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)?
17
15
9
7
21
Care din urmatoarele afirmatii NU corespunde metodei Greedy (metoda optimului local):
Problema poate fi imaginata ca o multime A cu n elemente
Pot exista mai multe submultimi diferite acceptabile (solutii posibile), dintre care una este considerata solutie optima pe baza unui criteriu care trebuie maximizat (minimizat)
O solutie posibila este o submultime (B) care indeplineste o conditie data (B este acceptabila)
Se repeta selectarea unui element din multimea A de maxim n ori (nr de elemente corespunzator multimii A)
Problema se descompune in probleme de complexitate mai mica sau probleme cu rezolvare imediata
Un graf G este arbore daca G este:
Conex
Aciclic si neconex
Aciclic si conex
Ciclic si neconex
Conex si ciclic
Prin recursivitate indirecta se intelege:
Un subprogram A apeleaza subprogramul A
Un subprogram A apeleaza un alt subprogram B, iar subprogramul B apeleaza subprogramul C
Un subprogram A apeleaza un alt subprogram B, iar subprogramul B apeleaza subprogramul A
Un subprogram A apeleaza un alt subprogram B, iar subprogramul B nu apeleaza subprogramul A
Niciuna din variantele de mai sus
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:
4, 2, 1, 7, 5, 8
3, 6, 9
4, 2, 1, 5, 7, 8
4, 1, 2, 7, 8, 5, 3, 6, 9
4, 1, 2, 7, 8, 5
Care din urmatoarele afirmatii legate de sortarea crescatoare prin interclasarea unei secvente de numere reale este adevarata:
Pozitioneaza un element astfel incat toate elemente care ajung in fata lui sa fie mai mici decat el si toate cele care ii urmeaza sa fie mai mari decat el
Insereaza un element intr-un vector ordonat pe pozitia corecta
Este denumita si sortarea prin interschimbare
Determina minimul din vector si il insereaza pe pozitia corecta
Utilizeaza metoda Divide Et Impera
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
2. Algoritmul lui Kruskal
3. algoritmul Roy – Warshall
4. algoritmul Roy – Floyd
2
2,3,4
1,2
3,4
1,2,3,4
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?
2143
2134
1423
1342
1432
Parcurgerea generalizata a unui graf se face:
.doar daca graful este conex
In latime
Pe diagonala
In adancime sau in inaltime
In adancime
Care dintre urmatorii algorimi se poate folosi pt determinarea celor mai scurte
drumuri dintr-un graf neponderat,de la un varf initial cat catre fiecare celalalte varfuri:
1.Dijkstra
2.parcurgerea in latime
3.parcurgerea in adancime
4.Roy-warshall
5.algoritmul ponderii minime
drumuri dintr-un graf neponderat,de la un varf initial cat catre fiecare celalalte varfuri:
1.Dijkstra
2.parcurgerea in latime
3.parcurgerea in adancime
4.Roy-warshall
5.algoritmul ponderii minime
6.Roy-Floyd
1,2
2,3
4,5,6
1,3,5
5,6,7
Drumurile minime de la un nos al unui graf la toate toate celelalte noduri din graf
Arborele partial de cost minim(algoritmul lui Kruskal)
Arborele partial de cost minim ( alg. Prim)
Toate componentele conexe ale unui graf
Costurile drumurile de la varful initial v0 la toate celelalte noduri din graf
Ce reprezinta un subgraf al unui graf neorientat?
Un graf cu cel putin un varf izolat
Un graf cu cel putin un varf izolat
Un graf care contine un ciclu partial
Un graf din care se elimina anumite muchii
Un graf cu n noduri si n muchii
Fie graful G=(V,E),V={1,2,3,4,5,6,7,8,9,10} si E={(1,2),(1,6),(1,4),(2,6),(2,5),(3,8),(3,10),(4,5),(4,6), (4,7),(5,7),(7,8),(7,9),(8,9),(9,10)}.Considerand v0=3,care din urm este ordinea de vizitare in latime:
3,8,10,7,9,4,5,1,2,6
Toate variantele
3,8,10,9,7,4,5,2,1,6
3,10,8,9,7,4,5,6,2,1
3,10,8,9,7,5,4,2,6,1
Dintre metodele de sortare studiate,cea mai buna complexitate medie este:
Niciun rasp corect
O(n2 )
O(n)
O(nxlog(n))
O(n+k)
Pentru un algoritm recursiv formula recursiva:
Arata cand se termina algoritmul
Nu exista notiunea de “formula de start”
Sugereaza conditia de oprire a generarii de noi autoapelur
Se aplica pentru descompunerea problemei
Este polinomiala de grad n
Metoda optimului local determina:
Intotdeauna o saloutie optima
Niciuna din afirmatiile anterioare nu este corecta
Intotdeauna o solutie acceptabila
Solutie optime/acceptabila/cea mai nefavorabila ,in functie de prob
Intotdeauna cea mai nefavirabila solutie
Algoritmul lui Dijsktra este de tip Greedy pt ca
Nu stiu,asa ni s a spus la curs
Nu este de tip greedy
.seamana cu algoritmul general Greedy
.problema prezinta toate caracteristice prob rezolvate prin metoda greedy
Problema prezinta toate caracteristicile prob rezolvate prin metoda greedy,algoritmul se incadreaza in algoritmul greedy si contine operatiile generale ale metodei greedy
Care dintre urmatoarele nu sunt elemente caracteristice prob care se rezolva divide et timpera:
Solutia se reprezinta ca un vector cu n componente
In urma descompunerii se pot obtine probleme triviale
Problema se poate descompune in probleme de acelasi tip cu complexitate mai mica
Solutia problemei se obtine prin combinarea solutiilor problemelor obtinute prin descompunere
Descompunerea e de doua tipuri: descompunere propriu-zisa si reducere
Care din urmatoarele sunt operatiile generale ale metodei optimului local (Greedy):
1. Alegerea unui element candidat din multimea primita
2. Sortarea multimii primite
3. Verificarea acceptabilitatii elementului ales
4. Compararea elementului ales cu cel ales anterior
5. Adaugarea elementului acceptat la solutie
6. Compararea solutiei construite cu solutia construita anterior pt pastrarea celei mai bune?
1. Alegerea unui element candidat din multimea primita
2. Sortarea multimii primite
3. Verificarea acceptabilitatii elementului ales
4. Compararea elementului ales cu cel ales anterior
5. Adaugarea elementului acceptat la solutie
6. Compararea solutiei construite cu solutia construita anterior pt pastrarea celei mai bune?
2,4,5,6
1,3,5,6
1,3,5
1,2,3,5
1,5,6
Fie următoarea situație: un subprogram X apelează un alt subprogram Y, care apelează subprogramul X. Ce tip de recursivitate este aceasta:
Multipla
Nicio varianta
Directa
Simpla
Mutuala
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
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
1,2
1,2,4,5
1,2,4
1,2,3,4,5
1,2,3
Daca în cadrul unui arbore se elimina o muchie atunci se obține:
Un Graf neconex
Cel Putin un nod izolat
Cel Putin un ciclu
Tot un arbore
Cel pitin un circuit
Care dintre următoarele afirmații NU este adevarata în ceea ce privește metoda Backtracking?
Este posibila combinarea metodei cu alte metode pentru a reduce complexitatea acesteia
Orice element din spațiul soluțiilor constituie o soluție acceptabila
Mai multe elemente din spațiul soluțiilor este posibil sa constituie soluții acceptabile
Metoda este una costisitoare, implicând un consum mare de resurse
Metoda este utilizată când nu mai exista alta posibilitate de rezolvare a problemei
In ceea ce privește metoda Divide et Impera, care dintre următoarele afirmații NU este adevarata:
Problemle comple sunt descompuse în probleme cu complexitate mai mică
Pentru aceasta metoda, în general sunt definite subprobleme primitive a căror soluție nu este cunoscuta
Descompunerea se face pana când se ajunge la probleme cu soluție imediata
Modul de descompunere al problemei se face în funcție de problema rezolvată
Prin combinarea soluțiilor rezultate în urma descompunerii se obține o soluție pentru problema inițială
Care dintre urmatoarele afirmații NU este specifica algoritmului Kruskal?
Se da un varf initial de la care se pleacă
Se utilizează un Graf ponderat
Algoritmul se oprește după ce au fost adăugate n-1 muchii
Aplicand algoritmul se obține un arbore parțial de cost minim
La fiecare pas se încearcă adăugarea unei muchii de cost minim dintre muchiile neanalizate
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
2 si 4
1 si 3
1 sau 2 și 3 sau 4
1 sau 2 și 3
1 si 3 sau 4
Care dintre următoarele operații sunt specifice metodei Greedy: 1. Adăugare, 2. Initializare, 3. Eliminare, 4. Verificare, 5. Alegerea, 6. Combinarea
2,6,3,1
2,4,5,6
5,4,1
2,5,6
1,4,3,6
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
2,4
1,2,3
2,4,5
2,3,4
1,2,4
Ce metoda de sortare mentionata mai jos permite compararea și rearanjarea elementelor aflate la distante mai mari în vector:
Sortarea rapida
Sortarea prin numărare
Sortarea Heap
Sortarea prin interclasare
Sortarea Shell
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
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
Care dintre acestea sunt echivalente?
1,2,3
1,3,5
1,2,3,5
1,2,4,6
1,4,5
Într-un graf, drumul hameltonian reprezintă:
Un drum elementar care trece prin toate nodurile gradului
Un drum simplu care conține toate arcele gradului
Un drum in care fiecare nod apare o singura data
Un drum in care fiecare arc apare o singura data
Un drum care conține toate arcele grafului
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;
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
1,2,3,4,5
1,3,4,5
2,3,4,5
1,2,3,4
3,4
Elementele matricei de adiacentă a unui graf neorientat cu n vârfuri:
Au valorile -1,0
Sunt simetrice fata de diagonala secundara
Sunt simetrice fata de diagonala principala
Au ca valoare 0,1,-1
Au suma valorilor 2*n+1
Care din următoarele afirmații legate de subprogramele recursive NU este adevarata:
Nu pot fi scrise pentru implementarea unor algoritmi iterativi
Pot fi folosite la implementarea algoritmelor de parcurge a arborilor
Pot fi folosite în rezolvarea problemelor care utilizează metoda Divide et impera
Pot fi bazate pe o metoda de tip reducere
Pot fi bazate pe o metoda de tip descompunere
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:
5,3,6,1,2,7,4
5,3,6,1,2,7,4
5,3,4,2,1,6,7
5,3,4,1,2,6,7
5,3,4,1,2,7,6
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?
14
12
9
8
10
Ce reprezinta un graf partial al unui graf neorientat?
Un graf cu n noduri si n muchii
Un graf din care se elimina anumite muchii
Un graf care contine un ciclu partial
Un graf din care se elimina noduri si muchii adiacente
Un graf cu cel putin un varf izolat
Calculeaza
Prima aparitie a unei valori date (val) intr-un vector
Ultima aparitie a unei valori date (val) intr-un vector
Prima si ultima aparitie a unei valori date (val) intr-un vector
Nr. De aparitii ale unei valori date (val) intr-un vector
Prima valoare diferita de valoarea data (val)
Care dintre urmatoarele afirmatii referitoare la arborele orientat sunt adevarate?
1.graful suport este conex
2.graful suport este aciclic
3.este graf asimetric
4.este graf simetric
5.este arbore directionat cu radacina
6.este arbore directionat fara radacina
2.graful suport este aciclic
3.este graf asimetric
4.este graf simetric
5.este arbore directionat cu radacina
6.este arbore directionat fara radacina
Toate
1,2,3,5
1,2,3,6
1,2,4,5
6
Ce metoda de sortare mentionata mai jos foloseste construirea unui arbore binar?
Soartarea rapida
Sortare prin interclasare
Sortare prin numarare
Sortarea heap
Sortarea shell
fie G=(V,E) un graf arbore. Care dintre urmatoarele afirmatii sunt echivalente cu aceasta afirmatie?
1.G e graf aciclic maximal
2.G e graf conex maximal
3.G e graf aciclic minimal
4.G e graf conex minimal
1, 4
1,2,4
Niciuna
1,3
1,3,4
Fie urmatorul arbore cu radacina R=4 , 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 e parcurgerea A-postordine pt acest arbore?
Nicio varianta
2,7,1,8,3,5,6,4
2,6,7,4,5,8,1,4
2,5,3,4,6,8,1,4
4,5,6,2,3,1,8,7
Fie urmatorul arbore cu radacina R=4 , nr de varfuri 8 si cu multimea de muchii E={91,3),(1,7),(2,5),(3,5),(3,8),(4,5),(4,6)}.Crae e parcurgerea pe niveluri pt acest arbore?
4,5,2,3,1,7,8,6
4,5,6,2,3,1,8,7
4,5,6,3,2,1,8,7
4,5,7,1,3,8,6,2
4,2,7,1,8,3,5,6
Utilizand metoda Backtracking pt a genera toate permutarile de 4 obiecte, dupa identificarea solutiei 3124( considerata solutia nr 1), care va fi solutia nr 4?
3241
4231
3142
3214
4321
Fie utilizarea metode de backtracking pt generarea tuturor sirurilor palindrom formate din 3 litere din multimea {a,b,c}. Exemplu de solutie: aba. Nr solutiilor identificate este:
14
6
9
3
12
Fie un graf conex ponderat reprezentat sub forma tabelata T. Considerand v0=3, alg. lui Dijkstra determina urmatoarele rezultate pe distantele D(v0,v) si predecesorul lui v(P).
Rezultatul este de forma: V3-Vi: distanta, predecesor
T=
(
1,2,7
1,3,6
1,4,3
1,5,2
1,6,10
2,5,1
3,4,2
4,6,2
)
V3-V1:5,4; V3-V2:8,5; V3-V4: 2,3; V3-V5:7,1; V3-V6:4,4
V3-V1:5,4; V3-V2:5,4; V3-V4: 3,4; V3-V5:2,5; V3-V6:5,4
V3-V1:5,4; V3-V2:2,4; V3-V4: 4,3; V3-V5:5,1; V3-V6:1,4
NICI UNA
V3-V1:5,4; V3-V2:8,5; V3-V4: 2,5; V3-V5:3,4; V3-V6:5,4
Un algoritm recursiv care utilizeaza date din una din repetarile anterioare este un algoritm
Unirecursiv
Recursiv indirect
Niciun raspuns
Multirecursiv
Pseudorecursiv
Un subprogram X apeleaza un alt subprg Y, care apeleaza suprg X. Ce tip de recursivitate e?
Simpla
Nicio varianta
Directa
Multipla
Mutuala
{"name":"Atp", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"Are you ready to challenge your understanding of algorithms and data structures? This quiz covers various concepts including recursion, graph theory, and sorting methods.Engage with questions that will: Test your knowledge of key algorithmic principles.Help you understand complex topics better.Provide essential insights for programming enthusiasts.","img":"https:/images/course4.png"}