Werkblad Datastructuren met antwoorden

In welke volgorde bezoekt een preorder-doorloop van een binaire boom de knopen?

1. ALinkersubboom, dan rechtersubboom, dan knoop
2. BLinkersubboom, dan knoop, dan rechtersubboom
3. CNiveau voor niveau vanaf de bovenkant
4. DKnoop, dan linkersubboom, dan rechtersubboom

De diepte van een knoop in een boom is:

1. AHet aantal kanten van de wortel tot die knoop
2. BHet aantal kanten van die knoop tot het diepste blad
3. CHet aantal kinderen van die knoop
4. DHet aantal knopen in zijn subboom

Een graaf bestaat uit:

1. AAlleen sleutels en hashes
2. BKnopen (vertices) verbonden door kanten
3. CAlleen een wortel en bladeren
4. DRijen en kolommen

Wat is de tijdcomplexiteit van het zoeken naar een sleutel in een gebalanceerde binaire zoekboom?

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

AVL-bomen en rood-zwartbomen garanderen:

1. ADat sleutels in invoegvolgorde worden opgeslagen
2. BEen hoogte van O(log n) door herbalancering
3. CZoeken in constante tijd in elk geval
4. DDat geen enkele knoop twee kinderen heeft

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

1. Ah²
2. B2h + 1
3. C2^h
4. D2^h+1 − 1

In een circulaire buffer kan front == rear zowel leeg als vol betekenen. Wat is een gangbare manier om ze te onderscheiden?

1. ASla front en rear op in dezelfde variabele
2. BMaak de buffergrootte een macht van twee
3. CHoud een apart aantal elementen bij, of laat altijd één plaats ongebruikt
4. DMaak de buffer altijd leeg als front gelijk is aan rear, zodat de toestand leeg is

Welke bewerkingen ondersteunt een Fenwick-boom (binary indexed tree) over een array van n getallen in O(log n)?

1. APrefixsomquery's en updates van één element
2. BDe mediaan vinden in O(1)
3. CDe array sorteren en binair zoeken
4. DElementen op elke positie invoegen