Werkblad Datastructuren met antwoorden

Wat is de bezettingsgraad (load factor) van een hashtabel?

1. AHet aantal botsingen tot nu toe
2. BHet aantal buckets gedeeld door de gemiddelde lengte van de opgeslagen sleutels
3. CDe tijd die nodig is om de tabel van schijf te laden
4. DHet aantal opgeslagen elementen gedeeld door het aantal buckets

In een enkelvoudig gekoppelde lijst bevat elke knoop:

1. AData en een verwijzing naar de volgende knoop
2. BData en verwijzingen naar alle andere knopen
3. CData en een index
4. DAlleen data

Wat doet de bewerking peek (of top) op een stack?

1. AVerwijdert alle elementen van de stack
2. BGeeft het bovenste element terug zonder het te verwijderen
3. CGeeft het onderste element van de stack terug
4. DVerwijdert het bovenste element en geeft het terug

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

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

Hoe wordt in een circulaire queue in een array met capaciteit n de volgende positie na index i berekend?

1. Ai + 1
2. B2i + 1
3. C(i + 1) mod n
4. D(i − 1) mod n

Wat is de maximaal mogelijke load factor in een hashtabel met open addressing?

1. A2
2. B0,5
3. C1
4. DEr is geen maximum

Door het invoegen van een sleutel in een AVL-boom wordt de linkersubboom van een knoop te hoog, en de nieuwe sleutel kwam in de linkersubboom van zijn linkerkind (left-left-geval). Welke correctie wordt toegepast?

1. AEen linksrotatie bij het kind, dan een rechtsrotatie bij de knoop
2. BEen enkele linksrotatie bij de ongebalanceerde knoop
3. CEen enkele rechtsrotatie bij de ongebalanceerde knoop
4. DHet opnieuw kleuren van de knoop en zijn kind

De union-find-structuur (disjoint set) met union by rank en padcompressie heeft geamortiseerde kosten per bewerking van:

1. AO(n²)
2. BPrecies O(log n)
3. CO(α(n)), de inverse Ackermann-functie, die in de praktijk constant is
4. DO(n)