Werkblad Datastructuren met antwoorden

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

1. AKleiner dan de waarde van de knoop
2. BIn willekeurige volgorde
3. CGelijk aan de waarde van de knoop
4. DGroter dan de waarde van de knoop

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

1. AStapel (stack)
2. BHash-set
3. CGraaf
4. DWachtrij (queue)

Hoe heet de queuebewerking die het element vooraan verwijdert?

1. AEnqueue
2. BDequeue
3. CPush
4. DInsert

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

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

Hoeveel knopen heeft een perfecte binaire boom met hoogte h, waarbij de hoogte in kanten wordt geteld?

1. A2^h+1 − 1
2. B2^h
3. Ch²
4. D2h + 1

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

1. A√n
2. B1
3. Cn (hij wordt een gekoppelde lijst)
4. Dlog₂ n

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

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

Een dynamische array verdubbelt als hij vol is. Waarom verkleinen veel implementaties hem pas als hij voor een kwart vol is, en niet voor de helft?

1. AOm herhaald vergroten en verkleinen te voorkomen als pushes en pops elkaar bij de grens afwisselen
2. BOmdat halveren bij de helft elementen zou kwijtraken
3. COm de array gesorteerd te houden
4. DOmdat de geheugenbeheerder geheugen alleen in kwarten van een blok kan vrijgeven