Werkblad Datastructuren met antwoorden

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

1. AHeap
2. BBinaire boom
3. CWachtrij (queue)
4. DStapel (stack)

Een hashtabel slaat data op als:

1. ASleutel-waardeparen die via een hashfunctie worden gevonden
2. BEen boom met geordende sleutels
3. CUitsluitend een gesorteerde lijst
4. DEen string met vaste lengte

Wat is een deque (double-ended queue)?

1. ATwee aparte queues die één array delen
2. BEen queue die alleen verwijderen achteraan toestaat
3. CEen structuur die invoegen en verwijderen aan beide uiteinden toestaat
4. DEen queue gesorteerd op prioriteit

Waarom is het doorlopen van een array in de praktijk vaak veel sneller dan het doorlopen van een gekoppelde lijst van dezelfde lengte?

1. AArrays gebruiken minder instructies om waarden te vergelijken
2. BArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
3. CEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)
4. DGekoppelde lijsten slaan elementen altijd op schijf op

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

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

Wat gebeurt er als een hashtabel rehasht nadat de load factor een drempel overschrijdt?

1. ADe oudste sleutels worden verwijderd om ruimte te maken
2. BDe bestaande sleutels worden ter plaatse gesorteerd
3. CAlleen de botsende sleutels worden naar een nieuwe overloop-lijst aan het eind van de tabel verplaatst
4. DEr wordt een grotere tabel gereserveerd en elke sleutel wordt opnieuw ingevoegd

Wat doet een splay tree na elke toegang?

1. ABouwt de hele boom gebalanceerd opnieuw op
2. BVerplaatst de benaderde knoop naar een blad
3. CKleurt de knopen op het zoekpad opnieuw
4. DRoteert de benaderde knoop omhoog naar de wortel

Je moet uit een stroom van n getallen de k kleinste waarden bewaren met O(k) geheugen. Welke aanpak werkt in O(n log k) tijd?

1. AEen FIFO-queue van de laatste k waarden
2. BEen max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt
3. CEen gesorteerde array van alle n waarden
4. DEen min-heap met alle n waarden, waaruit aan het eind de k kleinste worden gehaald