Cãutare secventialã/ Cãutare binarã/ Arbori binari / Tabele hash / Tehnici de rezolvare a coliziunilor / Prima paginã

 

Probleme propuse pentru arbori binari de cãutare



 1. Sã se considere un arbore binar care cuprinde strãmosii unei persoane , al cãrei nume figureazã în rãdãcina arborelui . Nodul care figureaza în stânga cuprinde numele tatãlui , iar cel din dreapta pe cel al mamei .Fiind dat numele unei persoane oarecare  din familie, sã se afiseze numele bunicilor , dacã acestia figureazã în arbore .

2. Sã se afiseze informatiile atasate nodurlor unui arbore binar , utilizând  parantezele rotunde pentru a marca nodurile situate pe acelasi nivel in arbore  .Exemplu : pentru arborele binar din figura urmãtoare  se afiseazã
          1(2(5( . , 6),3( . ,4(7 , .))))

3. Arãtati arborele binar construit printr-o serie de înserãri ,pentru urmãtorul sir de chei :
   8, 17, 10, 15, 5, 2, 16, 19, 13, 1 , 4, 11 .

4. Arborele binar complet  constituie un mijloc convenabil de a reprezenta un arbore cu lungimea minimã a drumului în locatii consecutive . Elaborati o metodã eficientã de cãutare, bazatã pe aceastã  reprezentare .[ Sugestie : Este posibil sã se utilizeze înmultirea cu 2 în loc de împãrtire  cu 2 intr-o cãutare binarã ? ] .

5. Existã  11! = 39.916.800 ordine diferite în care denumirile CAPRICORN , AQUARIUS etc.puteau fi înserate într-un arbore binar de cãutare . a) Câte din aceste aranjamente vor fi produse din figura  urmãtoare  ? b) Câte din aceste aranjamenta vor produce arbore degenerat ?


 

 

6. Dupã ce n elemente  au fost înserate într-un arbore initial vid , într-o ordine aleatoare , care este numãrul mediu de comparatii necesare pentru a gãsii al m –lea cel mai mare numãr ?

7. S-a demonstrat  cã operatia de cãutare cu ajutorul arborilor precum  si  cel de înserare necesitã doar circa 2 ln N comparatii atunci când cheile sunt înserate într-o ordine aleatoare ; dar in practicã ordinea poate sã nu fie cea aleatoare . Efectuati studii empirice pentru a constata cãt  de potrivitã este în realitate înserarea în arbori pentru tabelele de simboluri din cadrul compilatoarelor si  sau a asambloarelor . Conduc oare identificatorii folositi în cadrul programelor relativ  mari la arbori binari de cãutare rezonabil de bine echilibrati ?

8. Presupuneti cã pe un programator nu-l intereseazã proprietatea de sortare a acestui algoritm , dar el se asteaptã ca datele de intrare sã vinã într-o ordine nealeatoare . Discutati metodele prin care el poate încã utiliza cãutarea pe arbore fãcând ca intrarea datelor “ sa parã a fi “ în ordine aleatoare .

9. Gãsiti un arbore binar optim pentru cãutare , pentru cazul n = 40 , cu ponderile   p1 = 5  ,  p2 = p3 = …= p40 = 1  ,        q0 = q1 = …= q40 = 0 . ( Nu folositi un calculator .)

10. Care  este arborele binar cel mai dezavantajos  de cãutare , pentru cele 31 de cuvinte din limba englezã cel mai frecvent utilizate , folosind valorile frecventelor din figurã urmatoare ?

11. Considerati o schema  în care se construieste cu ajutorlul algoritmului de cãutare si înserare în arbore  un arbore binar de cãutare , cu exceptia ca de câte ori numãrul nodurilor ajunge la o valoare de forma arborele este reorganizat într-un arbore uniform perfect echilibrat , cu  noduri la nivelul k pentru 0<=k<n . Demonstrati cã numãrul de comparatii executate în timpul construirii unui asemenea arbore este egal cu Nlog2N+O(N) în medie .( Nu este dificil de aratat cã durata de timp necesara reorganizarilor este O(N).)
 

12. Formulati un algoritm  care face stergere în arborele 2-3  .

13. Implementati un program  Pascal  care foloseste diferite structuri pentru pentru algoritmul obtinut în problema  1 .

14.  Implementati un program Pascal pentru operatia de înserare  .

15. Demonstrati ca un arbore 2-3 de înãltime  h  contine între :
                                                                 
                                                            noduri frunze .

16. Formulati un algoritm specific care sterge si rebalanseazã un arbore binar balansat în greutate .

17. Formulati un algoritm care schimbã un nod particular într-un arbore balansat în greutate . apelarea algoritmului sã aibã forma

SCHIMBA ( CHEIE , GREUTATE_NOUA )

unde CHEIE este cheia nodului care se schimbã  si GREUTATE_NOUA  este greutatea noua a nodului  .
Observatie : GREUTATEA _NOUA  poate  sã aibã o valoare care poate cauza plasarea noduluila un nivel superior sau inferior în arbore .

 


 
Pagina anterioarã------Pagina urmãtoare


 

Proiect de diplomã -- Kakucs Ede Elemér -- Tehnologie Informaticã -- 2000