Werkblad Datastructuren met antwoorden

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

1. ABinaire boom
2. BStapel (stack)
3. CWachtrij (queue)
4. DHeap

Wat is een deque (double-ended queue)?

1. AEen queue gesorteerd op prioriteit
2. BEen structuur die invoegen en verwijderen aan beide uiteinden toestaat
3. CTwee aparte queues die één array delen
4. DEen queue die alleen verwijderen achteraan toestaat

Welke bewerking is O(1) voor een array maar O(n) voor een enkelvoudig gekoppelde lijst?

1. AInvoegen aan de kop
2. BHet eerste element lezen
3. CHet element op index i benaderen
4. DHet kopelement verwijderen

AVL-bomen en rood-zwartbomen garanderen:

1. AEen hoogte van O(log n) door herbalancering
2. BZoeken in constante tijd in elk geval
3. CDat sleutels in invoegvolgorde worden opgeslagen
4. DDat geen enkele knoop twee kinderen heeft

Waarom kan een binaire heap zonder pointers in een array worden opgeslagen?

1. AHeaps bevatten nooit meer dan 100 elementen
2. BArrays houden sleutels automatisch gesorteerd, dus er zijn geen pointers nodig
3. CAlle sleutels in een heap zijn gelijk
4. DHet is een complete binaire boom, dus posities volgen eenvoudige indexformules

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

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

Door het invoegen van een sleutel in een AVL-boom wordt de linkersubboom van een knoop te hoog, en de nieuwe sleutel kwam in de linkersubboom van zijn linkerkind (left-left-geval). Welke correctie wordt toegepast?

1. AEen enkele linksrotatie bij de ongebalanceerde knoop
2. BHet opnieuw kleuren van de knoop en zijn kind
3. CEen linksrotatie bij het kind, dan een rechtsrotatie bij de knoop
4. DEen enkele rechtsrotatie bij de ongebalanceerde knoop

Welke garantie geven de regels van een rood-zwartboom over de hoogte van een boom met n sleutels?

1. ADe hoogte is hoogstens n / 2
2. BDe hoogte is hoogstens 2 log₂(n + 1)
3. CDe hoogte is hoogstens log₂ n + 1
4. DDe hoogte is precies log₂ n