Werkblad Datastructuren met antwoorden

Wat slaat een map (dictionary) op?

1. AWaarden gesorteerd op grootte
2. BAlleen waarden in volgorde van invoegen
3. CParen van gelijke sleutels
4. DSleutel-waardeparen met unieke sleutels

Wat is een gerichte graaf?

1. AEen graaf zonder cykels
2. BEen graaf waarvan alle kanten een gewicht hebben
3. CEen graaf waarin elk paar verschillende knopen door een kant verbonden is
4. DEen graaf waarvan de kanten een richting hebben van de ene knoop naar de andere

Wat is een botsing (collision) in een hashtabel?

1. AEen sleutel kan helemaal niet worden gehasht
2. BDe tabel heeft geen geheugen meer
3. CTwee gelijke sleutels worden twee keer opgeslagen
4. DTwee verschillende sleutels worden op dezelfde index afgebeeld

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 6
3. CIndex 3
4. DIndex 0

Wat is de tijdcomplexiteit van het zoeken naar een sleutel in een gebalanceerde binaire zoekboom?

1. AO(n)
2. BO(n log n)
3. CO(log n)
4. DO(1)

Een binaire boom heeft wortel 1 met linkerkind 2 en rechterkind 3; knoop 2 heeft kinderen 4 (links) en 5 (rechts). Wat is de preorder-doorloop?

1. A4 2 5 1 3
2. B1 2 3 4 5
3. C1 2 4 5 3
4. D4 5 2 3 1

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 gesorteerde array van alle n waarden
3. CEen min-heap met alle n waarden, waaruit aan het eind de k kleinste worden gehaald
4. DEen max-heap van grootte k, waarvan je de wortel vervangt als er een kleinere waarde binnenkomt

Welke datastructuur maakt een LRU-cache (least recently used) met get en put in O(1) mogelijk?

1. AEén gesorteerde array
2. BEen hashmap gecombineerd met een dubbel gekoppelde lijst
3. CAlleen een binaire zoekboom
4. DAlleen een stack