Werkblad Datastructuren met antwoorden

Welke datastructuur is het meest geschikt voor de functie "ongedaan maken" (undo) in een teksteditor?

1. AWachtrij (queue)
2. BStapel (stack)
3. CGraaf
4. DHash-set

Wat doet de bewerking peek (of top) op een stack?

1. AGeeft het bovenste element terug zonder het te verwijderen
2. BGeeft het onderste element van de stack terug
3. CVerwijdert het bovenste element en geeft het terug
4. DVerwijdert alle elementen van de stack

Wat is het belangrijkste verschil tussen een statische en een dynamische array?

1. AEen dynamische array kan groeien door naar een groter geheugenblok te verhuizen
2. BEen statische array kan alleen getallen opslaan
3. CEen dynamische array slaat zijn elementen op in gekoppelde knopen zodat hij element voor element kan groeien
4. DEen statische array geeft tragere toegang via de index

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

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

Een in-order-doorloop van een binaire zoekboom bezoekt de sleutels in:

1. AAltijd aflopende volgorde
2. BVolgorde per niveau
3. CInvoegvolgorde
4. DOplopend gesorteerde volgorde

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. BArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten
3. CArrays gebruiken minder instructies om waarden te vergelijken
4. DGekoppelde lijsten slaan elementen altijd op schijf op

Je wilt voor elk element van een array het volgende grotere element rechts ervan vinden, in totaal O(n) tijd. Welke structuur helpt?

1. AEen queue die elk paar elementen bevat
2. BEen stack die elementen bewaart die op hun antwoord wachten
3. CEen binaire zoekboom die voor elk element opnieuw wordt opgebouwd
4. DEen hashtabel van alle elementen

Hoe verbetert een radix tree (gecomprimeerde trie) een gewone trie?

1. AHij slaat elk woord op in een hashtabel bij de wortel in plaats van in aparte knopen
2. BHij voegt ketens van knopen met één kind samen tot één kant met een string als label
3. CHij sorteert de kinderen van elke knoop op frequentie
4. DHij bewaart alleen de eerste letter van elk woord