Werkblad Datastructuren met antwoorden

Wat slaat een map (dictionary) op?

1. AWaarden gesorteerd op grootte
2. BSleutel-waardeparen met unieke sleutels
3. CAlleen waarden in volgorde van invoegen
4. DParen van gelijke sleutels

In welke volgorde bezoekt een preorder-doorloop van een binaire boom de knopen?

1. ALinkersubboom, dan knoop, dan rechtersubboom
2. BLinkersubboom, dan rechtersubboom, dan knoop
3. CNiveau voor niveau vanaf de bovenkant
4. DKnoop, dan linkersubboom, dan rechtersubboom

Wat is een gerichte graaf?

1. AEen graaf waarvan alle kanten een gewicht hebben
2. BEen graaf zonder cykels
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 de waarde van de postfixexpressie 3 4 + 2 * ?

1. A24
2. B10
3. C11
4. D14

Hoeveel geheugen gebruikt een adjacency list voor een graaf met V knopen en E kanten?

1. AO(V × E)
2. BO(V + E)
3. CO(E²)
4. DO(V²)

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

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

Een dynamische array verdubbelt als hij vol is. Waarom verkleinen veel implementaties hem pas als hij voor een kwart vol is, en niet voor de helft?

1. AOmdat de geheugenbeheerder geheugen alleen in kwarten van een blok kan vrijgeven
2. BOm de array gesorteerd te houden
3. COm herhaald vergroten en verkleinen te voorkomen als pushes en pops elkaar bij de grens afwisselen
4. DOmdat halveren bij de helft elementen zou kwijtraken

De tijdcomplexiteit van decrease-key in een binaire heap (als de positie van het element bekend is) is:

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