Werkblad Datastructuren met antwoorden

Wat is een gewogen graaf?

1. AEen graaf met meer kanten dan knopen
2. BEen graaf die op schijf is opgeslagen
3. CEen graaf waarin sommige knopen zwaarder zijn dan andere doordat ze meer kanten hebben
4. DEen graaf waarin elke kant een numerieke waarde heeft, zoals kosten of afstand

Een hashtabel slaat data op als:

1. AEen string met vaste lengte
2. BUitsluitend een gesorteerde lijst
3. CSleutel-waardeparen die via een hashfunctie worden gevonden
4. DEen boom met geordende sleutels

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

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

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

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

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

1. A2i + 1
2. B(i − 1) mod n
3. Ci + 1
4. D(i + 1) mod n

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. CEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)
4. DGekoppelde lijsten slaan elementen altijd op schijf op

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

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

Wat doet een splay tree na elke toegang?

1. AKleurt de knopen op het zoekpad opnieuw
2. BRoteert de benaderde knoop omhoog naar de wortel
3. CBouwt de hele boom gebalanceerd opnieuw op
4. DVerplaatst de benaderde knoop naar een blad