Nederlands
Menu

Datastructuren en algoritmen

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.

  1. AChaining kan elementen opslaan ook als de bezettingsgraad groter is dan 1, maar open adressering kan niet meer elementen opslaan dan de tabel groot is, en het aantal pogingen neemt sterk toe als de bezettingsgraad 1 nadert
  2. BBij open adressering treden geen botsingen op, dus een zoekactie kost altijd één poging, ongeacht de bezettingsgraad
  3. CBij chaining blijft de zoekinspanning gelijk, hoe hoog de bezettingsgraad ook wordt
Antwoord en toelichting tonen

Antwoord: A. Chaining kan elementen opslaan ook als de bezettingsgraad groter is dan 1, maar open adressering kan niet meer elementen opslaan dan de tabel groot is, en het aantal pogingen neemt sterk toe als de bezettingsgraad 1 nadert

Chaining koppelt elementen op dezelfde positie tot lijsten en kan dus meer elementen opslaan dan de tabel groot is, maar de gemiddelde lijstlengte groeit evenredig met de bezettingsgraad, en de zoekinspanning ook. Open adressering slaat alles in de tabel zelf op en kan dus hoogstens zoveel elementen bevatten als de tabel groot is; het aantal pogingen om een vrije plaats te vinden neemt sterk toe als de bezettingsgraad 1 nadert. Bij beide methoden is het gebruikelijk om de tabel te vergroten en alle elementen opnieuw in te voegen (rehashing) zodra de bezettingsgraad een gekozen grens overschrijdt, bijvoorbeeld ongeveer 0,5 tot 0,75. Ook bij open adressering treden botsingen op; ze worden opgevangen door een vrije positie te zoeken.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

  1. Wat is een voorwaarde om binair zoeken te kunnen gebruiken, dat de gezochte waarde met het middelste element vergelijkt en het zoekbereik telkens halveert?
  2. 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?
  3. 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?
  4. 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?
  5. De array 29, 10, 14, 37, 13 wordt met selection sort oplopend gesorteerd: het minimum van het ongesorteerde deel wordt gezocht en verwisseld met het eerste element van het ongesorteerde deel. Hoe ziet de array eruit nadat deze stap twee keer is uitgevoerd?