Werkblad Datastructuren met antwoorden

Welke structuur wordt doorgaans gebruikt om een prioriteitswachtrij te implementeren?

1. AEen heap
2. BEen ongeordende enkelvoudig gekoppelde lijst
3. CEen string
4. DEen stack

Wat is een blad in een boom?

1. AEen knoop zonder kinderen
2. BEen knoop zonder ouder
3. CDe knoop met de grootste waarde
4. DEen knoop met precies één kind

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

1. AWachtrij (queue)
2. BGekoppelde lijst
3. CHashtabel
4. DStapel (stack)

Hoe vind je de kleinste sleutel in een binaire zoekboom?

1. AVolg vanaf de wortel linkerkinderen tot er geen linkerkind meer is
2. BVolg vanaf de wortel rechterkinderen tot er geen rechterkind meer is
3. CBezoek elk blad en vergelijk ze
4. DKijk alleen naar de wortel

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 trie (prefixboom) is bijzonder efficiënt voor:

1. AZoeken op prefix, zoals automatisch aanvullen
2. BMatrices opslaan
3. CKortste paden vinden
4. DGetallen sorteren

Welke bewerkingen ondersteunt een Fenwick-boom (binary indexed tree) over een array van n getallen in O(log n)?

1. APrefixsomquery's en updates van één element
2. BDe array sorteren en binair zoeken
3. CElementen op elke positie invoegen
4. DDe mediaan vinden in O(1)

Wat zijn de tijd- en extra geheugenkosten van het ter plaatse omkeren van een enkelvoudig gekoppelde lijst?

1. AO(n log n) tijd en O(1) extra geheugen
2. BO(1) tijd en O(1) extra geheugen
3. CO(n) tijd en O(1) extra geheugen
4. DO(n) tijd en O(n) extra geheugen