Werkblad Datastructuren met antwoorden

In een enkelvoudig gekoppelde lijst bevat elke knoop:

1. AAlleen data
2. BData en verwijzingen naar alle andere knopen
3. CData en een verwijzing naar de volgende knoop
4. DData en een index

Een hashtabel slaat data op als:

1. AUitsluitend een gesorteerde lijst
2. BEen string met vaste lengte
3. CEen boom met geordende sleutels
4. DSleutel-waardeparen die via een hashfunctie worden gevonden

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

1. ALinkersubboom, dan rechtersubboom, dan knoop
2. BRechtersubboom, dan knoop, dan linkersubboom
3. CKnoop, dan linkersubboom, dan rechtersubboom
4. DLinkersubboom, dan knoop, dan rechtersubboom

Wat is het doel van een sentinelknoop (dummyknoop) in een gekoppelde lijst?

1. ADe code vereenvoudigen door speciale gevallen aan kop of staart weg te nemen
2. BVoorkomen dat de lijst groeit voorbij een vast maximumaantal knopen
3. CDe lijst gesorteerd maken
4. DHet aantal elementen opslaan

Hoe lang duurt het om met een adjacency matrix te controleren of de kant (u, v) bestaat?

1. AO(V)
2. BO(log V)
3. CO(1)
4. DO(E)

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

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

Welk probleem van linear probing vermindert double hashing vooral?

1. ADe noodzaak van een hashfunctie
2. BPrimaire clustering, waarbij lange reeksen bezette plaatsen ontstaan
3. CDe noodzaak om sleutels in de tabel op te slaan
4. DDe O(n)-kosten van het lezen van de waarde van een sleutel

Welke bewerkingen ondersteunt een Fenwick-boom (binary indexed tree) over een array van n getallen in O(log n)?

1. ADe array sorteren en binair zoeken
2. BElementen op elke positie invoegen
3. CPrefixsomquery's en updates van één element
4. DDe mediaan vinden in O(1)