Algoritmuselmélet 2010.11.19. PZH megoldásai
A lap korábbi változatát látod, amilyen Arklur (vitalap | szerkesztései) 2013. június 19., 20:29-kor történt szerkesztése után volt. (→7. Feladat)
Tartalomjegyzék
2010.11.19 - PZH megoldásai
1. Feladat
TODO
Megoldás
TODO
2. Feladat
TODO
Megoldás
TODO
3. Feladat
TODO
Megoldás
TODO
4. Feladat (Van megoldás)
Dijkstra algoritmussal határozza meg a G gráfban az [math]A[/math] pontból az összes többi pontba menő legrövidebb utak hosszát az [math]X[/math] pozitív valós paraméter függvényében. Minden lépésnél írja fel a távolságokat tartalmazó D tömb állapotát, és a KÉSZ halmaz elemeit.
5. Feladat
TODO
Megoldás
TODO
6. Feladat (Van megoldás)
Hajtsa végre az alábbi [math]F[/math] bináris keresőfán a BESZÚR(13), TÖRÖL(10) műveleteket! Minden lépést jelezzen!
7. Feladat (Van megoldás)
Egy piros-fekete fa gyökerének mindkét gyereke fekete. A gyökér baloldali részfájában 14, a jobboldali részfájában 63 elemet tárolunk. Mennyi lehet a fa fekete-magassága?
Megoldás
- Először vizsgáljuk a jobboldali részfát:
- Tudjuk, hogy [math] n \leq 2^m-1 \Rightarrow 63 \leq 2^m-1 \Rightarrow m \geq 6 [/math], vagyis a jobb oldali részfa magassága legalább 6.
- Továbbá [math] fm \geq \frac{m}{2} \Rightarrow fm \geq 3 [/math]
- Tudjuk, hogy [math] n \leq 2^m-1 \Rightarrow 63 \leq 2^m-1 \Rightarrow m \geq 6 [/math], vagyis a jobb oldali részfa magassága legalább 6.
- Most nézzük a baloldali részfát:
- Ismert, hogy [math] b_v \geq 2^{fm(v)}-1 \Rightarrow 14 \geq 2^{fm(v)}-1 \Rightarrow fm \leq 3.907 \Rightarrow \Rightarrow fm \lt 4 [/math]
- A 2 korlátot összevetve jön ki, hogy a bal és jobb részfa esetén [math] fm = 3.[/math]
- Emiatt az eredeti fában pedig [math] fm = 4.[/math]
8. Feladat
TODO
Megoldás
TODO