Werkblad Datastructuren met antwoorden

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

1. AGelijk aan de waarde van de knoop
2. BGroter dan de waarde van de knoop
3. CKleiner dan de waarde van de knoop
4. DIn willekeurige volgorde

Wat slaat een map (dictionary) op?

1. ASleutel-waardeparen met unieke sleutels
2. BWaarden gesorteerd op grootte
3. CParen van gelijke sleutels
4. DAlleen waarden in volgorde van invoegen

Hoe heet de stackbewerking die een element bovenaan toevoegt?

1. APop
2. BPeek
3. CPush
4. DEnqueue

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. C40
4. D50

AVL-bomen en rood-zwartbomen garanderen:

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

Een in-order-doorloop van een binaire zoekboom bezoekt de sleutels in:

1. AOplopend gesorteerde volgorde
2. BVolgorde per niveau
3. CInvoegvolgorde
4. DAltijd aflopende volgorde

De union-find-structuur (disjoint set) met union by rank en padcompressie heeft geamortiseerde kosten per bewerking van:

1. AO(α(n)), de inverse Ackermann-functie, die in de praktijk constant is
2. BO(n)
3. CPrecies O(log n)
4. DO(n²)

Een object wordt als sleutel in een hashmap opgeslagen, waarna een veld dat de hashfunctie gebruikt wordt gewijzigd. Wat is het waarschijnlijke gevolg?

1. AHet object opzoeken kan mislukken, omdat het in de bucket voor zijn oude hash staat
2. BDe map geeft een fout op het moment dat het veld verandert
3. CDe map verplaatst de sleutel automatisch naar zijn nieuwe bucket
4. DEr verandert niets, omdat de hash van een sleutel maar één keer wordt berekend wanneer het programma start