Werkblad Datastructuren met antwoorden

Wat bevat in een enkelvoudig gekoppelde lijst de next-pointer van de laatste knoop?

1. ANull (geen knoop)
2. BHet aantal knopen in de lijst
3. CHet adres van de vorige knoop
4. DHet adres van de eerste knoop

Welke bewerking is traag in een array maar snel aan de kop van een gekoppelde lijst?

1. AHet 5e element benaderen
2. BDe lengte van een array met vaste grootte bepalen
3. CInvoegen aan het begin
4. DHet laatste element via de index lezen

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

1. ABinaire boom
2. BHeap
3. CStapel (stack)
4. DWachtrij (queue)

Hoeveel knopen heeft een perfecte binaire boom met hoogte h, waarbij de hoogte in kanten wordt geteld?

1. A2h + 1
2. B2^h+1 − 1
3. Ch²
4. D2^h

Welke datastructuur gebruikt een draaiend programma om actieve functieaanroepen en hun lokale variabelen bij te houden?

1. AEen binaire zoekboom van frames
2. BDe call stack
3. CDe wachtrij van het heapgeheugen
4. DEen hashtabel van functies

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)

Het verwijderen van een knoop met twee kinderen uit een binaire zoekboom gebeurt meestal door:

1. ADe deelboom eronder helemaal opnieuw op te bouwen en elke sleutel die erin zat opnieuw in te voegen
2. BHem te vervangen door zijn in-order-opvolger (of -voorganger) en die knoop te verwijderen
3. CDe hele subboom te verwijderen
4. DHem te verwisselen met de wortel

De union-find-structuur (disjoint set) met union by rank en padcompressie heeft geamortiseerde kosten per bewerking van:

1. AO(n²)
2. BO(α(n)), de inverse Ackermann-functie, die in de praktijk constant is
3. CO(n)
4. DPrecies O(log n)