Algoritmuselmélet - ZH, 2013.04.03.
A lap korábbi változatát látod, amilyen Arklur (vitalap | szerkesztései) 2013. június 12., 19:28-kor történt szerkesztése után volt. (→3. Feladat)
Tartalomjegyzék
2013.04.03. ZH megoldásai
1. Feladat
TODO
Megoldás
TODO
2. Feladat
TODO
Megoldás
TODO
3. Feladat (Van megoldás)
Kaphatjuk-e az 1,7,3,6,11,15,22,17,14,12,9 számsorozatot úgy, hogy egy (a szokásos rendezést használó) bináris keresőfában tárolt elemeket posztorder sorrendben kiolvasunk?
Megoldás
Megjegyzés a feladathoz
- Szokásos rendezést használó bináris keresőfa: [math]bal(x) \lt x \lt jobb(x)[/math]
- Postorder:
- Rekurzívan [math] bal(x) \rightarrow jobb(x) \rightarrow x [/math]. Magyarul előbb meglátogatja a gyökérnél kisebbeket, utána a nagyobbakat, és ezután jön csak a gyökér.
- Egyik fontos tulajdonsága, hogy a gyökér az mindig a (figyelt) lista végén van.
- Első lépésnek írjuk fel egy táblázatba a számokat (az oszlopszámot tudjuk, ez esetben 11, sorok száma meg majd alakul...).
- A továbbiakban az i. sorban jelöljük, hogy melyik elem a gyökér (=), és hogy melyek a nála kisebbek (<), avagy nagyobbak (>) (a képen keretezéssel jelzem, hogy melyik az éppen figyelt lista). Ez azért hasznos, mert a posztorder bejárás során, ezzel a technikával mindig olyan sorrendet kell kapjunk, hogy [math] \lt \lt \lt ... \lt \lt \gt \gt ... \gt \gt = [/math], vagyis nem állhat fel olyan helyzet, hogy [math] ... \lt \gt \lt ...[/math] vagy [math] ... \gt \lt \gt ....[/math]
- Az 1. sorban a 9 lesz a gyökér. Felrajzoljuk a 9-t gyökérnek. (Bal oldalt lesz a hiba, de gyakorlásképp nézzük inkább a jobb oldalt.)
- A 2. sorban a 12 lesz a gyökér, így a 12-est felrajzoljuk a 9-es jobb fiának. Nála csak a 11 a kisebb (a vizsgált listában), így a 11-t berajzoljuk a 12 bal fiának.
- A 3. sorban 14 lesz a gyökér, így e 14-est felrajzoljuk a 12-es jobb fiának.
- A 4. sorban a 17 lesz a gyökér, így ez a 14-es jobb fia lesz. A 15 és 22 pedig értelemszerűen a bal, és jobb fia lesz 17-nek.
- Az 5. sorban a gyökér a 6 lesz, így azt berajzoljuk a 9-es bal fiának. És itt látszik is, hogy hiba van, hiszen [math] \lt \gt \lt [/math] sorrend van, ebből következik, hogy ilyen fa nem létezhet.
4. Feladat
TODO
Megoldás
TODO
5. Feladat
TODO
Megoldás
TODO
6. Feladat
TODO
Megoldás
TODO
7. Feladat
TODO
Megoldás
TODO
8. Feladat
TODO
Megoldás
TODO
