Werkblad Datastructuren met antwoorden

Wat is een botsing (collision) in een hashtabel?

1. ATwee verschillende sleutels worden op dezelfde index afgebeeld
2. BTwee gelijke sleutels worden twee keer opgeslagen
3. CEen sleutel kan helemaal niet worden gehasht
4. DDe tabel heeft geen geheugen meer

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

1. AKleiner dan de waarde van de knoop
2. BGroter dan de waarde van de knoop
3. CIn willekeurige volgorde
4. DGelijk aan de waarde van de knoop

Waar vind je het kleinste element van een binaire min-heap?

1. AOp de laatste positie in de array
2. BIn de wortel
3. CIn een willekeurig blad, dat moet worden gezocht
4. DIn het meest linkse blad

Je hebt een verwijzing naar een knoop in het midden van een lijst. In welke lijst kun je die in O(1) verwijderen?

1. AEen dynamische array
2. BEen dubbel gekoppelde lijst
3. CEen gesorteerde array
4. DEen enkelvoudig gekoppelde lijst

Hoe werkt extract-min in een binaire min-heap?

1. AVerwijder de wortel en schuif alle elementen één plaats naar links
2. BVerplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
3. CZoek in alle bladeren naar het nieuwe minimum
4. DVerwijder het laatste element van de array

Een queue wordt geïmplementeerd met twee stacks: push op een "in"-stack en pop van een "out"-stack, die vanuit "in" wordt bijgevuld als hij leeg is. Wat zijn de geamortiseerde kosten per bewerking?

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

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

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

Het verwijderen van een knoop met twee kinderen uit een binaire zoekboom gebeurt meestal door:

1. AHem te verwisselen met de wortel
2. BDe hele subboom te verwijderen
3. CHem te vervangen door zijn in-order-opvolger (of -voorganger) en die knoop te verwijderen
4. DDe deelboom eronder helemaal opnieuw op te bouwen en elke sleutel die erin zat opnieuw in te voegen