Werkblad Datastructuren met antwoorden

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

1. AGraaf
2. BWachtrij (queue)
3. CStapel (stack)
4. DHash-set

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

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

Een hashtabel slaat data op als:

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

Welke balansvoorwaarde handhaaft een AVL-boom in elke knoop?

1. ABeide subbomen van elke knoop bevatten precies hetzelfde aantal knopen
2. BDe hoogten van de linker- en rechtersubboom verschillen hoogstens 1
3. CElke knoop is rood of zwart gekleurd
4. DAlle bladeren liggen op precies dezelfde diepte

Hoeveel geheugen gebruikt een adjacency list voor een graaf met V knopen en E kanten?

1. AO(V²)
2. BO(V + E)
3. CO(V × E)
4. DO(E²)

AVL-bomen en rood-zwartbomen garanderen:

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

Hoe lang duurt het zoeken naar een willekeurige sleutel in een binaire min-heap van n elementen?

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

Hoe kun je met O(1) extra geheugen detecteren of een enkelvoudig gekoppelde lijst een cykel bevat?

1. ATel de knopen tot het aantal het lengteveld van de lijst overschrijdt
2. BSorteer de lijst en zoek naar duplicaten
3. CVerplaats één pointer telkens één stap en een andere twee stappen en kijk of ze elkaar ontmoeten
4. DSla elke bezochte knoop op in een hash-set