Werkblad Datastructuren met antwoorden

Wat is de max-heap-eigenschap?

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

Wat definieert een binaire boom?

1. AElke knoop slaat een binair getal op
2. BElke knoop heeft precies twee kinderen
3. CElke knoop heeft hoogstens twee kinderen
4. DDe boom heeft precies twee niveaus

Wat is de wortel van een boom?

1. AEen knoop zonder kinderen
2. BEen willekeurige knoop in het midden
3. CDe bovenste knoop zonder ouder
4. DDe knoop met de grootste waarde

Bij welke methode voor het oplossen van botsingen worden botsende sleutels in een lijst in dezelfde bucket opgeslagen?

1. ALineair proberen (linear probing)
2. BDubbel hashen (double hashing)
3. CSeparate chaining (ketenen)
4. DKwadratisch proberen (quadratic probing)

Hoeveel knopen heeft een perfecte binaire boom met hoogte h, waarbij de hoogte in kanten wordt geteld?

1. Ah²
2. B2h + 1
3. C2^h+1 − 1
4. D2^h

Een trie (prefixboom) is bijzonder efficiënt voor:

1. AGetallen sorteren
2. BKortste paden vinden
3. CMatrices opslaan
4. DZoeken op prefix, zoals automatisch aanvullen

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

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

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 queue (of een willekeurige verzameling) van knopen met ingraad 0
3. CEen stack van alle bezochte kanten
4. DEen max-heap geordend op uitgraad