Variante bac S II V 11-20

Problema 1
Pentru arborele cu rădăcină având următorul vector de “de taţi” tata=(2,0,2,3,2,3,4,4,3), care este rădăcina arborelui şi care sunt descendenţii
direcţi (fiii) ai nodului 3?

Raspuns : Radacina arborelui este 2, deoarece in vectorul de tati nodul 2 are valoarea 0. Descendentii directi(fiii) nodul 3 sunt nodurile 4, 6 si 9, deoarece in vectorul de tati acestia au valoarea 3, valoarea nodului.

Problema 2
Care este vectorul "de taţi" pentru arborele cu rădăcină din figura alăturată?
a. 0 0 5 7 6 5 1
b. 1 0 0 7 6 5 0
c. 7 4 5 0 4 5 4
d. 7 4 5 0 4 5 7

Raspuns: c. 7 4 5 0 4 5 4 deoarece nodul 4 este radacina, nodurile 5, 7 si 2 sunt descendenti directi ai nodului 4. Varianta d nu poate fi datorita faptului ca in vectorul tata apare ca nodul 7 are doi descendenti, respectiv nodul 1 si nodul 7.

Problema 3
Care sunt etichetele nodurilor de tip frunză ale arborelui cu rădăcină, având 7 noduri,
numerotate de la 1 la 7, şi următorul vector “de taţi”: (5,1,5,1,0,7,5)?

Raspuns : Nodurile de tip frunza ale arborelui sunt 2, 3, 4 si 6, deoarece aceste noduri nu se gasesc in vectorul tata, ele nemaiavand descendenti.

Problema 4
Câţi fraţi are nodul 1 din arborele cu rădăcină cu 7 noduri, numerotate de la 1 la 7,având următorul vector ”de taţi”: (5,1,5,1,0,7,5)?

Raspuns : Nodul 1 din arbore are 2 frati si anume nodul 3 si nodul 7, deoarece aceste noduri au acelasi tata ca si nodul 1, respectiv nodul 5.

Problema 5
Un arbore binar este un arbore cu rădăcină în care fiecare nod are cel mult 2 descendenţi direcţi (fii). Înălţimea unui arbore este reprezentată de numărul maxim de muchii ale unui lanţ elementar ce uneşte rădăcina cu un vârf terminal (frunză).
Pentru un arbore binar cu exact 8 noduri, care este înălţimea minimă posibilă şi care este numărul de noduri terminale (frunze) în acest caz?

Raspuns : Inaltimea minima posibila este 4, iar in acest caz, avem un singur nod terminal.

Problema 6
Se considera graful neorientat cu 80 d enoduri si 3160 muchii. Care este numarul de muchii care pot fi eliminate astfel incat graful partial obtinut sa devina arbore ?

Raspuns : Un arbore cu n noduri are n-1 muchii. Pentru ca graful dat sa devina arbore, trebuie sa se elimine 3160-79=3081 muchii.

Problema 7
Care este gradul maxim posibil si care este gradul minim posibil pentru un nod dintr-un graf cu n noduri, care este arbore ?

a. n-1 si 1
b. n si 1
c. n si 0
d. n-1 si 0.

Raspuns: a. Un arbore este conex, deci nu are varfuri izolate, oar gradul maxim al unui varf este n-1, daca in graf sunt n varfuri.

Problema 8
Un arbore cu rădăcină având 8 noduri, numerotate de la 1 la 8, este memorat cu ajutorul vectorului de ”taţi” t=(8,8,0,3,4,3,4,6). Scrieţi care este numărul total de descendenţi ai nodului 4?

Raspuns : 2 descendenti deoarece din vectorul de tati se observa ca nodul 5 si 7 il au ca tata pe 4.

Problema 9
Care dintre următoarele afirmaţii este adevărată pentru graful neorientat având mulţimea nodurilor X={1,2,3,4,5} şi mulţimea muchiilor U={[1,2], [1,5], [2,3], [2,4],[3,4], [4,5]}? (4p.)

a. Este graf hamiltonian, dar nu este eulerian.
b. Este graf eulerian, dar nu este hamiltonian.
c. Este şi graf hamiltonian şi graf eulerian.
d. Nu este graf hamiltonian, şi nici nu este graf eulerian.

Raspuns: a) Deoarece graful format reprezinta un cilcu Hamiltonian elemtentar care trece prin fiecare nod al grafului.

Problema 10
Un graf neorientat cu nodurile numerotate de la 1 la 4 este reprezentat prin matricea de adiacenţă alăturată. Care dintre afirmaţiile de mai jos este adevărată pentru acest graf?

a. Graful este arbore
b. Graful nu este conex
c. Graful este ciclic
d. Graful are toate gradele nodurilor numere pare.

Raspuns: a)Graful este un arbore, deoarece nodul 1 este radacina, care are ramificatie de dreapta nodul 2 si de stanga nodul 3, iar nodul 3 are ramificatied de stanga.

Problema 11
Se consideră un arbore cu 9 noduri, numerotate de la 1 la 9, şi cu vectorul “de taţi” următor: (8, 8, 8, 2, 6, 2, 9, 0, 2).
a) Enumeraţi descendenţii nodului 2.
b) Câte noduri de tip frunză are acest arbore?

Raspuns: a) descendentii nodului 2 sunt: 4,6,9,5,7;
b) exista 3 noduri de tip frunza : 4,5,7;