Algoritmuselmélet 2010.11.19. PZH megoldásai

← Vissza az előző oldalra – Algoritmuselmélet

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.

Megoldás

• Egy egyszerű Dijkstra-s feladat.
• Annyit kell megjegyezni hozzá, hogy:
  • Ha [math] X \leq 2 [/math], akkor az [math]X[/math] élt [math]( D \rightarrow E )[/math] veszi be.
  • Ha [math] X \geq 2 [/math], akkor a [math]C \rightarrow E [/math] élt veszi be.

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!

Megoldás

• BESZÚR(13):
  • Egyszerű, mint az 1x1
    

• TÖRÖL(10):
  • Töröljük a 10-t.
  • A BAL oldali részfából kiválasztjuk a LEGNAGYOBB elemet, és berakjuk a gyökérbe (ebben az esetben a 7).
  • A fát rendbe rakjuk (ez esetben a 6-t beírjuk a 7 régi helyére).
    

7. Feladat

TODO

Megoldás

TODO

8. Feladat

TODO

Megoldás

TODO