Werkblad Datastructuren met antwoorden

Wat definieert een binaire boom?

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

Welke datastructuur wordt gebruikt voor een level-order-doorloop van een boom?

1. AHashtabel
2. BQueue
3. CStack
4. DPrioriteitswachtrij

In een binaire zoekboom zijn de waarden in de linkersubboom van een knoop:

1. AGelijk aan de waarde van de knoop
2. BGroter dan de waarde van de knoop
3. CIn willekeurige volgorde
4. DKleiner dan de waarde van de knoop

Wat is in het slechtste geval de hoogte van een binaire zoekboom met n knopen als de sleutels in gesorteerde volgorde worden ingevoegd?

1. A1
2. Blog₂ n
3. Cn (hij wordt een gekoppelde lijst)
4. D√n

Wat kost het invoegen van een element in het midden van een array met n elementen?

1. AO(1), omdat de index bekend is
2. BO(n²), omdat elk element n keer verschuift
3. CO(log n), vanwege binair zoeken
4. DO(n), omdat latere elementen moeten opschuiven

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 ongesorteerde gekoppelde lijst
4. DEen stack

Wat doet een splay tree na elke toegang?

1. AKleurt de knopen op het zoekpad opnieuw
2. BBouwt de hele boom gebalanceerd opnieuw op
3. CRoteert de benaderde knoop omhoog naar de wortel
4. DVerplaatst de benaderde knoop naar een blad

Een AVL-knoop is ongebalanceerd omdat de rechtersubboom van zijn linkerkind te hoog werd (left-right-geval). Welke correctie wordt toegepast?

1. AEen rechtsrotatie bij het linkerkind, dan een linksrotatie bij de knoop
2. BEen enkele linksrotatie bij de knoop
3. CEen linksrotatie bij het linkerkind, dan een rechtsrotatie bij de knoop
4. DEen enkele rechtsrotatie bij de knoop