Werkblad Datastructuren met antwoorden

Wat is de wortel van een boom?

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

Hoe heet de queuebewerking die het element vooraan verwijdert?

1. ADequeue
2. BInsert
3. CPush
4. DEnqueue

In welke volgorde bezoekt een postorder-doorloop van een binaire boom de knopen?

1. ALinkersubboom, dan knoop, dan rechtersubboom
2. BKnoop, dan linkersubboom, dan rechtersubboom
3. CRechtersubboom, dan knoop, dan linkersubboom
4. DLinkersubboom, dan rechtersubboom, dan knoop

Hoe wordt een nieuw element in een binaire heap ingevoegd?

1. ABouw de hele heap opnieuw op
2. BVoeg het op de gesorteerde positie in door alle grotere elementen één plaats naar rechts te verschuiven
3. CPlaats het in de wortel en laat het omlaag zakken (sift down)
4. DPlaats het aan het eind van de array en laat het omhoog zakken (sift up) zolang het de heap-eigenschap schendt

Hoe werkt extract-min in een binaire min-heap?

1. AVerwijder de wortel en schuif alle elementen één plaats naar links
2. BVerwijder het laatste element van de array
3. CVerplaats het laatste element naar de wortel en laat het omlaag zakken (sift down)
4. DZoek in alle bladeren naar het nieuwe minimum

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)

Wat is onder simple uniform hashing de verwachte zoektijd in een hashtabel met chaining, n sleutels en m buckets?

1. AO(m)
2. BO(1 + α), waarbij α = n / m
3. CO(n)
4. DO(log n)

Wat doet een splay tree na elke toegang?

1. ARoteert de benaderde knoop omhoog naar de wortel
2. BKleurt de knopen op het zoekpad opnieuw
3. CBouwt de hele boom gebalanceerd opnieuw op
4. DVerplaatst de benaderde knoop naar een blad