Werkblad Datastructuren met antwoorden

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

Wat doet een hashfunctie in een hashtabel?

1. ASorteert de sleutels in de tabel
2. BTelt hoeveel sleutels er zijn opgeslagen
3. CBeeldt een sleutel af op een index in de tabel
4. DVersleutelt de waarden in de tabel

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

1. AIn een willekeurig blad, dat moet worden gezocht
2. BIn de wortel
3. COp de laatste positie in de array
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 enkelvoudig gekoppelde lijst
3. CEen dubbel gekoppelde lijst
4. DEen gesorteerde array

Een circulaire buffer (ring buffer) wordt vaak gebruikt om het volgende te implementeren:

1. AEen graafdoorloop
2. BEen hashfunctie
3. CEen wachtrij met vaste grootte
4. DEen binaire zoekboom

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 3 4 5
2. B4 5 2 3 1
3. C1 2 4 5 3
4. D4 2 5 1 3

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

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

Hoe lang duurt het zoeken naar een willekeurige sleutel in een binaire min-heap van n elementen?

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