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

Hoe heet de stackbewerking die een element bovenaan toevoegt?

1. APop
2. BEnqueue
3. CPeek
4. DPush

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

1. ANiveau voor niveau vanaf de bovenkant
2. BLinkersubboom, dan knoop, dan rechtersubboom
3. CKnoop, dan linkersubboom, dan rechtersubboom
4. DLinkersubboom, dan rechtersubboom, dan knoop

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. BEen array doorlopen kost in totaal O(1), een gekoppelde lijst doorlopen O(n)
3. CGekoppelde lijsten slaan elementen altijd op schijf op
4. DArray-elementen liggen aaneengesloten, zodat ze de CPU-cache goed benutten

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

1. A1 2 4 5 3
2. B1 2 3 4 5
3. C4 5 2 3 1
4. D4 2 5 1 3

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

1. A2^h+1 − 1
2. B2h + 1
3. C2^h
4. Dh²

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

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

Waarom zou een server zijn hashfunctie willekeurig kiezen uit een universele familie?

1. AOm het zeer onwaarschijnlijk te maken dat een aanvaller veel sleutels kan kiezen die allemaal botsen
2. BOm het vergroten van de tabel overbodig te maken
3. COm de hashtabel gesorteerd te maken
4. DOm te garanderen dat geen twee sleutels ooit botsen, welke sleutels een aanvaller ook stuurt