Werkblad Datastructuren met antwoorden

Wat is de bezettingsgraad (load factor) van een hashtabel?

1. AHet aantal buckets gedeeld door de gemiddelde lengte van de opgeslagen sleutels
2. BHet aantal botsingen tot nu toe
3. CHet aantal opgeslagen elementen gedeeld door het aantal buckets
4. DDe tijd die nodig is om de tabel van schijf te laden

Wat is een blad in een boom?

1. AEen knoop met precies één kind
2. BEen knoop zonder kinderen
3. CEen knoop zonder ouder
4. DDe knoop met de grootste waarde

Wat bevat in een enkelvoudig gekoppelde lijst de next-pointer van de laatste knoop?

1. AHet adres van de eerste knoop
2. BNull (geen knoop)
3. CHet aantal knopen in de lijst
4. DHet adres van de vorige knoop

Waarom kan een binaire heap zonder pointers in een array worden opgeslagen?

1. AHet is een complete binaire boom, dus posities volgen eenvoudige indexformules
2. BHeaps bevatten nooit meer dan 100 elementen
3. CArrays houden sleutels automatisch gesorteerd, dus er zijn geen pointers nodig
4. DAlle sleutels in een heap zijn gelijk

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 gesorteerde array
4. DEen dubbel gekoppelde lijst

Hoe wordt een nieuw element in een binaire heap ingevoegd?

1. APlaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt
2. BVoeg het op de gesorteerde positie in door alle grotere elementen één plaats naar rechts te verschuiven
3. CPlaats het in de wortel en laat het omlaag zakken (sift down)
4. DBouw de hele heap opnieuw op

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

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

In de BST met wortel 50, linkersubboom 30 (kinderen 20, 40) en rechtersubboom 70 (kinderen 60, 80) wordt de wortel verwijderd met behulp van de inorder-opvolger. Welke sleutel wordt de nieuwe wortel?

1. A80
2. B60
3. C40
4. D70