Arbori și vectorul de tați (doar matematică-informatică)

Pe scurt

2 minesențialul, de recitit oricând

Culorile din lecție:termencifră, datăidee-cheie

• Doar la matematică-informatică. Punctul 11.3 din programă nu apare la științele naturii.
• Un arbore e un graf neorientat conex și fără cicluri. Când alegi o rădăcină, capătă sus și jos: tați, fii, frați, frunze, niveluri.
• Din 46 de itemi de grafuri și arbori din lucrările MI 2023-2027, 17 sunt pe arbori, iar 10 dintre aceștia dau arborele printr-un vector de tați.
• Lucrările scriu cuvintele în ghilimele: vector de „tați”, descendenți direcți („fii”), noduri „frunză”.

Urmează · 2 min

Ideea, apoi numele oficial

5 min o întrebare la final

Un arbore genealogic: sus un om, sub el copiii lui, sub ei copiii lor. Fiecare are un singur părinte în desen. Asta e tot ce îți trebuie.

Lucrările definesc nivelul explicit: un nod este pe nivelul x dacă lanțul elementar dintre el și rădăcină are lungimea x. Pe nivelul 0 se află doar rădăcina.

Urmează · 5 min

Trei reprezentări

2 min

Programa cere trei.

Matricea de adiacență, ca la orice graf neorientat, are a[i][j]=1 dacă există muchia [i,j].

Listele de descendenți dau, pentru fiecare nod, fiii lui:

1: 2, 3
2: 4, 5
3: 6
4: (niciun fiu)
5: 7
6: (niciun fiu)
7: (niciun fiu)

Vectorul de tați dă, pentru fiecare nod, tatăl lui. Rădăcina are 0.

E cea mai folosită în lucrări, pentru că încape pe un rând.

Urmează · 2 min

Din vector în desen

3 min

1. Găsești rădăcina
   Poziția pe care e 0.
2. Grupezi
   Pentru fiecare valoare x, scrii pozițiile pe care apare x: aceștia sunt fiii lui x.
3. Desenezi
   De la rădăcină în jos.

În C++, aceleași întrebări se rezolvă așa:

int t[101],nf[101],n,i;
cin>>n;
for(i=1;i<=n;i++)
  cin>>t[i];
// radacina
for(i=1;i<=n;i++)
  if(t[i]==0) cout<<i<<" ";
// numarul de fii
for(i=1;i<=n;i++)
  if(t[i]!=0) nf[t[i]]++;
// frunzele
for(i=1;i<=n;i++)
  if(nf[i]==0) cout<<i<<" ";

Nivelul unui nod îl afli urcând spre rădăcină:

int nivel(int x)
{ int k=0;
  while(t[x]!=0)
  { x=t[x];
    k++;
  }
  return k;
}

Pentru vectorul de mai sus, nivel(7) este 3: de la 7 urci la 5, 2, 1.

În Pascal: t:array[1..100] of integer, restul se scrie la fel. Nu am găsit în lucrările 2023-2027 niciun item care să ceară un program pe arbore, dar programa cere reprezentările, deci e bine să știi cum arată.

Urmează · 3 min

Oficial: iulie 2024, varianta 3, II.2

1 min 2 întrebări la final

Arbore cu 8 noduri și vectorul de tați (3,0,2,5,2,5,1,5). Se cer, în ordinea parcurgerii, nodurile celui mai lung lanț elementar cu extremitatea inițială în rădăcină.

Răspuns: 2, 3, 1, 7.

Urmează · 1 min

Oficial: simulare 2024, II.2

2 min

Vectorul este (8,1,4,5,0,9,4,5,4,3). Se cer toate nodurile cu un singur descendent direct.

Răspuns: 1, 3, 8, 9.

Barem: 6 p pentru toate. Punctajele parțiale: numai 2 p dacă un singur nod e bun, 3 p pentru două, 4 p pentru trei și 5 p dacă ai enumerat cinci sau șase noduri, dintre care patru sunt bune.

Urmează · 2 min

Oficial: sesiunea specială 2023, varianta 6, II.2

1 min

Vectorul este (0,1,1,2,2,4,5,1). Se cer toți descendenții nodului 2.

• Fiii lui 2: pozițiile cu valoarea 2, adică 4 și 5.
• Fiul lui 4 este 6, fiul lui 5 este 7.
• Nu există alți fii.

Răspuns: 4, 5, 6, 7. Barem: numai 3 p dacă ai scris doar descendenții direcți.

Urmează · 1 min

Oficial: grile de 4 puncte

6 min

Pentru rezervă 2026, nivelurile sunt: 3 pe nivelul 0; 1, 4, 8 pe nivelul 1; 2, 5, 6 pe nivelul 2; 7 pe nivelul 3.

Iunie 2023, varianta 5, I.4. Se cere un vector de tați pentru un arbore cu 7 noduri în care un nod are trei ascendenți.

• a. (0,1,2,1,1,1,2): cel mai adânc nod e pe nivelul 2, deci are doi ascendenți.
• b. (3,0,2,1,3,2,1): rădăcina e 2. Lanțul 4, 1, 3, 2 dă lui 4 trei ascendenți: 1, 3, 2. Barem: varianta b.
• c. (4,3,0,3,4,4,3): rădăcina e 3, iar cel mai adânc nod e pe nivelul 2.
• d. (5,4,3,0,2,3,4): t[3]=3, deci nodul 3 e propriul tată. Nu e un arbore.

Urmează · 6 min

Ce se cere la BAC

2 mincum apare la examen

Urmează · 2 min

Greșeli care costă puncte

2 mincapcanele de evitat

• Citești vectorul invers: poziția e fiul, valoarea e tatăl.
• Scrii doar fiii, când se cer toți descendenții. La sesiunea specială 2023 asta înjumătățește punctajul.
• Numeri nivelurile de la 1, deși rădăcina e pe nivelul 0.
• Uiți că frunzele sunt numerele care lipsesc din vector și le numeri pe cele care apar o singură dată.
• Enumeri lanțul de jos în sus, deși enunțul cere extremitatea inițială în rădăcină.
• Sari peste o valoare când grupezi. Scrie toate pozițiile sub vector înainte să numeri.

Urmează · 2 min