Werkblad Datastructuren met antwoorden

De hoogte van een boom wordt gewoonlijk gedefinieerd als:

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

Wat is een botsing (collision) in een hashtabel?

1. ATwee gelijke sleutels worden twee keer opgeslagen
2. BTwee verschillende sleutels worden op dezelfde index afgebeeld
3. CEen sleutel kan helemaal niet worden gehasht
4. DDe tabel heeft geen geheugen meer

Wat is een blad in een boom?

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

AVL-bomen en rood-zwartbomen garanderen:

1. AZoeken in constante tijd in elk geval
2. BDat geen enkele knoop twee kinderen heeft
3. CDat sleutels in invoegvolgorde worden opgeslagen
4. DEen hoogte van O(log n) door herbalancering

Welk abstract datatype gebruikt het algoritme van Dijkstra om de volgende te verwerken knoop te kiezen?

1. AEen stack
2. BEen min-prioriteitswachtrij
3. CEen FIFO-queue
4. DEen set zonder ordening

De sleutels 50, 30, 70, 20, 40 worden in deze volgorde in een lege binaire zoekboom ingevoegd. Wat is het linkerkind van 30?

1. A20
2. B70
3. C50
4. D40

Waarom gebruiken databases voor indexen vaak B+-bomen in plaats van gewone B-bomen?

1. AB+-bomen gebruiken binaire interne knopen, wat het aantal schijflezingen vermindert
2. BB+-bomen slaan data alleen in de wortel op
3. CAlle records staan in gekoppelde bladeren, wat bereikscans efficiënt maakt
4. DB+-bomen hoeven niet gebalanceerd te zijn

Welke garantie geven de regels van een rood-zwartboom over de hoogte van een boom met n sleutels?

1. ADe hoogte is hoogstens log₂ n + 1
2. BDe hoogte is hoogstens 2 log₂(n + 1)
3. CDe hoogte is hoogstens n / 2
4. DDe hoogte is precies log₂ n