A feladat hasító tábla kitöltése. Három táblát kell
kitölteni ugyanazon 15 darab kulccsal. Az első táblában lineáris kipróbálást, a
másodikban kvadratikus kipróbálást, a harmadikban dupla hasítást kell
alkalmazni. Kiinduló adatként a táblaméret, egy kezdőkulcs és egy
kulcsnövekmény szolgál. A táblák üresen indulnak. Először négy kulcsot kell
beszúrni, majd a legkorábbit törölni. Ezután újra négy kulcsot kell beszúrni,
majd törölni a kezdetben másodiknak érkezettet. Ezután újabb négy beszúrás és a
kezdeti harmadik kulcs törlése jön, végül a megmaradt három kulcs beszúrása
következik. A kulcsok képzési szabálya: A kezdőkulcs adva van. A további kulcsokat
úgy képezzük, hogy mindig az előző kulcshoz hozzáadjuk a kulcsnövekményt. Ha a
kapott kulcs nagyobb lenne, mint 999, akkor 1000-et levonunk. Ha ezután 100-nál
kisebb kulcsot kapnánk, akkor 100-at hozzáadunk. Minden kulcs szigorúan
háromjegyű szám kell legyen. Lásd az 1. példát! Eredményül kérjük a kipróbálások
maximális indexét mindhárom esetben. (Zérus, ha azonnal sikerült a beszúrás, egy ha csak a kezdő próbálkozást
követő volt sikeres, stb.) Kérjük az eredményül kapott három táblát is a
beszúrt kulcsokkal, valamint az egyes rések állapotának a jelzésével. A rés
állapota foglalt, ha a kulcs előtt egy „+” jel áll és törölt, ha egy „-” jel áll. A
rés állapota szabad, ha a kulcs zérus és az állapotjel egy helyköz. Lásd a 2. példát! A számításhoz szükséges hasító
függvények láthatók az alábbi táblázatban. A táblázatban m a hasító tábla
mérete, és h0(k) =
k mod m.
|
Lineáris kipróbálás |
h(k,i) = (h0(k)+i) mod m |
|
Kvadratikus kipróbálás |
h(k,i) = (h0(k)+i*(i+1)/2) mod m |
|
Dupla hasítás |
h(k,i) = (h0(k)+i*h1(k)) mod m ahol h1(k) = 1+(k mod (m-1)) |
Meghatározandó a három kipróbálás esetének megfelelő
maximális számú próbálkozásszám. Az eredményeket egyetlen A/4-es
lapnak megfelelően egyetlen alkalommal e-mail jpg,
vagy pdf formátumú csatolmányaként kell elküldeni az adatstruktura@gmail.com e-mail címre. A levél tárgya
(Subject) a 3.HF,
(levelezőknél a LEV_3.HF) kell legyen. Az A/4-es lap
fejlécében a következő táblázat szerepeljen kitöltve:
|
Adatstruktúrák,
algoritmusok |
3. házi feladat |
||||||
|
|
|||||||
|
NEPTUN kód: |
|
Beadás dátuma: |
|
||||
|
Név (Nyomtatott nagybetűk): |
|
Sajátkezű aláírás: |
|
||||
|
Megoldások |
|||||||
|
táblaméret |
kezdőkulcs |
kulcsnövekmény |
Lineáris |
Kvadratikus |
Dupla hasítás |
||
|
|
|
|
|
|
|
||
A lapon szerepeljen a beszúrandó kulcsok felsorolása a
képzési sorrendnek megfelelően, valamint a három eredménytábla.