Lista de probleme 93

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine cele mai mici valori număr prim din subarborii stâng și drept ai rădăcinii.

Se dă un șir a[1], a[2], …, a[n] de numere naturale și un număr natural k. Să se determine cele mai mari k numere din șir.

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se afișeze valorile din arbore în urma parcurgerii în lățime, pornind din rădăcină.

Se dă o matrice pătratică de dimensiune N. Asupra ei se fac 2 tipuri de operații:

• 1 x y val – elementul de coordonate x y crește cu val
• 2 x1 y1 x2 y2 – se cere suma elementelor submatricei cu colțul stânga-sus de coordonate x1 y1 și cel drepta jos de coordonate x2 y2.

Dându-se Q operații să se raspundă în ordine la cele de tip 2.

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine înălțimea arborelui.

Dirigu’ vrea să știe care este cel mai frecvent prenume printre elevii din clasa noastră. Pentru aceasta a realizat o listă cu cele n prenume ale elevilor din clasă și acum vă cere să determinați prenumele cel mai frecvent și numărul său de apariții.

Dacă sunt mai multe prenume cu număr maxim de apariții se va determina primul în ordine alfabetică.

Gigel este la ora de informatică, iar profesorul i-a dat o sarcină: să sorteze numele celor n colegi ai săi după o regulă specială. Fiecărui nume i se asociază un număr care iniţial este 0 și crește cu 1 pentru fiecare pereche de vocale consecutive și scade cu 1 pentru fiecare pereche de consoane consecutive Dacă perechea este formată dintr-o vocală și o consoană, numărul nu se modifică.

Dându-se cele n nume ale colegilor, să se sorteze crescător după numerele asociate. La numere egale, se vor sorta alfabetic.

Se consideră un arbore binar în care nodurile memorează numere naturale nenule și un număr k. În arbore rădăcina se află pe nivelul 0, fii rădăcinii pe nivelul 1, fii fiilor rădăcinii pe nivelul 2, etc. Să se determine suma valorilor din nodurile aflate pe nivelul k.

Șcuțu, elev pe clasa a 10-a, s-a plictisit să lucreze probleme de clasa a 6-a. Mygo a văzut că Șcuțu a reușit să obțină 100p pe problema Munte de la OJI2014, însă nu cu o soluție prea inteligentă, așa că îi va pune o provocare. Se dă un vector A de N elemente indexat de la 1. Un vârf este un element A[i] cu proprietatea că A[i-1] < A[i] > A[i+1] (1 < i < N). Mygo îi oferă lui Șcuțu Q operații de tipul:

• 1 x y: “Elementul de pe poziția x ia valoarea y”.
• 2 x y: “Având o copie a vectorului A[x...y] (ceea ce urmează nu va afecta cu nimic vectorul A), se determină toate vârfurile iar acestea se elimină, procedeul acesta continuă până când nu vor mai exista vârfuri. Se cere să se afișeze câte vârfuri au existat de la început până la final”.

Un arbore binar de căutare (BST – Binary Search Tree) este un arbore binar cu proprietatea că valoarea memorată într-un nod este mai mare decât valoarea memorată în orice nod din subarborele său stâng și este mai mică sau egală decât valoarea memorată în orice nod din subarborele său drept. Dându-se un șir de n numere naturale, să se ordoneze crescător utilizând un BST.