Werkblad Datastructuren met antwoorden

Wat zijn broer- of zusknopen (siblings) in een boom?

1. AKnopen zonder kinderen
2. BEen knoop en zijn ouder
3. CKnopen op dezelfde diepte in verschillende subbomen
4. DKnopen die dezelfde ouder hebben

Wat is een botsing (collision) in een hashtabel?

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

Wat is het belangrijkste verschil tussen een statische en een dynamische array?

1. AEen statische array geeft tragere toegang via de index
2. BEen dynamische array kan groeien door naar een groter geheugenblok te verhuizen
3. CEen statische array kan alleen getallen opslaan
4. DEen dynamische array slaat zijn elementen op in gekoppelde knopen zodat hij element voor element kan groeien

Waarom is het doorlopen van een array in de praktijk vaak veel sneller dan het doorlopen van een gekoppelde lijst van dezelfde lengte?

1. AArrays gebruiken minder instructies om waarden te vergelijken
2. BGekoppelde lijsten slaan elementen altijd op schijf op
3. CEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)
4. DArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten

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

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

Een binaire boom heeft wortel 1 met linkerkind 2 en rechterkind 3; knoop 2 heeft kinderen 4 (links) en 5 (rechts). Wat is de postorder-doorloop?

1. A4 2 5 1 3
2. B5 4 3 2 1
3. C1 2 4 5 3
4. D4 5 2 3 1

Een segmentboom (segment tree) wordt doorgaans gebruikt om:

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

Wat is de looptijd van breadth-first search op een graaf met V knopen die als adjacency matrix is opgeslagen?

1. AO(V²)
2. BO(V)
3. CO(V + E)
4. DO(E log V)