Werkblad Datastructuren met antwoorden

De hoogte van een boom wordt gewoonlijk gedefinieerd als:

1. AHet aantal bladeren in de boom
2. BHet aantal kinderen van de wortel
3. CHet aantal kanten op het langste pad van de wortel naar een blad
4. DHet totale aantal knopen in de boom, inclusief de wortel en elk blad

Wat is een blad in een boom?

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

Wat is het bepalende kenmerk van een set (verzameling) als abstract datatype?

1. AZe slaat elementen gesorteerd op
2. BZe slaat sleutel-waardeparen op
3. CZe slaat elementen op zonder duplicaten
4. DZe staat alleen toegang aan één uiteinde toe

Een hashtabel van grootte 7 gebruikt h(k) = k mod 7 en linear probing. Waar wordt 17 opgeslagen nadat 10 is ingevoegd?

1. AIndex 3
2. BIndex 6
3. CIndex 4
4. DIndex 0

Wat kost het invoegen van een element in het midden van een array met n elementen?

1. AO(log n), vanwege binair zoeken
2. BO(n²), omdat elk element n keer verschuift
3. CO(1), omdat de index bekend is
4. DO(n), omdat latere elementen moeten opschuiven

Hoe vind je de kleinste sleutel in een binaire zoekboom?

1. AVolg vanaf de wortel linkerkinderen tot er geen linkerkind meer is
2. BBezoek elk blad en vergelijk ze
3. CVolg vanaf de wortel rechterkinderen tot er geen rechterkind meer is
4. DKijk alleen naar de wortel

Het algoritme van Kahn voor topologisch sorteren verwijdert herhaaldelijk knopen met ingraad 0. Welke structuur bevat die knopen?

1. AEen adjacency matrix die bijhoudt welke knopen al zijn verwijderd
2. BEen max-heap geordend op uitgraad
3. CEen stack van alle bezochte kanten
4. DEen queue (of een willekeurige verzameling) van knopen met ingraad 0

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