Arbori

Acest forum este dedicat intrebarilor de programare care nu-si au locul in unul din celelalte forumuri

Arbori

Mesajde Skyp89 » 07 Mai 2016, 12:03

Care sunt nodurile care au exact 2 descendenţi pentru un arbore cu rădăcină, cu 7 noduri, numerotate de la 1 la 7, dat de vectorul de ”taţi”: (3,3,0,1,2,2,4)? (Intrebare din varianta 23 de BAC2008 informatica intensiv)

Am indoieli in privinta raspunsului corect. Eu cred ca doar nodul 2 este solutie. In variante rezolvate gasesc ca solutia ar fi: nodul 2 si nodul 3, insa de ce ar specifica ca vor nodurile care au EXACT 2 descendenti ? Mie mi se pare ca vor nodurile care au doar 2 descendenti in total (adica adunand toti fii, nepotii sa dea 2) ... atunci raspunsul ar fi nodul 2, pentru ca nodul 3 are 6 descendenti dintre care doar 2 DIRECTI. Insa ... daca ar fi dorit nodurile care au 2 descendenti directi, ar fi trebuit sa specifice explicit "descendenti directi" pentru ca e diferenta mare intre 2 descendenti si 2 descendenti directi. Am mai gasit si definitia urmatoare care ma pune mai mult pe ganduri:

Descendent = într-un arbore cu rădăcină nodul y este descendentul nodului x dacă este situat pe un nivel mai mare decât nivelul lui x şi există un lanţ care le uneşte şi nu trece prin rădăcină.

In cazul in care 3 este radacina, si se formeaza lant intre 3 si 1,2,4,5,6,7 ... sunt acestea descendentii lui 3 sau nu ? la ce se refera "si nu trece prin radacina" ? sa nu o atinga ? sau sa nu treaca prin ea spre cealalta parte a arborelui (cazul in care poate am zice ca 7 e descendentul lui 2 ... dar lantul dintre 7 si 2 trece prin 3)? Daca lantul care "certifica" faptul ca un nod e descendentul altui nod nu are voie sa atinga radacina, adica radacina nu poate avea descendenti, atunci 3 are 0 descendenti si din nou ramane doar nodul 2 ca solutie. Deci in opinia mea doar nodul 2 e solutie. Fie pentru ca 3 are 6 descendenti, si nu 2, fie pentru ca 3 are 0 descendenti (in cazul in care nu are voie lantul dintre ascendent si descendent sa aiba ca sfarsit de lant radacina), dar tind sa cred ca nodul 3 are descendenti ... 2 directi, 6 in total. Merci pentru rabdarea de a citi nelamurirea! Acu sa vedem cine are rabdare sa explice :)
Skyp89
Junior
Junior
 
Mesaje: 12
Membru din: 25 Ian 2016, 11:55
Judet: Suceava

Înapoi la Programare generala

Cine este conectat

Utilizatorii ce navighează pe acest forum: Niciun utilizator înregistrat şi 2 vizitatori

cron