WorksheetsTest Arbori
Total questions: 10
Worksheet time: 2hrs 40mins
Într-un arbore cu 50 de noduri, numerotate de la 1 la 50, rădăcina este nodul 1, iar tatăl oricărui alt nod i al său este nodul numerotat cu [i/2]. Lungimea lanţului cu o extremitate în nodul 14 și cealaltă extremitate în nodul 47 este:
16
5
33
8
Care este vectorul de ”taţi” asociat arborelui cu rădăcină din figura următoare în care nodul 5 este nodul rădăcină?
Scrieți elementele vectorului în ordine, separate prin exact un spațiu.
(a)
Care este vectorul de „taţi” pentru arborele cu 8 noduri, numerotate de la 1 la 8, şi muchiile [1,5], [2,3], [3,6], [3,8], [4,6], [5,7], [6,7], dacă se alege ca rădăcină nodul numerotat cu 6?
5 3 6 6 6 0 7 3
5 3 6 6 7 0 6 3
5 3 6 6 1 0 6 3
7 3 6 6 1 0 6 3
Se consideră arborele cu rădăcină cu 10 noduri, reprezentat prin următorul vector de tați: (10, 6, 7, 6, 0, 9, 1, 5, 8, 5).
Să se precizeze rădăcina arborelui și lungimea maximă a unui lanț elementar în arbore.
Scrieți cele două valori în ordinea precizată, separate prin exact un spațiu.
(a)
Considerăm că înălțimea unui arbore cu rădăcină este egală cu cea mai mare dintre lungimile lanțurilor elementare care au o extremitate în rădăcină și cealaltă extremitate în oricare dintre “frunzele” arborelui.
Se consideră arborele cu 9 noduri, numerotate de la 1 la 9, și muchiile [1,2], [2,3], [2,5], [3,7], [4,5], [5,6], [5,8], [8,9]. Scrieți nodurile care pot fi alese drept rădăcină, astfel încât înălțimea arborelui să fie maximă.
Scrieți cele 2 noduri în ordine crescătoare, separate prin exact un spațiu!
(a)
Un arbore cu 4 noduri, numerotate de la 1 la 4, NU poate fi reprezentat prin vectorul de „taţi”:
4 4 4 0
0 1 2 3
2 3 4 0
2 1 0 3
Se consideră arborele cu 8 noduri, numerotate de la 1 la 8, reprezentat prin vectorul de „taţi”: (3, 0, 2, 5, 2, 5, 2, 5). Care sunt nodurile arborelui care au acelaşi „tată” cu nodul 4?
2 7
3 5 7
6 8
6 7
Determinaţi ultima valoare (notată cu ?) din vectorului „de taţi” (0, 1, 1, 2, 3, 3, ?) astfel încât arborele cu rădăcină, cu 7 noduri, numerotate de la 1 la 7, descris de acest vector, să aibă pe fiecare nivel n exact 2n noduri, nodul rădăcină fiind pe nivelul n=0, şi fiecare nod să aibă cel mult doi descendenţi.
4
2
5
3
Care este vectorul de ”taţi” corespunzător arborelui cu rădăcină, cu 8 noduri, numerotate de la 1 la 8, dat prin lista următoare a descendenţilor direcţi (fiilor)?
1: 4,6,7
2: -
3: 1,8
4: -
5: -
6: 2
7: -
8: 5
Scrieți elementele vectorului în ordine, separate prin exact un spațiu.
(a)
Scrieți "Gata" fără ghilimele pentru punctul din oficiu!
(a)
