Werkblad Datastructuren met antwoorden

In een enkelvoudig gekoppelde lijst bevat elke knoop:

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

Welke datastructuur werkt volgens het principe "first in, first out" (FIFO)?

1. AHeap
2. BStapel (stack)
3. CBinaire boom
4. DWachtrij (queue)

Wat is een cykel in een graaf?

1. AEen knoop zonder kanten
2. BEen pad dat elke knoop bezoekt
3. CEen kant met gewicht nul
4. DEen pad dat begint en eindigt in dezelfde knoop

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

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

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

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

Een circulaire buffer (ring buffer) wordt vaak gebruikt om het volgende te implementeren:

1. AEen binaire zoekboom
2. BEen wachtrij met vaste grootte
3. CEen graafdoorloop
4. DEen hashfunctie

Een segmentboom (segment tree) wordt doorgaans gebruikt om:

1. AStrings alfabetisch te sorteren door elk voorvoegsel in een aparte boomknoop op te slaan
2. BEen stack te implementeren
3. CDe kanten van een graaf op te slaan
4. DBereikquery's (zoals bereiksommen) en updates in O(log n) te beantwoorden

Welke uitspraak over heapsort is juist?

1. AHet sorteert ter plaatse in O(n log n) in het slechtste geval, maar is niet stabiel
2. BHet heeft een binaire zoekboom nodig als extra opslag, dus het gebruikt O(n) extra geheugen
3. CHet draait op elke invoer in O(n) tijd
4. DHet is stabiel en heeft O(n) extra geheugen nodig