Werkblad Datastructuren met antwoorden

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

1. AStapel (stack)
2. BWachtrij (queue)
3. CHash-set
4. DGraaf

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 geeft tragere toegang via de index
3. CEen statische array kan alleen getallen opslaan
4. DEen dynamische array slaat zijn elementen op in gekoppelde knopen zodat hij element voor element kan groeien

Wat definieert een binaire boom?

1. AElke knoop slaat een binair getal op
2. BElke knoop heeft precies twee kinderen
3. CDe boom heeft precies twee niveaus
4. DElke knoop heeft hoogstens twee kinderen

Een knoop in een binaire zoekboom heeft een rechtersubboom. Waar staat zijn inorder-opvolger?

1. AAltijd zijn rechterkind
2. BDe meest linkse knoop van zijn rechtersubboom
3. CDe meest rechtse knoop van zijn linkersubboom
4. DAltijd zijn ouder

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

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

Een applicatie heeft snel opzoeken nodig en moet ook sleutels gesorteerd kunnen opsommen en bereikquery's beantwoorden. Welke structuur past het best?

1. AEen hashtabel
2. BEen gebalanceerde binaire zoekboom
3. CEen stack
4. DEen ongesorteerde gekoppelde lijst

Welke uitspraak over heapsort is juist?

1. AHet draait op elke invoer in O(n) tijd
2. BHet is stabiel en heeft O(n) extra geheugen nodig
3. CHet sorteert ter plaatse in O(n log n) in het slechtste geval, maar is niet stabiel
4. DHet heeft een binaire zoekboom nodig als extra opslag, dus het gebruikt O(n) extra geheugen

Aan welke eigenschap moet een rood-zwartboom voldoen?

1. AElke knoop moet rood zijn
2. BElk pad van een knoop naar zijn afstammende bladeren bevat evenveel zwarte knopen
3. CRode knopen moeten rode kinderen hebben, dus rode knopen vormen altijd ononderbroken ketens tot de bladeren
4. DDe wortel moet rood zijn