Werkblad Datastructuren met antwoorden

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

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

De diepte van een knoop in een boom is:

1. AHet aantal knopen in zijn subboom
2. BHet aantal kanten van die knoop tot het diepste blad
3. CHet aantal kanten van de wortel tot die knoop
4. DHet aantal kinderen van die knoop

Welke bewerking is O(1) voor een array maar O(n) voor een enkelvoudig gekoppelde lijst?

1. AHet element op index i benaderen
2. BInvoegen aan de kop
3. CHet kopelement verwijderen
4. DHet eerste element lezen

Wat is de maximaal mogelijke load factor in een hashtabel met open addressing?

1. A2
2. B1
3. CEr is geen maximum
4. D0,5

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(1)
2. BO(log n)
3. CO(n²)
4. DO(n)

In een binaire min-heap die in een array is opgeslagen (index begint bij 0), staan de kinderen van de knoop op index i op:

1. A2i en 2i + 1
2. B2i + 1 en 2i + 2
3. Ci/2 en i/2 + 1
4. Di + 1 en i + 2

Een segmentboom (segment tree) wordt doorgaans gebruikt om:

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

Aan welke regel moeten hash en gelijkheid voldoen om een hashtabel correct te laten werken?

1. AGelijke hashwaarden impliceren gelijke sleutels
2. BGelijke sleutels moeten gelijke hashwaarden hebben
3. CHashwaarden moeten priemgetallen zijn
4. DVerschillende sleutels moeten verschillende hashwaarden hebben