Werkblad Datastructuren met antwoorden

Wat slaat een map (dictionary) op?

1. AAlleen waarden in volgorde van invoegen
2. BParen van gelijke sleutels
3. CSleutel-waardeparen met unieke sleutels
4. DWaarden gesorteerd op grootte

In een binaire zoekboom zijn de waarden in de linkersubboom van een knoop:

1. AGroter dan de waarde van de knoop
2. BKleiner dan de waarde van de knoop
3. CGelijk aan de waarde van de knoop
4. DIn willekeurige volgorde

Wat is de max-heap-eigenschap?

1. ADe sleutels zijn van links naar rechts gesorteerd
2. BDe sleutel van elke ouder is groter dan of gelijk aan de sleutels van zijn kinderen
3. CDe sleutel van elk linkerkind is groter dan of gelijk aan de sleutel van zijn rechterbroer
4. DAlle bladeren bevatten de maximale sleutel

Een applicatie heeft snel opzoeken nodig en moet ook sleutels gesorteerd kunnen opsommen en bereikquery's beantwoorden. Welke structuur past het best?

1. AEen hashtabel
2. BEen ongesorteerde gekoppelde lijst
3. CEen stack
4. DEen gebalanceerde binaire zoekboom

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

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. BAlle sleutels in een heap zijn gelijk
3. CArrays houden sleutels automatisch gesorteerd, dus er zijn geen pointers nodig
4. DHeaps bevatten nooit meer dan 100 elementen

Wat zijn, zonder union by rank of path compression, de kosten in het slechtste geval van één find in een union-findstructuur met n elementen?

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

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

1. AHashwaarden moeten priemgetallen zijn
2. BVerschillende sleutels moeten verschillende hashwaarden hebben
3. CGelijke sleutels moeten gelijke hashwaarden hebben
4. DGelijke hashwaarden impliceren gelijke sleutels