Adatszerkezetek és algoritmusok
Vizsgafeladatsor, 2014. 06. 03.

1) Posztorder bejárással egy bináris keresőfát bejárva ezt kaptuk:
   18, 20, 26, 21, 19, 40, 39, 43, 41, 31
   
   a) Rajzold fel a fát!
   b) Kiegyensúlyozott? Minimális magasságú? Indoklással
   c) Írd le a bin. keresőfa preorder bejárásának algoritmusát mondatszerűen!
   d) Járd be a fát preorder módon, és írd le íz eredményt!

2) a) Bináris fából való törlés algoritmusa
   b) Rajzolj fel 10 egész számot tartalmazó minimális magasságú bin. keresőfát!
   c) Töröld ennek a fának a gyökérelemét, majd rajzold fel az eredményfát!

3) Egy 6 magasságú bin. fában max. mennyi elemet lehet tárolni?

4) Mik a szinonimák, és hogyan kezeljük független túlcsordulási listával?

5) a) Mi az a verem, és milyen műveletei vannak?
   b) Verem szétszórt reprezentációja, és a fontosabb műveletek megvalósítása
      szétszórt reprezentáció esetén

6) a) AVL-fa, jellemzői
   b) Bővítésekor előforduló RR és LR esetek, megoldásaik, rajzzal együtt
   c) Csinálj AVL-fát ebből, majd rajzold fel a kapott fát:
      6, 11, 21, 20, 19, 23, 4, 2

7) a) Hash függvény def.
   b) Valódi prefix def.
   c) Cirkuláris lista deb.
   Mindegyikhez példa is.

8) Hol lehet használni a Vyssotzky-módszert, és hogyan működik?

9) KMP algoritmus esetében mit határoz meg a KÖV tömb i-edik eleme?

10) (Opcionális)
    Írj egy C eljárást, ami megfordítja egy tömb elemeinek sorrendjét a tömb
    és annak elemszámának ismeretével!