Werkblad Datastructuren met antwoorden

Wat doet een hashfunctie in een hashtabel?

1. AVersleutelt de waarden in de tabel
2. BTelt hoeveel sleutels er zijn opgeslagen
3. CBeeldt een sleutel af op een index in de tabel
4. DSorteert de sleutels in de tabel

Welke datastructuur werkt volgens het principe "first in, first out" (FIFO)?

1. ABinaire boom
2. BWachtrij (queue)
3. CHeap
4. DStapel (stack)

Hoe worden de elementen van een array in het geheugen opgeslagen?

1. AIn een boom van geheugenpagina's
2. BOp willekeurige plaatsen gekozen door een hash
3. CIn één aaneengesloten blok, na elkaar
4. DVerspreid, verbonden door pointers

Een hashtabel van grootte 7 gebruikt h(k) = k mod 7 en linear probing. Waar wordt 17 opgeslagen nadat 10 is ingevoegd?

1. AIndex 3
2. BIndex 0
3. CIndex 4
4. DIndex 6

Een circulaire buffer (ring buffer) wordt vaak gebruikt om het volgende te implementeren:

1. AEen binaire zoekboom
2. BEen hashfunctie
3. CEen wachtrij met vaste grootte
4. DEen graafdoorloop

Hoe lang duurt het zoeken naar een woord met lengte L in een trie met een vast alfabet?

1. AO(log n), waarbij n het aantal woorden is
2. BO(L × n)
3. CO(n), waarbij n het aantal woorden is
4. DO(L), onafhankelijk van hoeveel woorden er zijn opgeslagen

Het verwijderen van een knoop met twee kinderen uit een binaire zoekboom gebeurt meestal door:

1. ADe hele subboom te verwijderen
2. BHem te vervangen door zijn in-order-opvolger (of -voorganger) en die knoop te verwijderen
3. CHem te verwisselen met de wortel
4. DDe deelboom eronder helemaal opnieuw op te bouwen en elke sleutel die erin zat opnieuw in te voegen

Welke garantie geven de regels van een rood-zwartboom over de hoogte van een boom met n sleutels?

1. ADe hoogte is hoogstens 2 log₂(n + 1)
2. BDe hoogte is hoogstens n / 2
3. CDe hoogte is hoogstens log₂ n + 1
4. DDe hoogte is precies log₂ n