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. CHash-set
4. DStapel (stack)

Wat is de max-heap-eigenschap?

1. ADe sleutels zijn van links naar rechts gesorteerd
2. BAlle bladeren bevatten de maximale sleutel
3. CDe sleutel van elke ouder is groter dan of gelijk aan de sleutels van zijn kinderen
4. DDe sleutel van elk linkerkind is groter dan of gelijk aan de sleutel van zijn rechterbroer

Wat doet de bewerking peek (of top) op een stack?

1. AGeeft het bovenste element terug zonder het te verwijderen
2. BGeeft het onderste element van de stack terug
3. CVerwijdert alle elementen van de stack
4. DVerwijdert het bovenste element en geeft het terug

Wat geldt voor de adjacency matrix van een ongerichte graaf?

1. AZe is symmetrisch ten opzichte van de hoofddiagonaal
2. BZe is altijd bovendriehoeks
3. CHaar hoofddiagonaal bevat altijd enen
4. DElke rij heeft precies één 1

De sleutels 50, 30, 70, 20, 40 worden in deze volgorde in een lege binaire zoekboom ingevoegd. Wat is het linkerkind van 30?

1. A20
2. B40
3. C50
4. D70

Een in-order-doorloop van een binaire zoekboom bezoekt de sleutels in:

1. AVolgorde per niveau
2. BInvoegvolgorde
3. CAltijd aflopende volgorde
4. DOplopend gesorteerde volgorde

De tijdcomplexiteit van decrease-key in een binaire heap (als de positie van het element bekend is) is:

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

Een segmentboom (segment tree) wordt doorgaans gebruikt om:

1. AEen stack te implementeren
2. BDe kanten van een graaf op te slaan
3. CStrings alfabetisch te sorteren door elk voorvoegsel in een aparte boomknoop op te slaan
4. DBereikquery's (zoals bereiksommen) en updates in O(log n) te beantwoorden