Arbori1

Se consideră un arbore. Care dintre următoarele afirmații este adevărată?

• are cel puțin un nod izolat

• toate nodurile au grad par

• are cel puțin două componente conexe

• este aciclic

Numărul de noduri care au gradul 1 într-un graf neorientat conex

şi aciclic cu n noduri (n>1) este:

• mai mare sau cel puțin egal cu 2

• exact n-1

• exact 1

• 0 sau 1

Care dintre următorii vectori ”de taţi” corespunde reprezentării

unui arbore în care nodurile numerotate cu 6, 4 şi 9 sunt descendenţi direcţi

ai nodului 3?

• tata=(3,3,4,0,2,3,4,4,4)

• tata=(9,9,4,9,9,9,9,9,0)

• tata=(3,3,1,3,2,3,4,4,3)

• tata=(3,0,2,3,2,3,4,4,3)

Se consideră vectorul de taţi al unui arbore

oarecare t=(0,3,1,3,1,5), în care nodurile sunt numerotate de la 1 la 6.

• nodurile 2, 4, 6 sunt fraţi

• nodul 5 are gradul 1

• nodul 3 este tatăl nodului 1

• nodurile 2, 4 şi 6 sunt frunze

Pentru reprezentarea unui arbore cu rădăcină cu 9 noduri,

etichetate cu numere de la 1 la 9, se utilizează vectorul de taţi TATA =(4,

1, 1, 0, 1, 3, 3, 7, 4). Care sunt frunzele arborelui?

• 2,5,6,8,9

• 1,4,6,8,9

• 2,3,4,5,6

• 2,6,7,8,9

Pentru arborele cu rădăcină din

figura alăturată vectorul de “taţi” este:

• 0 5 7 4 0 0 3

• 0 5 7 0 4 3 3

• 2 0 2 5 5 3 3

• 2 0 2 5 2 3 3

Fie un arbore precizat prin vectorul de taţi

T=(0,1,2,5,2,8,8,2). Care este numărul maxim de descendeţi direcţi ai

unui nod din arbore?

• 3

• 0

• 2

• 1

Un arbore cu 9 noduri, numerotate de la 1 la 9, este memorat cu

ajutorul vectorului de taţi t=(2,5,5,3,0,2,4,6,6). Ascendenţii nodului 6

sunt:

• 1 şi 4

• 2

• 8 şi 9

• 2 şi 5

Câte lanţuri

elementare de lungime

maximă ce leagă două noduri terminale

ale arborelui din figura

alăturată există?

• 8

• 6

• 10

• 4