Nederlands
Menu

Datastructuren en algoritmen

De sleutels 10, 17, 24 en 3 worden in deze volgorde opgeslagen in een hashtabel van grootte 7 (posities 0 tot 6) met de hashfunctie h(k) = k mod 7. Botsingen worden opgelost met lineair proberen (linear probing): de positie schuift telkens één plaats op (na 6 komt 0) tot er een vrije plaats is gevonden. Op welke positie wordt sleutel 3 opgeslagen?

  1. APositie 3
  2. BPositie 4
  3. CPositie 6
Antwoord en toelichting tonen

Antwoord: C. Positie 6

Alle vier de sleutels geven bij deling door 7 de rest 3, dus elk probeert eerst positie 3. Sleutel 10 komt op positie 3; 17 vindt positie 3 bezet en komt op positie 4; 24 vindt posities 3 en 4 bezet en komt op positie 5. Sleutel 3 vindt posities 3, 4 en 5 bezet en wordt op positie 6 opgeslagen. Zoals dit laat zien, gaan bij lineair proberen bezette posities aaneengesloten blokken vormen (clustering), zodat later aankomende sleutels meer pogingen nodig hebben.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

  1. Welke vergelijking van chaining (de elementen op dezelfde positie aan elkaar koppelen in een gelinkte lijst) en open adressering (een andere vrije positie in de tabel zoeken) als methoden om botsingen in een hashtabel af te handelen is juist? De bezettingsgraad (load factor) is het aantal opgeslagen elementen gedeeld door de grootte van de tabel.
  2. Wat is een voorwaarde om binair zoeken te kunnen gebruiken, dat de gezochte waarde met het middelste element vergelijkt en het zoekbereik telkens halveert?
  3. Met binair zoeken wordt een waarde gezocht in 1000 verschillende waarden die oplopend gesorteerd zijn. Eén vergelijking laat zien of de waarden gelijk zijn of dat de ene kleiner of groter is. Wat is het maximale aantal vergelijkingen, voor zowel een geslaagde als een mislukte zoekactie?
  4. Binair zoeken zoekt 38 in de oplopende array a[0] tot a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. Het zoekbereik begint met lo = 0 en hi = 9, en de middelste positie is (lo + hi) ÷ 2, naar beneden afgerond. Welke reeks geeft, in volgorde, de waarden van de elementen waarmee 38 wordt vergeleken?
  5. De array 5, 3, 8, 1, 4 wordt met bubblesort oplopend gesorteerd. Hoe ziet de array eruit na één doorgang (pass), waarin vanaf het begin tot het eind telkens twee buren worden vergeleken en verwisseld als het linkerelement groter is?